Привет!
Уже завтра, в 25.11.2018 19:35 (Московское время) состоится заключительный раунд Mail.Ru Cup 2018. Задачи были придуманы и подготовлены командой Codeforces — мной, Дмитрием cdkrot Саютиным, Ильдаром 300iq Гайнуллиным и Михаилом MikeMirzayanov Мирзаяновым, а также Максимом Neon Мещеряковым. Спасибо Григорию vintage_Vlad_Makeev Резникову и Kamil Errichto Debowski за тестирование задач!
Этот раунд — заключительный в новом соревновании Mail.Ru Cup, подробнее о котором можно прочитать по ссылке. Раунд будет рейтинговый для всех!
По итогам этого раунда будет ясно, кому достанутся ценные призы:
- Первое место — Apple MacBook Air
- Второе и третье место — Apple iPad
- Четвертое, пятое, шестое места — Samsung Gear S3
- Традиционно топ-100 участников чемпионата получат классные футболки!
В каждом раунде лучшим 100 участникам начисляются призовые очки в соответствии с таблицей. Итоговый результат участия в чемпионате — сумма двух максимальных результатов из трех раундов. Результаты двух уже прошедших раундов опубликованы здесь. В случае равенства турнирных баллов среди первых шести мест будет учитываться сумма внутрираундовых очков, полученная в соответствующих (лучших для участника) двух раундах.
Вам будут предложены восемь задач и два с половиной часа на их решение.
Удачи!
P. S. MikeMirzayanov приглашает всех в официальный канал Codeforces в Telegram: t.me/codeforces_official.
Раунд завершен, спасибо всем за участие, надеюсь, вам понравились задачи!
Поздравляем победителей третьего раунда Mail.Ru Cup 2018:
Общие результаты чемпионата будут опубликованы в ближайшее время.
Разбор раунда тут.
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
Число 998244353 простое?
Yes
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 EvenImage. Will they join and make competition really high and interesting?
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.
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.
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.
How to solve B?
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.
If we knew the number of elements in range [12, 22, ..., n2] that are divisible by m with remainder i (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 by m (without remainder).
To know that, we should know:
1) how to find the number of elements in range [1, 2, ..., n] that are divisible by m with remainder i (where, 0 < = i < m).
2) how to transform from [1, 2, ..., n] to [12, 22, ..., n2].
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 264 hashes.
Of course we are not retarded enough to generate anti-hash tests to default modulos/p's, but hashes against 264 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 k and total number of points P. 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 t which 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 to m.
Traverse an integer i from 1 to m. With each value, calculate two value:
Make an array RemCnt[], and with each i, add cnt to RemCnt[r].
After this, we can safely do a O(m2) traverse to find out the number of pairs (i, j) such as i + j is divisible by m.
Thanks I understand how to do it now :)
Problem B was 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.
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...
Mod = 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 = 1
the answer ?
If n = 1 answer is 1
fast system testing running...
Задача E была несколько лет назад на SN*S(а значит Снарк взял её из еще более раннего контеста).
Печально, если так :/
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 Test ever.
Thanks for fast system testing!
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
Open it for practice please Edit: Its open now, wonder why the delay.
How long after the contest is over can we submit our solutions again?
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 solved A. 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.