DCP-489: Country Roads Back to All Problems

Hard Divide and Conquer > Dynamic Programming


In a country there are **N** cities. The cities are numbered from **1** to **N**. There is a road from city **i+1** to **i** for all **i (1 ≤ i < N)**. The roads are uni-directional. The minister of the country decided to construct some more roads based on the array **A**. A road will be built from city **i** to city **j** where **(j < i)** if **( j ≥ A[i] )** and **gcd(i , j) > 1**. City number **1** is the capital of this country. Mr. Riki is currently staying at the **N** th city. He wants to go to the capital. You have to tell the minimum number of cities he has to visit (including **N** th city) to reach the destination. Input: ------ The first line contains an integer **T (1 ≤ T ≤ 5)**, denoting the number of test cases. Each case contains an integer **N (3 ≤ N ≤ 100000)** denoting the number of cities. The next line will contain **N** integers separated by spaces, denoting the elements of the array **A**. For any city **i** , (**1 ≤ A[i] ≤ i**). Output: ------- For each test, print the answer in a single line. Sample Input ------------ 2 5 1 1 2 2 4 6 1 2 3 4 5 1 Sample Output ------------- 4 3 **Test Case 1**: ![City Road Map][1] Here is the country road map. In the path **5 -> 4 -> 2 -> 1** , Mr. Riki has to visit **4** cities ; which is the minimum. **Test Case 2**: ![enter image description here][2] Here is the country road map. In the path **6 -> 2 -> 1** , Mr. Riki has to visit **3** cities ; which is the minimum. [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/b3d73cb6-fc86-cd01-0255-08d578e59eb1_f9aa2603ee724cc085518c1692e2521c_W323xH324.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/96570011-764b-cfc8-9e0c-08d57a3b736d_c27d53f5de4f4c5098fa42cc4192af07_W317xH323.png


Problem Setter:

Fahim Shahriar Shakkhor

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 3.00
C++ 3.00
C++14 3.00
C# 6.00
Go 6.00
Java 6.00
JavaScript 6.00
Objective-C 6.00
Perl 6.00
PHP 6.00
Python 6.00
Python3 6.00
Ruby 6.00
VB.Net 6.00

Problem Stats

14/139

Solve/Submission

Ranking

# User Language Timing
01 ovis96 Cpp14 0.49s
02 Morass Cpp14 0.95s
03 adarshkr532 Cpp14 0.99s
04 Robbinb1993 Cpp14 1.26s
05 Double_O Cpp14 1.49s
06 mahbubcseju Cpp14 1.52s
07 Mechanic Cpp14 1.97s
08 fsshakkhor Cpp 2.15s
09 roxter Java 2.96s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support