Hi!

Tomorrow, at Nov/25/2018 19:35 (Moscow time) we will host the final round of Mail.Ru Cup 2018. The problems were authored and prepared by Codeforces team: me, Dmitry _kun_ Sayutin, Ildar 300iq Gainullin and Mike MikeMirzayanov Mirzayanov, and also Maxim ne0n25 Mezhcheryakov. Huge thanks to Grigory gritukan Reznikov abd Kamil Errichto Debowski for problems' testing!

This round is the final in the new championship called Mail.Ru Cup, you can learn more about it following the link. The round will be rated for everybody!

After the round we will know who will get the following prizes:

- First place —
**Apple MacBook Air** - Second and third place —
**Apple iPad** - Fourth, fifth, sixth places —
**Samsung Gear S3** - Traditionally, the top
**100**championship participants will get cool**T-shirts**!

In each round, top 100 participants get prize points according to the table. The championship's result of a participant is the sum of the two largest results he gets on the three rounds. The results of the two first rounds are published here. In case of ties in the top six places, they will be broken by the sum of in-round scores in the corresponding (best for the participant) two rounds.

There will be eight problems and two and a half hours to solve them.

Good luck!

P. S. MikeMirzayanov invites everybody to the official Codeforces channel in Telegram: t.me/codeforces_official.

The round has finished, thanks everybody, hope you liked the problems!

Congratolations to the winners of the third round of Mail.Ru Cup 2018:

The results of the Cup will be announced shortly.

The editorial is here.

I hope there isn't much controversy like today's contest.

I want to become Cyan :p

Who cares

Ron, Hermione and probably all of Harry's fellas.

xD

There seems to be an unusually large amount of spam in the comments.

It seems that's right.

It seems you're imitating me >:(

Can someone help me figure out what is the motive behind the telegram channel? Do we have permission to write our comments there or we can just read?

I think it's for admins to give announcements in case website crashes or something.

Hello MikeMirzayanov why my comment in this post is removed ?

You have replied to a comment which got a lot of downvotes; such comments are hidden as well as replies to it

Two thanks to MikeMirzayanov?? Hope this round goes well. Thanks MikeMirzayanov

Don't you want to post anything on that channel??? At least announcing the contests...

Is it rated? :D

definitely yes.

We have all guys from top-10 registered for the contest except only tourist and OO0OOO00O0OOO0O00OOO0OO. Will they join and make competition really high and interesting?

die

like right now

tourist hasnt registered yet! i think mnbvmar going to be the first in rating

Radewoosh vs V--o_o--V vs scott_wu

hello i live in a very rural part of yugoslavia and i would like to know if this contest is rated for me too. thank you

No, this contest isn't rated for users from rural parts of Yugoslavia.

okk thanks for reply

lol

No contest till 3 weeks! why?

This is codeforces, wait for some days then you can see the list of the contests.

so please be with codeforces.

Contest in 3 days. Now that is CodeForces :)

You should fix the bug on the m1.codeforces.com (and m2,m3) platforms.

I was able to lock problem D and then resubmit it. My second submission must of course be skipped, and the same should happen to all contestants that took advantage of that bug.

Is this the reason why so many submissions on D or is it a very standard problem????

D was very basic graph/tree problem. So i dont think that is the reason.

What is the hack for D?

Seems like

n= 1.My code fails on this case, nobody hacked me :(

RIP my rating.

What is the answer?

It should be 1.

But my code doesn't even output anything lol.

UH OH

In problem D hack attempt: input: n = 1, giving status: invalid_input, I think it is a valid case 1 <= N <= 100000.

This happened to me too, but I fixed it by inputting an empty line after the 1.

hack validation script might not handling the empty line.

Well, it seemed to handle my empty line with no problems so I think the script can :)

Holy smoke.. if there is n = 1 in systests then FML

How to solve B ?

If you can count number of numbers with remainder i, it's easy to calculate number of x*x % m = i.

We just have to store the values of (i*i)%m for i=1 to m, the values repeat thereafter.So maintain an array which will store number of values for a particular mod value(0 to m-1). a[(i*i)%m]+=(n/m) for i=1 to m and then compute for remaining values(i=(n/m)*m+1 to n). Then,loop through all values of mod such that mod value k can pair with mod value (m-k).

How to solve D ?

For every node, count the number of leafs in its subtree. Store this number in an array, let's call it numleafs. Then sort numleafs in non-decreasing order (smallest element first). For every k from 1 to n, the answer is numleafs[k-1].

You can count the number of leafs in a node's subtree with a "simple" dfs.

thank you.

If we knew the number of elements in range [1

^{2}, 2^{2}, ...,n^{2}] that are divisible bymwith remainderi(where, 0 < =i<m), we can esily count the result, that is, the number of pairs of squares elements that are their sum is divisible bym(without remainder).To know that, we should know:

1) how to find the number of elements in range [1, 2, ...,

n] that are divisible bymwith remainderi(where, 0 < =i<m).2) how to transform from [1, 2, ...,

n] to [1^{2}, 2^{2}, ...,n^{2}].This is my submission for more details.

Wth is pretest 5 in B

Can anyone provide test 7 for E? Got runtime error :(

I got RTE on 5 because didn't use long long for some multiplications, maybe that's your case?

Yes, yes already got it. Is int overflow considered runtime error?

Yeah, at least in my case that was the error.

Cool, anyway thank for help.

Big strings' sizes i think. My solution failed because of overflow. Used long long and it passed.

I can't wait till the system testing finishes. Has anybody an idea what is pretest 17 of problem E??

I think anti hash.. I changed my hash function and it passed for me..

I tried hashing with 2 bases (29 and 31) mod 2^64 but still got WA :(

You should never hash with 2^64!

hashing mod 2^64 can be made to fail. I did the same thing. U need to change it to something not of form 2^n

I did not know about that. So I guess hashing with 2 or 3 big primes is the only option.

I dont think hashing with primes is necessary. non-primes should work too.

if you pick your primes from here then you won't get WA because of anti hsash

my hash solution of MOD 2^64 failed test 17 too,maybe test 17 is a speciallly structured test case

Daily Reminder:

Never hash with 2^64, Never!

I guess today's contest will serve as a good reminder for me.

Exactly, this is a test against 2

^{64}hashes.Of course we are not retarded enough to generate anti-hash tests to default modulos/

p's, but hashes against 2^{64}is a known vulnerability with easy antitest.What's pretest 2 in F?

Probably some random test case, but looks like I can only pass by switching to using binary search / ternary search instead of analytic solutions.

I switched to ternary search as well but no luck.

My solution was to find with DP the minimum of achievable for a fixed

kand total number of pointsP. Then we can minimize and check whether it fits under time.I have the same one! And I don't have any reasons why my solution doesn't work.

I passed pretest 2 when realized that t must be non-negative. So I took t = 0 if f(t) is minimum at negative t (but I got wa56 then and I have to clue about it)

Your INF is too small

Oh, shit! Thanks! I was so close to achieving red color and a T-shirt...

Oh, i’ve just skipped if t < 0

I did the same thing and failed to the same test :(

This is one thing I hate about math problems: The idea is often trivial but in the implementation you have to do so much math that it's inevitable you'll get bug :/

EDIT: my bugs were the following:

I calculated the optimal x (time spent training) as x = max((ld)0, -b/2*a), when it should be (2*a)

Knapsack looped from bottom to top, allowing the same item to be used twice

... how this even passed the first test, I'm not sure

Okay I had a major fuck-up which didn't trigger samples (never does): applied rearrangement inequality in reverse direction. Sorting the array in reverse direction worked.

I think the problem with analytic solutions might be that the value of

twhich minimizes the function comes to be negative. That seems to be the only thing I missed in my solution.EDIT : Yes, that was the only fault in my solution.

Look at mine: 46228777

I also lost about 50 minutes due to the same issue , but I've no idea WTH is wrong with it. Does anyone knows why this happens?

What did you change?

I changed the O(1) formula to find the maximum value in a concave function to a O(log(T)) ternary search and passed the pretests.

By the way if anyone is interested , here's a counter test :

1

4

1.000 11.112

4 9

12 3

1 3

1 5

I had that as well but it was because the formula gave me a negative value for

t. It worked when I maxed it with 0.Please guide for B and D

For D: count the number of leaves in every subtree, then sort.

This was my first time solving D but I failed to solve B >:(

Can someone please tel me how to solve B?

How to solve D?

Count the number of leaves in every subtree then sort. Use this guide https://www.geeksforgeeks.org/calculate-number-nodes-subtrees-using-dfs/ but instead of count1[s] = 1, only set it to 1 if it has no neighbors other than its parent.

Thank you :)

((i*i) + (j*j))%k can be written as ((i%k*i%k)%k + (j%k*j%k)%k)%k. Keep count of number of i's such that (i%k) = j for all j from 0 to (k-1). Similarly using this count array, construct (i*i)%k mapping to j, let this be arr. Now for every i,j such that 0<=i<k and 0<=j<k if (i*i + j*j)%k == 0 add the value of arr[i]*arr[j].

Thanks! Simplifying the problem using modular arithmetic was really smart.

Instead of thinking of the coordinates as numbers from 1 to

n, think of it as several consecutive periods of numbers from 1 tom.Traverse an integer

ifrom 1 tom. With each value, calculate two value:cnt: number of periods that containsiwithin range [1,n].r: the remainder ofi^{2}when divided bym.Make an array

RemCnt[], and with eachi, addcnttoRemCnt[r].After this, we can safely do a

O(m^{2}) traverse to find out the number of pairs (i,j) such asi+jis divisible bym.Thanks I understand how to do it now :)

Problem Bwas a fantastic problem.Hint please

Hint1:

(I^2 + J^2) = 0 (mod m)

I^2 = -J^2 ( mod m)

Hint2ঃ For a given n, (I^2 + J^2) % m will create a cycle. So find the cycle and you will find the answer.

I solve it very nicely.

Very good problem.

True that. But I felt it was harder than both C and D.

I can not solve C and D but solved B.

Actually it was harder. But a creative one.

In problem D hack attempt: input: n = 1, giving status: invalid_input, I think it is a valid case 1 <= N <= 100000 .

What's output for n=1?

I think the output should be: 1 (since root node == leaf node).

Probably you forgot to print an empty line, remember that the array of parents must be printed in a different line.

whats the test case 7 in C ??

Tfw you're worried AF about system tests in E because you used a single and standard hash :(

Haha, May the force be with us all :P

No reason to be afraid of system tests if you survived hacking phase, I didn't have that luck ;_;

I'm using an insanely weird modular number, yet the "single" property still makes me worried as hell, especially seeing Swistakk got hacked...

What I've usedMod = 2100003221LL;

Can you explain your solution for E?

Loop length of the string replacing zeroes, calculate length of string replacing ones, and check if this configuration works with hashes. Complexity is O(n log n) since you do n + n/2 + ... + n/n = O(n log n) work.

Guys, what is the tricky part in problem C, i get wrong answer on test 7. :(

Probably the query you are accidentally printing is the value of the player itself and not the index. I got a WA on test case 7 for that one.

I think for optimal solution you have to take special pairs of heroes first. I also got WA on test 7..... I fix this and pretest passed.

I think you may be right.Thank you for answer.

Simply you were getting the strategy wrong.

If you have a turn and not being obliged by anything, you can choose one pair of special heroes, pick the stronger one, therefore forcing your opponent to pick the weak one, and give you back your turn again. It's a clear win-win, so whenever you have a chance to freely choose heroes, repeat that process until there's no special heroes' pairs left unchosen.

After that being done, we return to the normal, maximum-prioritized strategy.

I understand now Akikaze thank you very much.

In problem D,Sample test 2

At k = 4 why is the node 3 happy? considering that subtree of node 3 consists of (3,4,5) we only colored (4,5) what about 3(it can't be colored) but shouldn't be counted as colored?

A happy junction is such a junction t that all light bulbs in the subtree of t have different colors.

We color leaves only.

"all the lights" so the nodes with no lights are ignored, every junction is concerned only with the "lights" in its subtree.

what is the hack for D ?

I think hack for D is

n = 1the answer ?

If

n = 1answer is1fast system testing running...

why can't you fcking include n = 1 in pretests?

Because it is corner case and it should be quite obvious to check before submitting solution. So if you didn't that — it's your fcking problem.

If it's my problem then don't fcking reply me

Yeah I feel bad for not trying it but at least I learned a valuable lesson.

Depending on how you implemented it, n=1 is not even a corner case; it can be handled by the general case. If you consider the sole node in n=1 to be a leaf and begin processing nodes at the leaves, you shouldn't run into an error with n=1, and you don't need a special case for it either.

This has to be the

Fastest System Testever.Thanks for fast system testing!

codeforces system testing rocks...

fastest ever.

No n = 1 in pretests for D? Are you kidding me!?!?!?!?!

Open it for practice please Edit: Its open now, wonder why the delay.

Was that the fastest System testing in Codeforces history :D

How long after the contest can we submit solutions again?mnbvmar gonna win

Apple MacBook Air.Very bad problemset for

div.2. >5k registered users, >3k users participated (made submissions), about 1.3k participants solvedA. And only 1.7k solved more than A (or at least B or C). So if you were participant of div.2 level, you probably read problems' A statement, almost immediately submitted an answer, and then you could leave contest, and your place will be determined only by comparing submission speed (and speed of overcoming of starting 502 Bad gateway) of problem A comparing with thousand other same level participants. I want to emphasize that there were no announcement about difficulty of the problemset, only it was said that this round is for all (so it means for div.1 + div.2 + div.3). And there were "АЖ" 8 problems. 7 of them were for 2/3 participants. In my opinion, better were to offer for all participants: about 2 problems of div.3 level, about 2 problems of div.2 B-C level, and about 4 more difficult problems.The only thing you should do is to stop complaining and improve yourself, and you will find out that pB is trivial enough.

rsFalse has a point here. B, C, D felt of the same difficulty, which isn't good already. For div. 1 guys they all felt easy, and for div. 2 guys they were all medium. Making B easier and D harder would've been appreciated by more people as then B would've been solvable by more div. 2 and div. 3 people, while D would've been more interesting for div. 1 participants. Problems of the same difficulty really create issues, but this is difficult to avoid when preparing a contest.

How to solve B ??

For a given n and m you have to count how many i, j are there where (i^2 + j^2) = 0 (mod m). You can easily see that i^2 mod m and j^2 mod m ( i, j from 1,..., n) forms a cycle.So, ans will be equal cnt[i^2 mod m] * cnt[m — ( i^2 mod m)]. Check my submission 46215431

By the way, why is the next competition three weeks away?

Maybe they are just taking care of new problems/competitions before posting them.

congratulation to yashChandnani to become a red coder.

such an inspiring rating graph.

Is there a reason for the tight time limit on problem H of 1 second, when n is 300000 and the intended solution is O(n sqrt(n))? Were there any unintended solutions you wanted to keep out with this time limit?

EDIT: sorry, I referred to the wrong problem

? Time Limit is 3sec, n is 1e6 and intended solution is n.

Did you mean H?

46235526 Problem A TEST 10. My answer is correct and the test result is incorrect. How can I pass the test?

You answer is incorrect since you have 64.

Notice the first numbers from 2nd line and so on indicate the number of stops in that line and it is not a stop itself.

I misunderstood that part. Thanks for the correction!

i don't care