How did you know? Thanks for the information! You saved my day!

The only breaks I see are in my switch statements.

Me too, first time I have seen. I hope the problems will be interesting.

It is :D

True Evil

please tell me the pretest 5 of problem B!

I got it wrong on pretest 10, don't know why.

D was trivial, chess is harder :)

D problem was okay.

but in all honesty . .

If I ever see anyone playing a game like that , I will make sure they see meet their maker.

LOL

The shape and size of the pizza slices are the same. Therefore no folds are required.

can you explain why answer is draw?

From

aaab

We can get bbbb obviously, so the score is 4.

How can we get a score of 4 from the other ones?

too much dotka for you sir

I didn't solve it completely but I think that segment tree storing divisors in each node + some additional data should work.

My solution kept sets for each possible k, 1 through 100.000. When adding a number u to the array (type 1) I go through all divisors of u, adding that u to each of sets where it qualifies with O(sqrt(n)) complexity (and O(log(n)) for each insert into a set). If the u is already in the array, I don't do anything (not sure if this improves anything but thought it might be a useful optimalisation).

Then, to answer a question for x, k, s, I check if k divides x with the Euclidean algorithm. If not, return -1, if yes, I check if the set for given k is non-empty and if it contains any number not greater than s-x. If so, I can start searching for the optimal solution within this set.

When I know which set I'm using and what is the maximal number from this set I can use, I can search bit-by-bit for the best solution, checking for every j-th bit (beginning with the greatest ones) if there exist a number in the set that satisfies both following conditions: 1) Its first j bits are the same as desired (i.e. all different from the x's bits or the same for those which cannot be different, based on previous steps) 2) It's not greater than s-x This can be done in logarythmical time for each bit.

maybe it can be solved like this:

construct a set which will store array values

since k|gcd(x, v), if this possible then x = p * k and v = q * k,

if x%k! = 0 then output is -1,

else, iterate over values of , find in set if set, maximise zor to find answer

bbbbaa -> bbbbba -> bbbbbc -> bbbbbb

ccccaa -> ccccca -> cccccd -> cccccc

ddddde -> dddddf -> ddddde -> dddddd

so the answer will be "Draw".

I don't get it — isn't the second case supposed to be Kuro?

why is second test case "Draw"?

I got it..

For example, if N = 50000 and M = 50000, then N * M is a rather big number.

fuck all problems I think :|

I think segment means the interval length >=1

because n is long?

No, it is Draw

Kuro can do a

aaaa -> aaab -> aaac -> aaaa

chết chưa bobo suka

Edited

Everone can make aa.

aa->ab->aa->ab->ac->aa

aa->ab->aa->ab->ac->aa

as->aa->as->ab->ac->aa

It's "Draw", right??

you can do 3 steps and the sequence stay same, aa -> ad -> as -> aa

This doesn't work only if you have to do 1 step

1. aa -> ab -> ac -> ad -> ae -> aa

2. aa -> ab -> ac -> ad -> ae -> aa

3. as — > ab -> ac -> ad -> ae -> aa

aa->ab->ac->aa

bb->bc->ba->bb

ca->cc->ca->cc

it's kinda obvious that this is "draw" because "aa" and "bb" are exactly the same strings and should give the same answer, so.

Maybe they wanted to allow n⁴ solutions like mine!!

I would say that pretests in div.2 should cover such obvious (but still easy to miss) cases like n = 0 in task A because, yes, nobody should be able to get +1000 points in a couple of minutes by just typing 0 and clicking "Hack".

But it doesn't feel right to limit the number of hacking attempts because even multiple hacks for the same problem may require you to read and understand various incorrect solutions and come up with unique testcases against each of them (today this was the case for me: I got 5 successful hacking attempts on problem B but I had to use 5 testcases slightly different from each other). These solutions can be relatively large and tough to understand, so I think that such challenges should be rewarded. After all, it's quite important to be able to read somebody else's code, to grasp the logic behind it and to find a counter example if the underlying logic is wrong. If you want to get a bunch of hacks on harder problems, you will have to sacrifice the time that you could have spent solving other problems (with no reward, i.e. successful hacks, guaranteed), so it's about time/risk management as well.

i think CF should have a hacking point for every problems :)

Even people who haven't solved any problem, and hacked as much as 10 codes in problem A are way ahead in standing than those who have solved even a single problem!

I didn't solve it. But my idea : save array as two dimension bool bit[512][512].

1) add u to array: bit[ u >> 9][ u & 511 ] = true;

2) find answer for x, k, s : 2.1) find that 0 <= ID < 512 that , x ^ (ID << 9) maximal. 2.2) for that ID go all 512 elements of ID's sub array.

yes you were. when you are searching the trie, keep in mind that the number you are searching (v) is <= si — xi, and you can verify this relation bitwise

Your thought process is correct. Let's assume we have BSTs instead of tries. Split the BST in two parts: (elements <= s — x) and (elements > s — x). Solve 706D - Vasiliy's Multiset on the first part. This takes time. (Note: Since a trie is essentially equivalent to a BST, I think this can also be done in O(logn) time, but I'm not sure how to implement this.)

You mean 01-trie, right? It's a way, but yes, it can't handle the condition : v + xi <= si

Instead, I used std::set in c++, which is more convenient.

And you can use the lower_bound function to find the minimal value, And you can solve the problem.

If you give every node in 01-trie min[] value, you can also solve the condition.

min[node] means the minimal value in the subtree of the node(if you know what I mean).

If min[node] + xi > si, the subtree of node will not have any v that satisfy the conditions.

Sorry, my English is poor. Hope you'll understand me.

I can't agree more.

the truth！

I suppose next. Find letter with maximum M appearances (using map for example). It's Beauty before. One can change N letters in the ribbon. So one can increase M with N. But sum should be not bigger than ribbon length. Let T = min(M + N, ribbon length). Special case is M = ribbon length and N = 1, here one have to change letter to another and T = M - 1. Finally, compare T for men.

Lets make this the most down voted comment

Could you give more information, please? I didn't notice that.

Although I did the contest badly, overall problems are good. But it's also true there's some mistakes on statements :'(

Thanos : Half of submissions of problem B would cease to exists (snap) just like that.

i agree with u

When you want to hack because you know people will forget about this case...

... but you don't know how to hack.

upvoters : did contest with good score

downvoters : the others

fight of the most subjective voters

The statements weren't fine. Yes, the author's intended solution is to run back and forth between a->b->a. That's what the sample test case description says. Those who understood this way will be judged correct. But there's no problem at all to use a->b->c->a (or a loop longer than 3) under the given description.

aaab->aaac->aaaa

Actually there is one more idea. Someone mentioned above somewhere in comments, I felt it was nice. Limit the number of hacks to 3 per question per person.

So you can start hacking too. No one is forcing you not to hack. Debugging is also an important asset to have

http://codeforces.net/blog/entry/59431?#comment-430573

i thought disabling hacks won't be a solution. in my opinion, limiting hack attempt or covering obvious test is way better.

there are some coder that seriously debugging other ppl code. but what i saw from this contest, most of the people just spamming 0 and click "hack" to get a free 1000 point because no one have started hacking in their room.

you are right for the complexity

return !puts("0"); Your solution returns exit code 1 on n=0.

Don't know why downvotes for my previous comment, but puts returns a non-negative value (on success). In your case puts returns 0 and your code makes return !0, i.e. return 1. Any non-zero exit code from the main process of a solution is treated as a runtime error.

Do you have any test?

I asked about it and the answer was no.