AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement

We will hold AtCoder Beginner Contest 335 (Sponsored by Mynavi).

We are looking forward to your participation!

• 41 hour(s) ago, # ^ | Atcoder always hosts its contests at the same time, it has nothing to do with codeforces rounds

  • 41 hour(s) ago, # ^ | I mean, they're are not only close by time, but often are in the same days

    • 41 hour(s) ago, # ^ | ← Rev. 3 →   +8 Atcoder (almost) always hosts its contests on saturdays and sundays, it has nothing to do with codeforces rounds. It just happens that codeforces also often hosts contests during the weekend.

      • 41 hour(s) ago, # ^ | ← Rev. 2 →   0 Now it makes sense, thanks

• 15 hours ago, # ^ | ← Rev. 2 →   +5 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.

  • 15 hours ago, # ^ | Besides atcoder and codechef, do other sites remind CodeForces users about their competitions?

  • 15 hours ago, # ^ | Got it.

• 15 hours ago, # ^ | Similar case for my submission, could not figure out why it gives those 15 WA, appreciate any help, thanks.

  • 15 hours ago, # ^ | Maybe you can have a look at this case 5 5 1 2 3 3 4 1 2 2 4 3 4 1 3 3 5 If your output is correct, maybe there is some other reason

• 15 hours ago, # ^ | 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.

  • 15 hours ago, # ^ | But the value of dp[i] will not change if I move to the same color vertices. Am I missing something, can you point out one such case?

    • 15 hours ago, # ^ | Well... The graph is not DAG in the first place, so topo sort won't work.

      • 15 hours ago, # ^ | If we are only traversing v[j]>v[i] then its kind of traversing a dag only, if we are traversing v[j]=v[i] the value of dp[i] wont change right? What could be the issue then

        • 10 hours ago, # ^ | What if there are two nodes with same a[] values but are not adjacent in path traversed by your dfs? It will get counted twice!

• 15 hours ago, # ^ | ← Rev. 9 →   0 I solve it with modified Dijkstra's 49115351 algorithm.

  • 14 hours ago, # ^ | I don't understand why Dijkstra's algo works faster with a set that sorts by the integer written on each node rather than by the score that was calculated for each node. Doesn't Dijkstra's algo always prioritize choosing and processing the node with the shortest calculated distance first? Then why it doesn't work in this problem. Shortly, set<pair<int, int>> as {res[u], u} -> TLE. TLE code set<pair<int, int>> as {a[u], u} -> Accepted (a[u] is the number written on node u) Accepted code Can anyone explain it to me, please?

• 14 hours ago, # ^ | 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. Spoiler To solve this as mentioned by Swishy123 we have to merge the same nodes, I have used DSU, you can check my Accepted code

  • 12 hours ago, # ^ | Can you please explain the idea of your dsu solution.

• 7 hours ago, # ^ | This solution is bounded by O(N∗sqrt(N))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∗N300∗N.

• 76 minutes ago, # ^ | ← Rev. 2 →   0 Define dp[i]dp[i] to be the number of valid subsets of the first ii elements such that the ithith element is necessarily painted black. The final answer is ∑dp[i]∑dp[i] The transitions are trivial, just follow the rules mentioned in the problem, i.e, dp[i]dp[i] contributes to all j=i+a[i]⋅xj=i+a[i]⋅x. Code What if the array was a permutation? Can you prove that the naive DP works in O(n⋅log(n))O(n⋅log(n))? What if the array only consisted of 1s1s? Do you see a way to optimize this DP? Note that each ii would update the suffix [i+1,…n][i+1,…n]. Hence, you can just use difference array to propagate the updates in O(1)O(1). Hence, if you define delta[i]delta[i] to be the delta that needs to be pushed to the suffix, for each ii, you can do delta[i+1]+=dp[i]delta[i+1]+=dp[i]. And you keep pushing that delta to the next element. What if the array only consisted of 2s2s? You now have to update [i+2,i+4,…n][i+2,i+4,…n]. The strategy from above still works. For each ii, delta[i+2]+=dp[i]delta[i+2]+=dp[i]. But while pushing the delta, the delta from the ithith element would be pushed to i+2thi+2th element. What if the array only consisted of 3s3s? What if the array had all elements equal to zz? All of these individual cases can be solved in O(n)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)O(1). But the matrix size is huge. So, let's not maintain the delta values of a[i]>n−−√a[i]>n. Then, each time we encounter such a[i]a[i], we can iterate over all its multiples and naively update the DP. Since n−−√⋅n−−√≥nn⋅n≥n, we would do no more than O(n−−√)O(n) work for each such index. For the remaining a[i]a[i], the delta value would propagate from ii to i+a[i]i+a[i]. Since a[i]≤n−−√a[i]≤n, we can maintain a matrix of size n×n−−√n×n to maintain these delta values. Code