September Challenge 2018

Official editorial:


I don't know why this is correct.


View the win-loss table diagonally and alternately. You can realize that the values almost unchange except for the both ends. So you can compute the all of values sequentially and compute the answer at an appropriate time.


Let's list the continuous subsequences such that the right end is R. Actually, the number of distinct values is at most 30. That is why for each adjacent values x and y, x is a proper subset of y, so at least one bit is lost.


This is an implementation problem (I supposed).


My simple O(NQ) dp solution pass the all test cases. It is no wonder. 5 seconds should be enough. The key property is similar to Ant (introduced in Antbook). By this property, each ants is not necessary to be distinguished. After that, only have to do is to compute the expectation at each positions. It is achieved by standard Markov-Chain like DP.


I have seen a similar problem. So I didn't feel it difficult. My solution is a little dirty. Given information about the order of the group (it's equivalent to Euler's phi), you can use Euler's theorem. It states that any element of the group raised to the power of the order of group is always equal to 1. Considering analogy of Miller-Rabin method, you can find x such that x^2=1 (mod N) and x is neither 1 or -1 with high probability, but skip the details here. If x is neither 1 nor -1, x-1 is a nontrivial divisor, so this problem is reduced to N/(x-1). Repeating this procedure, finally you can factor N. You might notice that if N is not square-free, this algorithm doesn't work properly, but this can be resolved by reducing to N to N/gcd(N,phi(N)).


My solution is perfectly wrong but luckily passed all test cases.


Is there any approximation algorithm?