Codeforces Round #708 Div2 Solution

_{Skip problem AB for this round.}

C2. k-LCM (hard version)

Simple construction problem. The point is $\frac{n}{2}$. After dividing by 2, LCM is $\frac{n}{2}$. Then we just think of a way to subtract one, and make it can divide 2.

D. Genius

Normal. Know it's DP at very beginning. The memory limit is telling you it state compression DP directly.

The breakthrough point is: if just move forward, no need skip any questions.

And the IQ is only related to i and j. So it's safe to move backward.

The last issue is the case of same tag. Or state compression. Just normal things.

E2. Square-free division (hard version)

I not solved this problem by myself. I looked some others' solution.

I found the way to calculate the left, also thought about the dp definition. But not calculate dp successfully. So Sad.

I was trying to find some $O(n\cdot{k})$ solution. Because it need 4000,000 times calculation.  And think may get TLE for $O(n\cdot{k})$ solution.

But after looked others' solution, $O(n\cdot{k^2})$ solution is ok. Then fine...