Hello Community,
Thanks for participating in Criterion 2020 Round 6.
Standing: here.
A. Code At The Time of Pandemic
Author: Hasinur_
This problem is very simple. Let, totali = Number of total infected people till the ih day. So, the number of new infected people on (i+1)th day newi+1 = totali * 2 and total number of infected people till (i+1)th day = totali + newi+1 Totali and newi become large with increasing N. So, the calculation may not fit into 32-bit integer calculation.
Author: Shefin_
The main idea is: for each k, pre-calculate all possible values of ( (1+k) x (1+2k) x …. x (1+ik)) mod m, where ik <= 2^27. But to store them, we need a huge amount of memories. So, we will store the values maintaining a period. For example, if we maintain a period of length = 1000 and we store the values in an array called pre[], then for each k,
pre[1] will store ( (1+k) x (1+2k) x …. x (1+1000k) ) mod m pre[2] will store ( (1+k) x (1+2k) x …. x (1+2000k) ) mod m and so on.
If we need to calculate ( (1+k) x …. x (1+2115k) ), then we can use the value stored in pre[2] and calculate the rest manually. As we are maintaining a period of length = 1000, we don’t need to run more than 1000 loops to perform that rest calculation.
The rest of the task is pretty simple. They are for the readers to find out.
[Note: The length of the period should not be much large. In that case, a large amount of loop will be needed in each test case and that will give a Time Limit Exceeded verdict.]
Author: Hasnaine_
It is a simple Dp problem with a little bit of combinatorics in it. If you have the basic idea of dynamic programming, you might have solved this problem already in the contest.
So, we have to calculate from a certain node how many other nodes are there along the way where he will pass at least one road with prime numbers. Then if there is a total of x nodes from the node y where he will meet the condition. Ans will be increased to (xP2 = x permutation 2) or simply x * (x — 1). You can calculate the number of nodes y from every node x by a single or two dfs using dynamic programming.
Complexity(O(n))
D: Stick Game
Author: Dhruba10414
When a beauty number becomes replaced by another number in a range, after a few updates it will be several blocks continuously with the same numbers. You have to merge them in one big block. Use segment tree to do this. You can also use square root decomposition in this problem.
Complexity O(nlogn).
Author: tanus_era
At first divide the array into sqrt(n) blocks, where each block contains sqrt(n) elements. This trick is called sqrt decomposition. Then the update queries can be done using DSU(Disjoint Set Union) in each block. Total time complexity is O(q*sqrt(n)) . Here m is the number of queries and n is the size of the array.
This problem can also be solved in bruteforce, by using some compiler optimization trick. Setters were not aware of this technique, but some(Almost everyone having an AC solution of E) contestants have solved this problem using that. Here you can learn about that technique.
