Atcoder always hosts its contests at the same time, it has nothing to do with codeforces rounds

Consider this graph where wi=i and 1 is connected to 1e5 nodes and these 1e5 nodes are directly connected to a chain of 1e5 nodes each in increasing value then your solution will run all possible paths which will be 1e5*1e5. In short, you algo is not stopping for the path it has already traveled before.

Similar case for my submission, could not figure out why it gives those 15 WA, appreciate any help, thanks.

Since a[j] >= a[i], the graph you are trying to dp on is not a DAG. You need to merge on vertices such that they are all connected by edges and are equal, then it will become a DAG.

I solve it with modified Dijkstra's 49115351 algorithm.

Hey all, found the issue. The issue happens when you have some connected components having the same value, and if the first node is connected to N, the later nodes will not have proper dp value. Now if some of the later nodes have longer paths we will not be counting them. Providing one test case related to that.

10 10
1 2 6 6 6 6 3 4 5 7
1 2 
2 3
3 4
4 5
5 6
3 10
1 7
7 8
8 9
9 6

To solve this as mentioned by Swishy123 we have to merge the same nodes, I have used DSU, you can check my Accepted code

It gives WA on the following test case as already mentioned by pedastrian57

10 10
1 2 6 6 6 6 3 4 5 7
1 2 
2 3
3 4
4 5
5 6
3 10
1 7
7 8
8 9
9 6

This solution is bounded by $$$O(N*sqrt(N))$$$ and mentioned in one of the editorial.

On this case this soln prints 59528480 as no of operations. This is roughly $$$300*N$$$.

You should only apply DP on the leader nodes for each component. Here's a theoretical scenario that would TLE if not implemented properly.

Consider a graph of $$$2 \cdot n$$$ vertices. Split all vertices into 2 equal groups.

If you try to update the DP value of all nodes in the first group, you would have to take contribution from each of the $$$n$$$ nodes from the second group (since all of them are reachable). Hence, the time complexity is $$$O(n*n)$$$.

The correct strategy is to populate the DP values of leader only. That is, instead of asking the best path from node $$$a$$$ in group 1 to node $$$b$$$ in group 2, ask about the best path from the leader of group 1 to the leader of group 2.

Video Editorial for F : Hop Sugoroku

Define $$$dp[i]$$$ to be the number of valid subsets of the first $$$i$$$ elements such that the $$$i^{th}$$$ element is necessarily painted black. The final answer is $$$\sum dp[i]$$$

The transitions are trivial, just follow the rules mentioned in the problem, i.e, $$$dp[i]$$$ contributes to all $$$j = i + a[i] \cdot x$$$.

Code

What if the array was a permutation? Can you prove that the naive DP works in $$$O(n \cdot log(n))$$$?

What if the array only consisted of $$$1s$$$? Do you see a way to optimize this DP? Note that each $$$i$$$ would update the suffix $$$[i + 1, \dots n]$$$. Hence, you can just use difference array to propagate the updates in $$$O(1)$$$. Hence, if you define $$$delta[i]$$$ to be the delta that needs to be pushed to the suffix, for each $$$i$$$, you can do $$$delta[i + 1] \mathrel{+}= dp[i]$$$. And you keep pushing that delta to the next element.

What if the array only consisted of $$$2s$$$? You now have to update $$$[i + 2, i + 4, \dots n]$$$. The strategy from above still works. For each $$$i$$$, $$$delta[i + 2] \mathrel{+}= dp[i]$$$. But while pushing the delta, the delta from the $$$i^{th}$$$ element would be pushed to $$$i + 2^{th}$$$ element.

What if the array only consisted of $$$3s$$$? What if the array had all elements equal to $$$z$$$? All of these individual cases can be solved in $$$O(n)$$$. So, if the array consisted of mixed integers, you can combine the same logic, now keeping a delta for each variable.

Code

Now, notice that the transitions are in $$$O(1)$$$. But the matrix size is huge. So, let's not maintain the delta values of $$$a[i] \gt \sqrt n$$$. Then, each time we encounter such $$$a[i]$$$, we can iterate over all its multiples and naively update the DP. Since $$$\sqrt n \cdot \sqrt n \geq n$$$, we would do no more than $$$O(\sqrt n)$$$ work for each such index. For the remaining $$$a[i]$$$, the delta value of variable $$$j$$$ would propagate from $$$i$$$ to $$$i + j$$$. Since $$$j \leq \sqrt n$$$, we can maintain a matrix of size $$$n \times \sqrt n$$$ to maintain these delta values.

Code

the time complexity for the above code is o(n*(logn)^2)

2.82 seconds doesn't mean that your code completed execution in 2.82 seconds. It means that Atcoder decided to terminate the execution after 2.82 seconds because the time limit was 2.5 seconds. For example, on this testcase shared by aryanc403, your code runs in 58 seconds on my machine (and this is when the array is generated on the fly, so factoring in I/O would increase the time as well).

1700, 1900

Try this test case, it returns 3 when it should return 4. 5 5 1 2 3 3 4 3 4 1 3 1 2 2 4 3 5 I wrote out this example, it creates adjacency list [[3, 2], [1, 4], [4, 1, 5], [3, 2], [3]] => dfs traversal order: [1, 3, 4, 5, 2 ] [2, 1, min, 0, min

It traverses the 1, 3, 4. And it places the vis = int_min, which prevents it from finding the optimal path later that is 1-2-4-3-5, instead it just finds 1-3-5. But if it is converted into a DAG by creating supernode (3, 4), then it will work. Because you can do DP on a DAG.