Probably yes, since we "are going to assist Slastyona the Sweetmaid".

yes it was ...

Everything is possible in Sweetland :)

awkward boner

... Mike, change my handle from I_love_Tanya_Romanova to I_love_Slastyona since I don't love Tanya Romanova anymore

You can participate in the contest, just register to div2 version.

It seems like everybody refers to that color as yellow here on CF. I was starting to think I have some type of color hue blindness because it looks orange to me also.

:O

you will see what you want to see

Это превентивный ответ на вопрос, уже ставший классикой

Don't discuss problems during an active contest!

If you have any doubt regarding any question.You can use the option "Ask A Question", which is down side of the Dashboard

All the best!

"undefined" means that we "cannot decide" it is "clock wise" or "counter clock wise". It does not mean that it is "impossible".

Replacing cin by scanf takes about 60 seconds, there are still more than 400 seconds remaining, you are not out of time man.

Let's denote:

• cw_state is the Toy's state we achieve if we rotate it in clockwise.

• ccw_state is the Toy's state we achieve if we rotate it in counter-clockwise.

Then:

• "undefined": cw_state = ccw_state OR (final_state != cw_state && final_state != ccw_state)

• "cw": if cw_state = final_state

• "ccw": if ccw_state = final_state

Hope you find it useful

1/7 of the planet :D

They have 150 crore

This is my simple decision but so far I do not know whether it's right)

http://mirror.codeforces.com/contest/834/submission/29014215

Assume, Slastyona won when k₁, k₂, ...k_x were chosen, and Pushok won at k(x + 1), ...k_r. There x — number of rounds which Slastyona and r — number of all rounds.
Then A = k₁ * k₂ * ... * k_x, B = k(x + 1) * ... * k_r.
Then a = A² * B;b = A * B²
So if B = a / A² then b = A * (a / A²)² and b = a² / A³. So a² / b must be cubic. Anaogically b² / a must be cubic either.

a can be written in form x²y and b can be written in form xy² from this we can write ab as (xy)³ with binary search we find xy then check if really (a / xy) * (b / xy) = xy.

O(1) solution: Find . If it's not an integer, return NO. Otherwise, if s divides both a and b, return YES, otherwise return NO. (Cube root can be found by binary search, for example.)

To prove that this works, note that ab must be a cube, since every round it is multiplied by k³ for some k. Moreover, if we set ab = s³, then the product of all k played in the game is s. Thus we need to have both a and b divisible by s, since they are the product of all k played in the game, plus probably some more numbers. And this is all we need; if ab = s³, let a = sx and b = sy, so we see xy = s. Thus a = x^2y, b = xy², so one possible game is a winning a game with k = x and b winning a game with k = y.

EDIT: To avoid TLE, use very fast input/output methods because you're reading 700k numbers.

But my n*k*logn*logn did not pass? Was urs better complexity??

Normal max-segmenttree was enough.

you can do NKlogN with just a normal segtree.

Segment tree wasn't needed, you can just stretch the range as you need while using D&Q optimization.

That's what I did, and it passed pretests. A little bit scared; hopefully I pass systests too...

EDIT: Yay.

Same here, I found the bug is the last 10 seconds but do not have enough time, maybe 5 more seconds can save me. Here's my bug: array size 50 -> 51 Silly enough

Did you optimize input/output? I also had the same problem and changing cin/cout to scanf/printf made it pass pretests.

Hmm, I don't have TLE on Div2C, but I do have "Wrong answer on pretest 2". Is that better?

This is my solution; we can see that after (say) m rounds, a & b are in form:

• a = (k1 * k2 * ..ki)^2 * (k_(i+1) * ...*km) = K1^2 * K2 (we can shorten to that)

• Similarly, b = K1 * K2^2

So if we find K1 and K2, then we check if a & b are in those form. This is how I did it:

• a*b = (K1 * K2)^3 <= 1e18 => binary search on [0,1e6] to find K1*K2

• Obtain K1 = a / (K1 * K2).

• Obtain K2 = b / (K1 * K2)

Then check if a == K1*K1*K2 && b == K1*K2*K2

Note that we could only consider prime k are being chosen in each round. Additionally, for {a, b} to be valid, a*b must be a cubic root of a natural number, since a*b = k1^3 * k2^3 ... kn^3.

Therefore, we could consider the prime divisors of the cubic root of a*b, for each prime divisor, count the amount of times that a prime p shows up in a and b. For {a, b} to be valid, all (cnta+cntb) must be divisible for 3 (again, k*k^2 = k^3), and max(cnta, cntb) <= min(cnta, cntb)*2 (as we are considering at most k : k^2).

This gives a complexity of O(sqrt(cubic_root(a*b)) * N) = O(1e3 * N)

First, (a*b)^(1/3) is an integer. Put t=(a*b)^(1/3), and we obtain that the answer is "yes" when and only when it holds both (a%t==0) and (b%t==0). Then is an o(N) method.

However, I got 3 TLE as a result of cin and cout...

You can remove the logN factor. Update costs in O(1) when moving from i->i-1, by checking the next_right occurrence of current value is > mid or not. Use the query to persistent segment tree only for the rightmost valid split point and henceforth use the above trick.

You can see my code for the same.

During contest in last minute,I tried to memoize some part on those values.But my bad it got MLE. Then I lowered the Memory for memoisation.And now O(n*k*logn*logn) passes the TL.

Code:29025279

Maybe a test case like this:

1

1 64

notice that answer is atmost
This is because answer bounded by the number of solutions to x₁ + x₂ + x₃ + ... + x₉ ≤ 18
Now generate all those sequences and then check if it can be somehow squeezed between L and R.