Memory Reader

Practice

3.6 (13 votes)

Dynamic programming

Algorithms

Introduction to dynamic programming 1

Problem

46% Success 2016 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

There is a new AI in town. It reads through horizontal strips of memory. Let the strip of memory be divided into blocks numbered \(1,2,3...\) etc. There is good data at some integer points on the memory given in an array \(memory\). The AI can only read at these points. The AI aims to read the last point of good memory. Also, the AI can only move in the forward direction. To read a memory, it can move from one good point to another. It can move its reader pointer to either \(L-1\) or \(L\) or \(L+1\) points if the length of its last jump was \(L\). Initially, it is at point 0 (which is always a good memory). The first move can only be to the first good memory point. Determine if it can move to the last memory. It is ensured that the good memory points are given in sorted order. Note: The AI doesn’t need to read all the good memory points. Input format: The first line contains \(T\), denoting the number of test cases. The first line of each test case contains one integer \(N\), denoting the number of good memory points. The second line of each test case contains an array \(memory\) of \(N\) space-separated integers, denoting the position of the good memory points. Output format: For each test case, print the string \(YES\) if the AI can read the last memory point, else print the string \(NO\). Constraints: \(1 <= T <= 10\) \(1 <= N <= 10^3 \) \(1 <= memory[i] <= 10^9\) \(memory[i] < memory[i+1]\)

Sample Input

2
6
1 2 3 4 5 6
2
1 11

Sample Output

YES
NO

Explanation

In the first test case, the good memory points are [1, 2, 3, 4, 5, 6]. So, the AI starts at 0. It then moves to 1, with a jump of 1. It then moves to 3 with a jump of 2. Finally, it moves to 6, with a jump of 3. Hence, the answer is \(YES\). In the second test case, the good memory points are [1, 11]. So, the AI first jumps to 1 with a jump of 1. Now, the valid jumps are 0, 1, or 2. But, it requires a jump of 10 to reach 11. Hence, it cannot reach the last point. So, answer is \(NO \).

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor