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

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://codeforces.net/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.

A well-known technique from here. Inside the DP, one needs to compute # of distinct numbers on a segment, which is also a well-known problem (can be e.g. solved with persistent segment tree). <offtopic>I don't understand why authors would suggest such a problem, with exactly zero ideas, which is solvable just with trendy standard techniques... </offtopic>

I think you maybe need some data structure to do it. such a segment tree.

But it is not strictly concave/convex so no it can't be solved by ternary search.

No, since neither cw nor ccw is the answer

no ,if ^ ^ then n%4 should be equal to 0

That was the reason why I didn't submit any solution, I couldn't figure out why this is undefined for half an hour, it should have been mentioned in the question.

there won't be any difference . you can solve it with o(1) code . the A problem of the previous contest was 10^18 .

So you can't bruteforce it, but have to use case analysis.

Sadly, I can only use python and of course I get TLE even if my idea is right.

In this case n ≤ 10⁴ would let other, suboptimal algorithms pass. For example what I tried initially involves finding the prime factorization of a & b and checking the exponents of each prime, which might squeeze under the time limit for n = 10⁴ since there are only ~3000 primes up to .

It works, just fixed the array size. I had such stupid mistake last round too, now I am in div2 :(

I implemented this method during the contest, and it turns out that it even runs faster than the intended solution. Probably because long long arithmetics are much slower than int.

The truth is, nobody will care about Python users if that means making problem significantly harder. And making problem easy to Python and Java and far harder for C++ users is not what coordinator should aim at, so your point is invalid. 700000 numbers is far from "massive input" in my opinion and slow input in Python is much less important issue than making problem three times harder for C++ users.

It might or might not be a cheater. Nevertheless, you should report such findings privately to the coordinator.

It's probably because of long execution times on C. However don't be unsatisfiable, they started the system test pretty fast, and 1 h after the contest end it's at 82%, while sometimes they don't even start the system test by 1 hour after the contest.