This is an easy problem with only 25% difficulty rating and it costs me about 10min to code. My code runs in 0s. The idea is so simple that we can calculate rad(n) for every n from 1 to 100000. As an optimization, a priority queue is used to keep the first 10000 smallest values.

It’s too hard for me that didn’t figure out the answer until refer to others’ solution.

First of all, we can find that the number of moves is n(n + 2)refer to A005563 then what we need is to solve integes solution of equation n*(n+2) = t(t+1)/2 using this tool.

After reading problem description, It is evident that we need generate Grundy numbers from 1 to 10^6. But it will take a long period to do this. So what should we do in this case is to find if there is a pattern in Grundy numbers sequence. Brute-force to get the first several Grundy numbers and find that if we ignore non-zero values then it is a pattern.

It’s really a hard problem for me but it forces me to learn a new algorithm that computing sum of all primes below n. My code runs in 550 seconds after using OpenMP as an optimization. In order to solve this one, you’d better take a look at the method of counting primes that introduces a dp method to count the number of primes not exceeding n. This algo’s running time complexity is $O(n^{0.75})$ which is fast enough for this problem. The most important thing this problem brings to me is that there are methods to compute sum of primes without generating all primes first.

This problem can be solve using dynamic programming. My code runs in nearly 0.0 seconds. It is also works to enumerate all distinct permutations generated by given digits. Tha total amount of permutations should be 20!/(2^10) but I didn’t calculate what exactly the factorial is. I think it’s not difficult to figure out the dp solution.

Such problems are very straight forward, but if you want to make your code runs fast it needs several optimizations. My code runs in 4.04655s and I am not going to optimize it anymore. There are several observations here: 1. n + 1 must be a prime. 2. n must be an even number cuz (n + 1) wouldn’t be a prime if n is an odd. 3. n is a squarefree number.

It costs me half an hour to figure out the solution. My code runs in 6.92312s. The most important insight is: $s(n) = \max_i{p_i^{k_i}}$ where $n = \prod_i p_i^{k_i}$. So problem is reduced to calculate $s(p^k)$ where p is a prime.

It spent me 5min to solve this probelm, so really an easy one. My code runs in nearly 0 seconds. Above two thousand people have solved this task and it’s difficulty rating is only 10%. Someone can solve this problem easily as long as he/she knows how to calculate expectation.

This is an easy problem. My code runs in 0.045598s. At first, I was trying to generate all the palindromic numbers and then check whether they can be formed by consecutive squares one by one. Although it yield correct answer but needs 13.xx seconds which is unbearable. Let’s consider from another view. If we generate all possible distinct sum of consecutive squares and then check if the sum is a palindromic number and if yes, add it to our answer. Do not forget there might duplications when generate sum of consecutive squares, so I use a undered_set to mark a number as visited.