Please click on ads to support us..

Python Code:

import io,os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):


    n = int(input())
    arr = list(map(int,input().split()))

    dp = [False]*(n+1)
    dp[-1] = True


    for i in range(n):
        if dp[i-1] and i + arr[i] < n:   dp[i+arr[i]] = True
        if i - arr[i] >= 0 and dp[i-arr[i]-1]:  dp[i] = True


    
    if dp[n-1]:   print("YES")
    else:  print("NO")





















T = int(input())
t = 1
while t<=T:
    main(t)
    t += 1

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5 + 100;
int n, a[N], dp[N];
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = 0;
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(dp[i - 1] && i + a[i] <= n) dp[i + a[i]] = 1;
        if(i - a[i] >= 1 && dp[i - a[i] - 1]) dp[i] = 1;
    }
    cout << (dp[n] ? "YES" : "NO") << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}

// .........................................................................................................................
// .........................................................................................................................
// .........................................................................................................................
// ..............................................................]OOO]]/O]`.................................................
// .........................................................../OO@@@@@@@OOOOO`..............................................
// ........................................................./@@@@@@@@@@@@@@@@@O\............................................
// ........................................................O@@@@@@@@@@@@@@@@@@@OO\..........................................
// ........................................................=@@@@@@@@OOOO@@@@@@@@@^..........................................
// .........................................................O@@@@@@OoooOO@@@@@@@@...........................................
// ..........................................................\@@@OOOOOOOO@@@@@@@`...........................................
// ...........................................................O*,[[[*OOOOOOO@O^.............................................
// ...........................................................,,*,`*,Ooo]oOOO/..............................................
// .......................................................,/@@@ooo^/OOOOOOO.................................................
// ...................................................=@@@@@@@@@oo/\OOOOOO@^................................................
// .............................................,]@@^..@@@@@@@@@@\,\oooO@@@@@@`.............................................
// ...........................................@@@@@@@^.=@@@@@@@@@@@OOO@@@@@@@@@.=\..........................................
// ..........................................=@@@@@@@@.*@@@@@@@@@@@@@@@@@@@@@@@..@@\`.......................................
// ........................................@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@@@@@/.=@@@@@@\`...................................
// ......................................,@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@^.=@@@@@@@@@\.................................
// ....................................,@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@.*@@@@@@@@@@@@................................
// .................................../@@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@*=@@@@@@@@@@@@@]`.............................
// ................................,@@@@@@@@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@\..........................
// ..............................,@@@@@@@@@@@@@@@@@@@@^`@@@@@@@@@@@@@@@@@@@@@o,@@@@@@@@@@@@@@@@@@@@O........................
// ............................,@@@@@@@@@@@@@@@@@@@@@@**@@@@@@@@@@@@@@@@@@@@/*/@@@@@@@@@@@@@@@@@@@@@@@@@@OOo\]]*****........
// ........................../@@@@@@@@@@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@^\@@@@/..[@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@O\`.....
// ......................./@@@@@@@@@@@@@/`.=@@@@@@@@@^`@@@@@@@@@@@@@@@@@@@@/*@@@@@........[\@@@@@@@@@@@@@@@@@@@@@@@@@@@\*...
// ....................,/@@@@@@@@@@/[....,@@@@@@@@@@@*,@@@@@@@@@@@@@@@@@@@@,@@@@/..............,[O@@@@@OOOoOoooOOOoOOOOO*...
// ..................,@@@@@@@@@@/.......=@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@\@@@@`....................=OOOooOoooooooOOOooo*...
// ................,@@@@@@@@@@`........,@@@@@@@@@@@@`*@@@@@@@@@@@@@@@@@@@/@@@`...................../OOOOOOOoooooOOOOOO^=....
// .............../@@@@@@@@@`..........@@@@@@@@@@@@/*=@@@@@@@@@@@@@@@@@O@@[......................./OOOOOOOOOooOOOOOOOO\o*...
// ............../@@@@@@@@`...........=@@@@@@@@@@@@=\@@@@@@@@@@@@@@@@@@@/........................=OOOOOOOOOOOOOOOOOOOOoo*...
// ............,@@@@@@@/..............[@[@@@@@@@@@@@@@@@@@@@@@@@@@@@@`...........................=OOOOOO@OOO@OOOOOOOOOOO^...
// ...........,@@@@@@@/.................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@].........................OOOO@OOO@OOOOOOO@@OOOO`...
// ..........,@@@@@@@`..................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^........................=O@@@@@@@@@@@@@@@@@@/.....
// ..........*\@@@@/....................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^.........................,O@@@@@@@@@@@@@@@O^......
// .........*=oooO[.....................=@@@OOO@@@@@@@@@@@@@@@@@@@@@@@@@@............................,OO@@@@@@@@@@O/........
// .........oO^.=^......................=@@@OO@@@@@@@@@@@@@@@@@@@@@@@@@@OO.............................*[\OOOOO/[*..........
// ........,O^..=^.......................OOOOOOOO@@@@@@@@@@@@@@@@@@@@@@OOOO`................................................
// .........O\...........................OOOOOOOOO@@@@@@@@@@@@@@@@@OOOOOOOOO`...............................................
// ..........,..........................=OOOOOOOOOOO@@@@@@@@@@@OOOOOOOOOOOOOO\..............................................
// .....................................OOOOOOOOOOOOOO@@@@@@@@@@@@@@OOOOOOOOOOO.............................................
// .....................................OOOOOOOOOOOOOOO@^.,\@@@@@@@@@@@@@@@OOOOO`...........................................
// .....................................,[email protected]@@@@@@@@@@O@@@OOOOO^..........................................
// .......................................OOOOOOOOOOOOO^......,@@@@@@@@@@@@@OOOOOO^.........................................
// .......................................=OOOOOOOOOOOO^........,@@@@@@@OOOOOOOOOOO^........................................
// ........................................OOOOOOOOOOOOO..........\@@@@@@@@OOOOOOOOO`.......................................
// ........................................=OOOOOOOOOOOO............\@@@@@@@OOOOOOOOO.......................................
// ........................................=OOOOOOOOOOOO^.............\@@@@@@@OOOOOOO\......................................
// .........................................OOOOOOOOOOOO\..............=@@@@@@@@OOOOOO\.....................................
// **....********...........................OOOOOOOOOOO@@`..............,@@@@@@@@@OOOOO^....................................
// **************..........................OOOOOOOOO@@@@`.................=@@@@@@@@@@OOO`...................................
// ********************....***.............OOOOOOO@@@@@^..................,@@@@@@@@@@@@O....................................
// ********************..*************.....=OOOO@@@@@@^....................=@@@@@@@@@@@/....................................
// .************************************...=OOOO@@@@@@^....................O@@@@@@@@@@@.....................................
// ...************************************.=OOOO@@@@@@^.................../@@@@@@@@@@@^.....................................
// ......*..****************************.*.=OOO@@@@@@@^..................,@@@@@@@@@@@O......................................
// **...*******]]]]]]]]]]]]]]]]]]]]]]]`****=OOO@@@@@@@`..................=@@@@@@@@@@@^......................................
// ********=oooooooo**ooo*******************OOO@@@@@@O*******************O@@@@@@@@@@O***************************************
// *****************************************OO@@@@@@@^*******************O@@@@@@@@@@^***************************************
// *****************************************OO@@@@@@@********************O@@@@@@@@@/****************************************
// *****************************************=O@@@@@@O********************O@@@@@@@@O*****************************************
// *****************************************,O@@@@@@\.******************/@@@@@@@@O******************************************
// ********************************..........=OOOO@@O.*****.....******.=@@@@@@@@O*******************************************
// *********************************.......*.,@@@@@@^....**........***./@@OOO@@/********************************************
// **********************************........=@@@@@@^....****.......*.,@@@@@@@O************************..*******************
// *******************************...........@@@@@@@O..............*./@@@@@@@@^.******.*************************************
// **.......................................=@@@@@@@@*..............=@@@@@@@@@@^******.*************************************
// ........................................./@@@@@@@@...............@@@@@@@@@@@@^...........................................
// *.......................................=@@@@@@@@^..............@@@@@@@@@@@@@@\*...*************.........................
// ........................................@@@@@@@@^..............,@@@@@@@@@@@@@@@@@O]`*********..*.........................
// .......................................@@@@@@@@@^............****]/O@@@@@@@@@@@@@@@@O**************......................
// ......................................=@@@@@@@@@^.....**********,oooOOOOOO@@@@@@@@@@@^***************....................
// .................................**...=@@@@@@@@@^***************,oooooOOOOOoooooooo/`******************..................



Comments

Submit
0 Comments
More Questions

448. Find All Numbers Disappeared in an Array
1155. Number of Dice Rolls With Target Sum
415. Add Strings
22. Generate Parentheses
13. Roman to Integer
2. Add Two Numbers
515. Find Largest Value in Each Tree Row
345. Reverse Vowels of a String
628. Maximum Product of Three Numbers
1526A - Mean Inequality
1526B - I Hate 1111
1881. Maximum Value after Insertion
237. Delete Node in a Linked List
27. Remove Element
39. Combination Sum
378. Kth Smallest Element in a Sorted Matrix
162. Find Peak Element
1529A - Eshag Loves Big Arrays
19. Remove Nth Node From End of List
925. Long Pressed Name
1051. Height Checker
695. Max Area of Island
402. Remove K Digits
97. Interleaving String
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
501A - Contest
160A- Twins
752. Open the Lock