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.
same problem https://codeforces.net/contest/911/problem/G
this also solved with pragma
not same , there is a change in constraints...
You can't apply the algorithmic idea(which is discussed in cf editorial) of this problem in the criterion's one.
The intended solution to this problem was not with a pragma. However, compiler optimization wasn't one of the things we expected as we had no idea about it before.
But you learn new things every day, right? ;)
Now about the similarity between these problems: though we didn't know the existence of this problem before a contestant drew our attention after the contest, there is a change of constraint in our problem which made today's problem more challenging, I guess. Besides, the probability of getting matched this type of classic problem with some other exiting problem is really high, isn't it?
So, I'll recommend you to solve this problem without using any kind of compiler optimization or whatsoever.
Happy Coding. ^ _ ^
Can someone explain D: Stick Game in more detail.
Thanx in advance
In D, you will be given two types of query. In the first one you have to replace the numbers from L to R by A.
Suppose the array is {1,2,3,4,5,6,7}.
At first abstract numbers are {0,0,0,0,0,0,0}.
If a type 1 query where L = 3, R = 5 and A = 10. Then the new array will be {1,2,10,10,10,6,7}.
Now the abstract numbers will be {0,0,7,6,5,0,0}.
Again a type 1 query where L = 4, R = 6 and A = 7. Then the new array will be {1,2,10,7,7,7,7}.
Now the abstract number will be {0,0,7,9,8,1,0}.
Here you can use either square root decomposition or segment tree whichever you prefer. After several queries, the numbers will be placed in such a order where we can easily use lazy propagation.