alexandrethiault
commented
4 years ago Merci !
In order to complete all Doubling Danny test cases you had to think of this special case. Something to be aware of is the periodicity of the sequence u_n = ((2^n) mod m). If you know the period T, then (2^n) is equal to (2^(n mod T)) modulo m. The period is always a divisor of m-1 if m is prime (see Euler's theorem), in general m-1 itself, but in some rare cases (like m being a power of 2 minus one) it can be arbitrarily small, making the calculations a piece of cake. I found it kind of disappointing that we were given input limits that would never be present at the same time, like a very big prime number that doesn't have such a tiny period to simplify calculations. But, since all the very big primes we know are just like these, I guess they had no choice.
Now, to actually find out that the last few test cases had primes of the form p=2^k-1, I used some silly reverse engineering that should be completely impossible in any normal programming competition, but is somehow encouraged with this format. Import time, write an if test for something you want to know about from the 10 inputs, write time.sleep(x) for x of your choice depending on the result of the test, and return a wrong answer immediately after that. Alternatively, force a timeout with time.sleep(50) if you know your solution can't timeout anywhere else. As GSA gives you the return time of your solution, even when it is wrong, you can gather a lot of info. That's how 2 people got a 0 second solution at Gone to Seed on the last day of the competition, before removing it after the warning email from GSA: only the 10th input was hard to solve (16 tennis players), but that's still only 16 numbers from 1 to 20. 80 tests later you can recover the entire 10th input, take all your time to solve it on your machine, then hard code return the_answer_you_found.
Snakes and ladders as a board game is a source of a couple of classic DP problems. In our case, set dp[i] := expected time to go from square i to the end. We are looking for dp[0]. Saying the expected time to finish from square n is 1 plus the mean of the expected times from each of the squares n can directly lead to, one can find a lot of equations like dp[n] = 1 + 1/6(dp[n+1] + dp[n+2] + ... + dp[n+6]), put them in a matrix M and solve Mdp = B with B being all ones. dp[0] is then the first coefficient of (M^-1)B, which is the sum of the coefficients from the first line of (M^-1). The main source of timeouts is, M can be pretty big. You had to exploit the sparse nature of the matrix, which allows for faster inversion algorithms. Also, computing the sum of the coefficients from the first line of (M^-1) doesn't require you to fully compute that matrix inverse. But even with those two observations, I was unable to pass more than 8 tests on this problem. That's why I haven't published my solution on this one :) For more detailed explanations on the DP, see this Quora answer for example.
P.S. Nice HSFS profile pic ;)
changle0703
Tes solutions sont géniales!
A7 Doubling Danny je pense que ta solution spéciale a bien aidé.
Qu'était ta idée de 5D Snake and Ladders?