Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### JATC's blog

By JATC, history, 5 weeks ago, ,

Hi everyone. I'm glad to announce that the Codeforces Round #520 (Div. 2) will be held on 14.11.2018 18:35 (Московское время).

The round will be rated for Div 2 participants (whose ratings are lower than 2100). However, all the other participants can compete as well, without worrying about ratings being changed.

You will be given 2 hours to solve 6 problems. It's better to read all the problems. The scoring distribution will be announced soon before the contest starts.

All the problems were prepared by myself, with some help from my friend GiraffeCoder. I want to thank _kun_ for coordinating me in preparing the problems, gritukan, isaf27, demon1999 and Arpa for testing my solutions. I also want to thank csacademy for their graph editor tool. You can check it out at this link.

This is the first round I propose. I put a lot of work into it so I hope that you will enjoy it (smiley face).

Wish you do your best and get a high rating!

Update 1: If you want to discuss about the problems after the contest, here is the link to the CP Community on Discord. Please make sure that you don't give the solutions to other participants during the contest.

Update 2: The score distribution will be the standard one: 500 1000 1500 2000 2500 3000.

Update 3: Congrats to the winner

Official participants:

Unofficial participants:

Tutorial UPDATED

•
• +287
•

 » 5 weeks ago, # | ← Rev. 4 →   -75 You forgot to thank MikeMirzayanov!!! for awesome codeforces and polygon platform.
 » 5 weeks ago, # |   +51 Why gritukan became blue?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +22 Hi 300iq — 17iq + 2000iq — 200iq * 10iq
•  » » 5 weeks ago, # ^ |   +81 I think he was faking his red all this time.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +47 Because when they make post he was blue, but now he is cyan.
•  » » 5 weeks ago, # ^ |   +4 Maybe he let someone rent his account.
•  » » 5 weeks ago, # ^ |   +21 Because he wants to get vertical rating graph. Positive or negative is just direction, we only care magnitude.
•  » » » 5 weeks ago, # ^ |   +16 He will definitely break this (Maximum rating change in CF history) record.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +11 I asked his friends and he wants his team on the list in front of the icpc with nicknames and ratings to look funny. A team of two red and blue.
 » 5 weeks ago, # |   -54 fuckme please.
 » 5 weeks ago, # |   -31 I think you should hope that none of your problems or your checkers would have had mistake instead.
•  » » 5 weeks ago, # ^ |   -20 -8 your favorite number amiterite?
 » 5 weeks ago, # |   +43 Happy to see another round from Vietnamese.
•  » » 5 weeks ago, # ^ |   -21 a vừa tổ chức thi freecontest lại còn thi bên này nữa lun hả
 » 5 weeks ago, # | ← Rev. 2 →   +24 In China,520 means "I love you." I prefer high rating :)
•  » » 5 weeks ago, # ^ |   0 But my girlfriend and I just broke up,I am so sad that I don't know how to do it.
•  » » » 5 weeks ago, # ^ |   +4 Sorry about hearing that bad news. 振作起来，哥们。
 » 5 weeks ago, # |   -33 Hi warriors,I'm back;
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +4 Oh! So the prophecy was true!
 » 5 weeks ago, # |   -12 Why gritukan became blue?
•  » » 5 weeks ago, # ^ |   -19 Because at the moment they post this he was blue.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +16 I asked his friends and he wants his team on the list in front of the icpc with nicknames and ratings to look funny. A team of two red and blue.
 » 5 weeks ago, # |   -22 Isnt it unrated??
•  » » 5 weeks ago, # ^ |   -22 It was at this moment that i know i fucked up
 » 5 weeks ago, # |   0 I m not able to register for the contest ?
 » 5 weeks ago, # | ← Rev. 2 →   0 Whenever i try to submit it says you should be registered, although i registered for it yesterday itself, Please help
 » 5 weeks ago, # |   +25 Can someone get rid of fake accounts in places 3-8. It's obviously just one or two people modifying their codes and submitting again. JATC
•  » » 5 weeks ago, # ^ |   +1 now he is even first place, lol
•  » » 5 weeks ago, # ^ |   +1 If there is any cheating those accounts will be disqualified probably :)
•  » » » 5 weeks ago, # ^ |   0 I think there's some mistake happening here. Only 3 of those are cheaters, but coffee_chicken is not, but they all seem to be banned simultaneously. Is there any way to fix this?
•  » » » » 5 weeks ago, # ^ |   0 I'm not sure since it's the decision of the admins.
•  » » 5 weeks ago, # ^ |   +7 They all got banned. Thanks, admins!
 » 5 weeks ago, # | ← Rev. 2 →   -64
 » 5 weeks ago, # |   +6 What's wrong with pretest 9 of Problem B? Anyone with a clue...
•  » » 5 weeks ago, # ^ |   +3 Probably something like 93184 which is 1024*7*13. You may be having overflow issues.
 » 5 weeks ago, # | ← Rev. 2 →   0 How to solve E????? I tried Mo's algorithm + LCA the left/rightmost but got TLE every single time. I think the set is the main problem...
•  » » 5 weeks ago, # ^ |   +13 I think you just need to have the lca of (i and i+1) and (i and i+2) pre-calculated for all i and then do with segment tree.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Oh, it was that simple!!!!! LOL!!!!!! Thanks.
•  » » » » 5 weeks ago, # ^ |   0 I couldn't implement it as I forgot to make a simple observation in D but I think that should pass.
•  » » 5 weeks ago, # ^ |   +11 My solution is like this: say that dfn[x] represent the order of vertex v when you do dfs, then the LCA of a set of vertices is just the LCA of the vertices with the lowest dfn and the highest dfn, so we can use a segment tree to maintain the vertex with the lowest dfn, second lowest dfn, highest dfn and second highest dfn, to answer a query, just do case analysis (3 cases here, erase the vertex with the lowest dfn, erase the vertex with the highest dfn, or neither). The solution is . You can do the LCA part using whatever technique, both binary lifting and euler sequence+RMQ would do.
 » 5 weeks ago, # |   0 What hacks are there? (for any problem)
•  » » 5 weeks ago, # ^ |   +3 Hacks for B:18 (ans=6 2)144 (ans=6 3)
•  » » » 5 weeks ago, # ^ |   0 What is case 9? Hack is too far away
•  » » » » 5 weeks ago, # ^ |   0 Try this:24 (ans=6 3)
 » 5 weeks ago, # |   +16 Does this work for E? Find maximal L that lca(l, L) != lca(l, r) Find minimal R that lca(R, r) != lca(l, r) If L + 1 == R — 1 and lca(lca(l, L), lca(R, r)) != lca(l, r) answer is L + 1.
•  » » 5 weeks ago, # ^ |   0 Is this correct? I tried implementing the same but got WA on 6th test. https://ideone.com/kr0ZCY
 » 5 weeks ago, # |   +13 D is too easy, innit? Or i will drop on full tests...
 » 5 weeks ago, # |   0 Just 10 more seconds :(
 » 5 weeks ago, # | ← Rev. 2 →   -16 Is this not the correct formula for C?(2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*noOfZerosInLtoR)
•  » » 5 weeks ago, # ^ |   0 nope dude, try this test case 4 1 0001 1 4
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Got my mistake. Thank you!! Instead of noOfZerosInLtoR it will be (2^noOfZerosInLtoR)-1.
•  » » 5 weeks ago, # ^ |   +10 I first thought so and got several WAs.must be aware that after eatings ones, which were initially zeroes now have some values which even gets larger and larger eating those.
•  » » 5 weeks ago, # ^ |   0 (2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*(2^noOfzerosInLtoR-1))
•  » » 5 weeks ago, # ^ |   +23 It's just 2^(num zeroes + num ones) - 2^(num zeroes). Other formulas are looking kind of complicated.
•  » » » 5 weeks ago, # ^ |   0 How we came across this formula?
 » 5 weeks ago, # |   +6 All naruto characters are in the standings www
 » 5 weeks ago, # |   +8 What is solution for D?
•  » » 5 weeks ago, # ^ |   +3 My solution was simply to find all factors of every number from 2 to n. Now for each number from 2 to n, sum up all factors except 1 and the number itself. Now add all of these sums and multiply by 4 to get the answer.
•  » » 5 weeks ago, # ^ |   +21 Build the graph where there's an edge between a and b with weight if you can go from one to the other. Whenever you have an edge between a and b, you also have one from a to  - b, so the degree of each vertex is even, and thus the graph is eulerian, and you can traverse every edge. So it suffices to find the sum of all of the edges, which is easy.
•  » » » 5 weeks ago, # ^ |   0 that was a great observation.
•  » » 5 weeks ago, # ^ |   +3 Suppose you have an integer i.You can always make a cycle of size 4 for every k which is less than n and divisible by i.For any k which is divisible by i,just add 4 * (k/i) to your ans.Suppose that i has p multiples <=n.So for i,add 4 * ((p * (p+1))/2 — 1) to your ans.(-1 because i can not form a cycle to itself).
 » 5 weeks ago, # |   0 Does this work for E? I did dfs to find time in for every node. Then for each query, used seg tree to find node with minimum and maximum time, say mini and maxi. Then I took a node from l to r which is neither the max nor the min time, say x. I found lca(mini, x) and lca(maxi, x) and reported the one with maximum level and removed the other one.
 » 5 weeks ago, # |   0 RIP my rate :) anyone knows B pretest 3?
•  » » 5 weeks ago, # ^ |   0 I think it's 10^6
•  » » » 5 weeks ago, # ^ |   0 meh it was a silly mistake I knew the solution idea but I done it terribly :( I should have just checked if the last sqrt equals prime factors multiplied to know if we should multiply or not
•  » » 5 weeks ago, # ^ |   0 It's 256 or 64 I guess..
 » 5 weeks ago, # |   +13 Problem F is simply this but with more cases.
•  » » 5 weeks ago, # ^ |   +31 I think the factor of the "semi-important" cities makes the problem significantly more interesting and hard.
 » 5 weeks ago, # |   0 anyone knows problem B test 32?
•  » » 5 weeks ago, # ^ |   0 18
 » 5 weeks ago, # |   +16 In problem A, it would have been better if constraint for n was upto 1000, because for n = 1000 answer would be 1000. Some people might have missed this test case. I have also printed 999 in my current solution.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 exactly. I've got at least 3+ people in my room who've made this mistake. What was the reason for n being 100, I don't understand.
•  » » » 5 weeks ago, # ^ |   +8 Well, you can't call it a "mistake" if it doesn't lead to an incorrect solution. I knew this, but since n < 100, I didn't bother putting that case.
•  » » » » 5 weeks ago, # ^ |   0 Calling it a "mistake" was wrong actually. But n = 100 made it easier I think
•  » » 5 weeks ago, # ^ |   0 Really? What a disgrace.
•  » » 5 weeks ago, # ^ |   +5 However this allows to handle less cases in the solutions, which is also not very bad
 » 5 weeks ago, # | ← Rev. 2 →   0 How is my system test B(submitted at ~45mins) still running on test 50? while many other people's submissions finished running. https://codeforces.com/contest/1062/submission/45725683
•  » » 5 weeks ago, # ^ |   0 ACCEPTED XD
 » 5 weeks ago, # |   0 Pretests for A were very weak.
•  » » 5 weeks ago, # ^ |   0 I'm sorry this happens but it's seem too hard to cover all the cases in just a few tests. Too much tests and the server will die.
 » 5 weeks ago, # | ← Rev. 2 →   +90 The problem A pretests are one of the top-10 pranks that went too far.
 » 5 weeks ago, # |   +1 I was wondering in Problem E if i wanted to count the number of nodes instead of just printing one what would the solution be ?
•  » » 5 weeks ago, # ^ |   0 I guess there can be only two nodes (at max) the ones with min start and max finish (dfs) times.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 the case of x nodes being direct children to LCA or choosing a subtree the answer will be x not sure if this is just a corner case thou.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 If x nodes are children to LCA, with x > 2, then u can never increase the answer right? by just performing one remove operation. So the count is zero.
•  » » » » » 5 weeks ago, # ^ |   0 i think he asks for the nodes when removed will result in the best answer so i think the answer will be all of them however, my question is does handling this assures that the answer for all other cases is <= 2.
•  » » » » » 5 weeks ago, # ^ |   0 I would consider the count to be x, since you can remove any of the children and it will be true that the "level of the project manager required is as large as possible."
 » 5 weeks ago, # |   +16 it was hard for me. But in any case, thanks for the round and interesting problems.
 » 5 weeks ago, # |   +5 It was really a prank with the problem "A Prank". Missed the last line :'(. Yet didn't get AC.
 » 5 weeks ago, # | ← Rev. 2 →   0 deleted
 » 5 weeks ago, # | ← Rev. 2 →   0 How can the fastest solution in Python be 171 ms for even shortest test (e.g. problem A. tc #1)? Status order by consumed time (choose language, e.g. Python 2, and status: acc). Seems it doesn't depend on which problem but all Pythons (2, 3, pypy-2-3) have >100ms to pass any test case. Strange.
•  » » 5 weeks ago, # ^ |   0 Maybe it is to load the runtime environment, just like how java always eats 100ms start time.
•  » » » 5 weeks ago, # ^ |   0 But its first time I see ~170 ms (almost 1/6 of TL). If you look at much earlier contests this minimal time was usually faster, e.g. Contest #839
 » 5 weeks ago, # |   -13 I get 247 rated! Thank you!!!!
 » 5 weeks ago, # |   +10 Take a glance at AProcess to calculate sum of (each continue-element segment — 2) lengthsWrong answer at test 7Take one hour to realize answer is the maximum length Ye.
•  » » 5 weeks ago, # ^ |   +8 same here :(
•  » » 5 weeks ago, # ^ |   0 I realized that after the contest is finished XD
 » 5 weeks ago, # |   -6 Codefores is the best!!!
 » 5 weeks ago, # |   0 It seems that hatuanlhpk97 and trung289123 cheated during the contest. The codes are basicly the same but with random stuff added to hide it.
•  » » 5 weeks ago, # ^ |   0 The common parts of code seem to originate from http://e-maxx.ru, which is allowed.
•  » » » 5 weeks ago, # ^ |   0 E-maxx has implementations for standard algorithms, not specific problems. It is clear that all the solutions are identical. And why are the solutions filled with var-=a, var+=a, then?
•  » » » » 5 weeks ago, # ^ |   0 Cheaters should be punished. I am still struggling to become a pupil :( and here these guys are cheating.
 » 5 weeks ago, # |   0 It is written that Tutorial is UPDATED. where is the editorial link?
•  » » 5 weeks ago, # ^ |   0
•  » » » 5 weeks ago, # ^ |   0 Thanks