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.

Codeforces Round #708 k-LCM - Construction

When $k=3$, if n is a odd number, then the answer is: $a_0=1$, $a_1=\frac{n-1}{2}$, $a_2=\frac{n-1}{2}$When $k>3$, we just fill up the array with 1 until last 3 elements.

xloypaypa's Blogxloypaypa

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.

Codeforces Round #708 Genius - DP

This problem remind you about the memory limitation at very begin. Normally, it’s State compression DP.

xloypaypa's Blogxloypaypa

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...

Codeforces Round #708 Square-free division - DP

There is only one case to make product is a perfect square: For each number, the number of occurrences of prime factors is count[i]. if any different $i$, $j$ to make count[i]=count[j].

xloypaypa's Blogxloypaypa