### platypus179's blog

By platypus179, history, 5 years ago, translation,

Ladies and Gentlemen!

The Codeforces round #359 for both divisions will happen on 23 June at 7:35 PM MSK. We have been choosing and solving problems for a long time and we hope that they will seem quite interesting.

All of the problems were created under guidance of Endagorion (Mikhail Tikhomirov) by Moscow high school graduates: cdkrot (Dmitry Sayutin), ch_egor (Egor Chunaev), themikemikovi4 (Mikhail Sorokin) and me. It is our second Codeforces Div.1 + Div.2 round.

Thanks to coordinator GlebsHP (Gleb Evstropov) for help with preparing problems and to MikeMirzayanov (Mikhail Mirzayanov) for excellent systems Polygon and Codeforces. Also, the round is possible only because of Endagorion's help.

Participants will be given five problems in both divisions. The scoring distribution will be announced later.

Good luck to all!

UPD: All statements are based on the fairy tale "The Snow Queen" by H. C. Andersen.

UPD2: The scoring distribution:

Div. 1: 500-1250-1250-2000-2500

Div. 2: 500-1000-1500-2250-2250

UPD3: Congratulations to the winners!

Div. 1:

Div. 2:

UPD4:

Cheating detection may affect the ratings a little.

UPD5:

The editorial can be found here.

• +461

 » 5 years ago, # | ← Rev. 2 →   +8 Before 3 days , that's too early ! thanks at all
•  » » 5 years ago, # ^ |   -55 Road to 1720+
• »
»
5 years ago, # ^ |
-31

### Road to 1800+

•  » » 5 years ago, # ^ |   -52 EZ PZ +1720
•  » » 5 years ago, # ^ |   -27 HI EVERYBODY!!!!!!!!!! try pressing the the Caps Lock key O THANKS!!! ITS SO MUCH EASIER TO WRITE NOW!!!!!!! fak me
•  » » » 5 years ago, # ^ |   +9 What's your meaning?
•  » » » 5 years ago, # ^ |   +20 Feel like you are drunk.
•  » » » » 5 years ago, # ^ |   -10 No, it is a joke.Just the high rating can understand it.
•  » » » » » 5 years ago, # ^ |   +26 Okay then. Wish I will understand it someday.
•  » » » » » » 5 years ago, # ^ |   -14 ROAD TO FUCKING +1720
•  » » » » » » » 5 years ago, # ^ |   +24 don't think you can fuck a number
•  » » » » » » » » 5 years ago, # ^ |   +21 I see you are humorist.
 » 5 years ago, # |   -41 Good luck for everybody !
 » 5 years ago, # |   -58 Hoping to step up my game in this contest. :D
 » 5 years ago, # |   +59 This will be my first Div1 contest! Hope I don't do anything silly!
•  » » 5 years ago, # ^ |   +13 It's strange, I also hope I don't do anything silly, but it's not my first div 1 round :-? wonderful! isn't it?!
•  » » » 5 years ago, # ^ |   +12 Your commitment counts more than your performance. Looking at your history you definitely have commitment and I have the utmost respect for that!
 » 5 years ago, # |   -21 My rating has been dropping since forever. Hope i do not do anything stupid and finally increase my rating. :)
•  » » 5 years ago, # ^ |   +27 and your contribution.
 » 5 years ago, # |   +346
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 EDIT: ignore my reply, I mistook the post for something else, not a big dealThis glitch has been around for as long as I can remember, hope it gets a quick fix
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Which glitch are you talking about? If I am not mistaken, I don't see any glitch there.
•  » » » » 5 years ago, # ^ |   0 Sorry my bad, I thought the entries were doubled
 » 5 years ago, # |   -25 Hope Everyone Gets a new level up color , me also :)
 » 5 years ago, # |   -34 looking forward to do 3/5. :D
 » 5 years ago, # |   +32 Its just the right time, the contest is just being held on the day without Euro
•  » » 5 years ago, # ^ | ← Rev. 3 →   -36 Lucky you :D , it's the contrary here, the timing couldn't be worse for any rated round as I have to do stuff in the middle having only 1.5 hours at best :(
 » 5 years ago, # |   -15 Your last round was a round for hackers, not for coders, I hope we won't see the same tomorrow...
•  » » 5 years ago, # ^ | ← Rev. 6 →   +58 Actually, last time we just didn't put the overflow test in Div2A pretests.Of course, in some problems we will exclude some special cases from pretests. The process of dividing tests on pretests and system tests has many functions that are not related to the testing speed. For example, some people may learn to test their code after they get hacked.And of course, we try to make the round interesting to solve. We didn't expect to have so much hacks on integer overflow. Hope this particular mistake is an exception rather then the rule.
•  » » 5 years ago, # ^ |   +26 So as you wish, this round there were no hacks (at least in Div.1)
•  » » » 5 years ago, # ^ |   +9 And also in Div.2 :V
 » 5 years ago, # |   +19 This is one of the reasons that make codeforces a special site.. Its attractive way of announcements. Thanks platypus179
 » 5 years ago, # |   -42 it's summer and the contest labeled with " The Snow Queen " , Nice name in wrong time
•  » » 5 years ago, # ^ |   +65 Im quite sure that Snow Queen will ask us for a help because of such a nice(not for her) weather.
•  » » 5 years ago, # ^ |   +37 It's summer only in the Northern Hemisphere.
 » 5 years ago, # |   -21 platypus179 Said, "the round is possible only because of Endagorion's help ". And I love Endagorion's Problems.
 » 5 years ago, # |   -40 What's up with so many downvotes on simple good luck wishes or hopeful comments? :O
•  » » 5 years ago, # ^ |   0 because these comments are common and annoying.
 » 5 years ago, # |   +2 The only time I've got rating rise is when I'm in a foul or depressed mood. This isn't good I'm afraid
 » 5 years ago, # |   0 How can a contest be based on a fairy tail? Can anyone explain? Thank u.
•  » » 5 years ago, # ^ |   0 Something like that: http://codeforces.com/blog/entry/13247.
 » 5 years ago, # |   -24 I wish the time of the contest will be any time instead of breakfast time for muslims people in ramadan :/ , there is many contest in this time , can any one who will create a new contest can make it any time but not in our breakfast time ?, i think there is many Programmers will join it
•  » » 5 years ago, # ^ |   +14 time comfortable for you maybe uncomfortable for someone else
•  » » » 5 years ago, # ^ |   0 i think so :/ , but i need to change my rating :"(
•  » » 5 years ago, # ^ |   +21 Happy Ramadan
•  » » » 5 years ago, # ^ |   0 Thanks :) !
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I wanted to write something insulting here about muslims misconceptions, but didnt find proper words.
 » 5 years ago, # |   +7 It's so sad that I have two exams after tomorrow. But I can't help but give up this contest because the time of the contest is too late for me to have a good sleep. I really want to be a Div.1 player.
•  » » 5 years ago, # ^ |   +14 So sad.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -23 That story is fake
 » 5 years ago, # |   0 Who can tell me what the picture means?
•  » » 5 years ago, # ^ |   +145 The Snow Queen shows a young boy how it is to participate in a Div1 contest.Seriously, what explanation do you expect? If you're interested in the story then google "Andersen Snow Queen".
•  » » » 5 years ago, # ^ |   +12 Thank you
•  » » 5 years ago, # ^ |   +13 This has a complete explanantion of the story and of the picture. Here is what it says about the picture: "The following winter, Kay goes out with his sled to play in the snowy market square and — as was the custom — hitches it to a curious white sleigh carriage, driven by the Snow Queen, who appears as a woman in a white fur-coat. Outside the city she reveals herself to Kay and kisses him twice: once to numb him from the cold, and a second time to make him forget about Gerda and his family; a third kiss would kill him. She takes Kay in her sleigh to her palace."
 » 5 years ago, # |   +2 Good luck to all !
 » 5 years ago, # |   -6 The scoring distribution will be announced later？
•  » » 5 years ago, # ^ |   +32 You have to form the word "eternity" from pieces of ice to know the score distribution
 » 5 years ago, # |   +17 The score distribution shows D and E have same points...this one is going to be a tricky contest :D
 » 5 years ago, # |   +27 Summary of my participation:-Solves A relatively fast--Solves B relatively fast-"Hey, C is as hard as B so that shouldn't take long."-Proceed to dwell for an hour and a half without any results-I god damn hope C has some very magical and easy observation that leads to an elegant solution, cause else that scoring was atrocious :D
•  » » 5 years ago, # ^ |   0 How to solve your B?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -14 Don't know if you meant the division 1 B, but for Div2 I brute forced it, manually swapping two elements at a time when necessary and after every swap checking if it's sorted.
•  » » » » 5 years ago, # ^ |   0 I don't say div.2 B!
•  » » 5 years ago, # ^ |   -9 Yeah, you can simply check all pairs if sum of number of digits in the first one and the second one is <= 7, there are not many of those pairs I assume :D
•  » » » 5 years ago, # ^ |   +6 He's talking about Div.1 C I believe.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 I don't think he is talking about div2 C :P
•  » » » » 5 years ago, # ^ |   0 Oops, I forgot that there was a Div1, not used to it, sorry!
•  » » 5 years ago, # ^ |   +23 In C I moved to 4-dimensional space: (x, y, z) -  > (x + y + z, x + y - z, x - y + z, x - y - z) and used binary search in which I just intersected 4-dimensional cubes. But it's not enough to check that the intersection is not empty, you should also check that it has nonempty preimage.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +11 I used the same approach but failed. It might be easier if the distance was asked instead of the actual point :(
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 I can't understand, can you elaborate please? How does 4 dimension help? Also, can anyone suggest some problems which can be solved in similar way?
•  » » » » 5 years ago, # ^ |   +8 In Manhattan metric sphere is octahedron. Mentioned transform maps it to hypercube. Intersecting hypercubes is done coordinate-wise. After that we need to check that intersection has nonempty preimage. Ifa = x + y + z, b = x + y - z, c = x - y + z, d = x - y - z, thenx = (a + d) / 2 = (b + c) / 2, y = (a - c) / 2 = (b - d) / 2, z = (a - b) / 2 = (c - d) / 2.So the image of contains all integer points in hyperplane a - b - c + d = 0 with a ≡ b ≡ c ≡ d(mod 2). So we need to intersect that hyperplane with our cube and check some cases.There was similar problem on IOI 2007(link, problem "pairs").
•  » » 5 years ago, # ^ |   +1 Don't worry, it could have been much worse :D-Solves A relatively fast--Solves B relatively fast--Codes C relatively fast-Then try to debug WA for 1 hour. The only mistake in the code? I was checking if the number was odd by doing "number % 2 == 1".
•  » » » 5 years ago, # ^ |   0 What is wrong with that check?
•  » » » » 5 years ago, # ^ |   +6 -1 % 2 is -1, not 1 :(
•  » » » » » 5 years ago, # ^ |   0 Ok, I've forgotten about negative numbers.
•  » » » » » 5 years ago, # ^ |   0 Yeah, this test was put in statement by exactly same reason.
•  » » » 5 years ago, # ^ |   0 Solving B after 50 minutes seems relatively slow for you :p
 » 5 years ago, # | ← Rev. 2 →   +3 Do DIV 2 4th has a solution with binary search and dfs at each node?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 Yes, it can be done with binary search. First , we need to decompose the tree into chains using a dfs, by moving from a node to its largest sized sub-tree . Centroid of the subtree of node v, will lie somewhere on the chain consisting of v,below v.Now independently solve each chain. Suppose our chain has size x and we want to find the centroid for ith node in this chain , say chain[i].Now the centroid of chain[i] will be the first node chain[j] , i <  = j <  = x , such that maxChildSubtreesize[j] <  = Subtreesize[i] / 2 . Also , maxChildSubtreesize[j] is a decreasing function since we are moving down the tree. So, we can apply binary search with lower bound as i and upper bound as x.Overall Complexity :O(nlogn)Code
 » 5 years ago, # |   +9 Was O(log3(1018)) enough in C? I implemented O(log(1018)) but damn, that wasn't easy.
•  » » 5 years ago, # ^ |   0 What's your solution?I implemented binary search to get 4 inequalities A<=x +/- y +/- z<=B (assuming that 3d solution should be similar to 2d vesrion) and then realized that I have no idea how to actually find some integer solution (x,y,z) from these inequalities, or at least how to check that there exists one :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Ternary search on one coordinate z. For fixed z I have four inequalities and I claim that the value of answer is maximum of distances between parallel inequalities. This allows to find optimal z but not to find optimal x, y then.Maybe I should then ternary search the next coordinate but I think it's hard to implement. So instead for the found four inequalities I imagines drawing four lines, then I found two intersections (an intersection of leftup and leftdown lines, and an intersection of rightup and rightdown lines) and then the answer should be in the middle of segment connecting the two intersections. I didn't know if I can round the answer (found x, y) to closest integers so I checked brutally all 22 possibilities of rounding.
•  » » » 5 years ago, # ^ |   0 Is this correct for 2D version ? A=(min(Xi+Yi)+max(Xi+Yi))/2; B=(min(Xi-Yi)+max(Xi-Yi))/2; and you can get answerX and answerY from this answerX+answerY=A; answerX-answerY=B; answerX=(A+B)/2; answerY=(A-B)/2; I used same solution for 3D (4 coordinates for each point) , but got WA 6
•  » » » » 5 years ago, # ^ |   0 It is a bit more complicated. You have constrains on x + y + z, -x + y + z, x — y + z, x + y — z.The problem is about solving them
•  » » » » 5 years ago, # ^ |   -10 Same, I got WA4. I'm 99% sure it's correct for the 2D case, and some version of this idea really ought to work for the 3D one. One mistake which I couldn't fix in time: Adding 3 coordinates (or even 6 when taking average by (min+max)/2) can get you an overflow! Did you avoid that?
•  » » » » » 5 years ago, # ^ |   0 after WA#5 I checked x-3..x+3 y-3..y+3 z-3..z+3 , and it helped for test #5 :D
•  » » » 5 years ago, # ^ |   +10 It really is the same, you can consider: x + y + z, x + y — z, x — y + z and y + z — x. Transforming a point in such a tuple, it becames similar to 2D version(the rotation in 2D) and binary searching is enough. The very very stupid thing is that you really have to take care of overflow and of some parities as well and it's pretty ugly. The problem would have been much nicer if they fixed the limita 10^17 and the problem had a higher score. I didn't even had time to think at the other tasks and still have to write some more lines...I guess that in k-D plane, you have 2 ^ (D — 1) elements in tuples. I really liked that the rotation can be generalizate but the overflow really destroy the task
•  » » » » 5 years ago, # ^ |   0 I thought about overflow, but I don't think I can get any number out of range {-6*10^18 .. 6*10^18 }
•  » » » » » 5 years ago, # ^ |   0 Ohh never mind, thought the long long limit was around 2*10^18. No idea what my mistake was, in this case...
•  » » » » » » 5 years ago, # ^ |   0 Try this test: 1 3 10 10 10 10 9 10 10 10 9 This is a test where, in my source, at least, I had to take care at parity. I think I solved it now but I am unable to submit because it seems that they didn't enable the practice session yet
•  » » » » » » » 5 years ago, # ^ |   0 That is a counterexample indeed, thanks!
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Could you explain how you got overflow?Proposed solution fits in long long quite well.
•  » » » » » 5 years ago, # ^ |   +5 Well I didn't but theoretically some lines could get overflow so I thought a lot about how to improve them. For example, as in editorial, let's fix L the maximum distance, we had relations like maxA — L <= a <= minA + L and so on and we had one more for their sum maxS — L <= a + b + c <= minS + L. We had to intersect the intervals [maxS — L, minS + L] with [maxA + maxB + maxC — 3 * L, minA + minB + minC + 3 * L]. The ends of the later are very big in worst case...I hardly came up with a solution to treat those overflows.
•  » » » » » » 5 years ago, # ^ |   +33 Ouch, i see now. I should have set 1017 bound.My solution got over this trouble because of parity handling, when replacing a = 2a' + r, not only parity restriction goes away, but coordinates also become twice less.
•  » » » » » » » 5 years ago, # ^ |   0 Yeah, I made the same mistake once in one of my problems — 611G - New Year and Cake.We realized about possible problems with overflow in the day of the contest and I didn't have time to decrease constraints from 109 to 108. In hurry I added two tests designed to cause overflow (because if such malicious tests are valid then a setter should add them) and I put one of them in pretests. One participant had a bad luck and his solution passed pretests but didn't pass the other overflow-test and thus got WA on systests. Fortunately, he won anyway.One thing is that I should have set 108 in the first place. But since there was no time, I should have include both malicious tests in pretests. I learnt a lesson that day.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +10 Let x+y+z=C, x-y+z=D, x-y-z=E, x+y-z=F.There is integral solution to system if and only if C,D,E,F all have the same parity and C-D+E = F.What I did was, for each possible parity, take C,D,E to be the smallest possible and calculate value of C-D+E. Then try to make it fit into range of F inequalities by increasing C/E (if C-D+E is too small) or increasing D (if C-D+E is too big).
•  » » » 5 years ago, # ^ |   0 Turns out that bruteforcing a 3x3 cube around the non-integer solution works. No need to do any parity fiddling.18693710
•  » » 5 years ago, # ^ |   +79 Seems this was the worst difficulty estimation I made this year :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +47 But problems were nice and there were no issues. #smallmiraclesAnd I liked the fact that pretests were strong.
•  » » » » 5 years ago, # ^ |   +5 True. No hacks in Div1, only 5 hacks in Div2
•  » » 5 years ago, # ^ |   0 No, it wasn't. O(log) is proposed solution.
 » 5 years ago, # |   +15 The problem C sucks. Don't know what the statement want to say. My poor English. :(
•  » » 5 years ago, # ^ |   -31 Yeah me too so I send them this But they didn't respond for some reason i can't explain.But i was able to solve it somehow!
 » 5 years ago, # |   0 I loved the contest — the tasks were challenging but I hope I did 4 tasks correctly, we'll see :)
 » 5 years ago, # |   +3 Unexpected typing contest :P I thought Div1D was relatively easy than Div1C, and wanted to submit it T.T
 » 5 years ago, # |   +6 Testcase 11 div2 C :|
•  » » 5 years ago, # ^ |   +3 same here
•  » » 5 years ago, # ^ |   +6 Did you take log(n) or log(n — 1) ?
•  » » 5 years ago, # ^ |   0 I also stuck at that testcasebut after change (hourlength+minutelength > 6) to ( > 7)it passed.
•  » » 5 years ago, # ^ |   0 i was also stuck on that tc, implemented a recursive descent solution, testing out all possible combinations of different numbers. then i realised that i need to make room for 0 to n-1, instead of 0 to n so i think the tc is something like: 343 2401, where my program would output 0, while there is a solution :(
•  » » » 5 years ago, # ^ |   0 just had to do a n--,m--; at the start done the same mistake :(
•  » » 5 years ago, # ^ |   0 Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
•  » » » 5 years ago, # ^ |   0 LOL same xD
•  » » 5 years ago, # ^ |   +1 Don't remind me :"( That pretest 11, I really wonder what it is.
 » 5 years ago, # |   0 How to solve E ? I have a O(n m) solution that runs in 1450ms on a random test of maximum size, how to do better ?
 » 5 years ago, # | ← Rev. 2 →   +11 What is 11 pretest in Div2C?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 try this one:7 7the answer is 42
•  » » » 5 years ago, # ^ |   0 Answer?
•  » » » 5 years ago, # ^ |   0 getting 0
•  » » » 5 years ago, # ^ |   0 Shouldn't it be 0? Any single digit hour will have leading zero and so the single digit minute too? 01:02. Then 0 is duplicated (?)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 You need only one digit for hours and one digit for minutes.not 01:02 but 1:2
•  » » » » 5 years ago, # ^ |   +6 No, the watch will only have 1 digit because 1 digit is sufficient to represent 0-6. (6 = n — 1 = 7 — 1)
•  » » » » » 5 years ago, # ^ |   +1 Oh shit, forgot than numbers are in range 0, n — 1 and 0, m — 1.
•  » » » » » » 5 years ago, # ^ |   +1 same here. forgot to n--;m--;
•  » » » 5 years ago, # ^ |   0 Answer to the Ultimate Question of Life, the Universe, and Everything...
•  » » 5 years ago, # ^ |   0 Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
 » 5 years ago, # |   +101 Div1 B and C having same score doesn't even sound funny...
 » 5 years ago, # |   +11 Problem B is classic. So many people know it. I remember have solved it! It's not fair!
•  » » 5 years ago, # ^ |   +8 How do you solve it? I've never seen finding centroid before...
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 My idea is tree dp. Here's a brief sketch of my idea :Do standard subtree size dp. For each node, determine the maximum subtree size of its children. Then, we calculate the answer for each node which is closest to the root. (actually I think I implemented something slightly different in my solution) We consider whether the node itself is actually a centroid and also which nodes to take from the childrens. This sketch is not very detailed but this is briefly what I did.UPD : It got Accepted! Basically, I stored a "jump pointer" on each node, which is initially the answer for that node (after we finish dfsing the node). Then, when we process the parent, this "jump pointer" jumps depending whether jumping to the parent will yield a better centroid (better centroid means maximum subtree size is lesser, with ties broken using distance from root). Using this, for each child of a node that we're currently processing, if the node itself is a centroid, we take the node. Otherwise, we check the jump pointers in the childrens. Code
•  » » » » 5 years ago, # ^ |   0 Why closest to the root? And what's the time complexity?
•  » » » » » 5 years ago, # ^ |   0 It's ~3am here so I'm lazy to go over the details. Actually, it doesn't need to be closest to the root I think, it's something like this.Time Complexity should be O(n) I think.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Brief basica idea: dp on tree when you process subtree rooted at v check if v can be centroid if it can't be centroid, then the centroid will be on the path largest_child_of_v -> centroid[largest_child_of_v] It is enough to start with the centroid on the largest child and move up by parents until you find the centroid of the v. Amortized time os O(n).
 » 5 years ago, # |   +3 Div1C: I found a possible overflow bug 10 sec before the end, couldn't submit in time... I REALLY hope that wasn't my only mistake and I didn't mess up by literally less than a minute :D
 » 5 years ago, # |   -29
 » 5 years ago, # |   +8 Why is the memory limit so tight in Div1-D? My solution went a few MB over. :(
•  » » 5 years ago, # ^ |   -16 We know solution with linear amount of memory.
•  » » » 5 years ago, # ^ |   +11 The solution in the editorial uses O(nk) memory. I had two arrays of size n*k each, they require some 228 MB. 256 MB memory limit definitely seems too strict if you intended to allow O(nk) memory solutions to pass.
 » 5 years ago, # | ← Rev. 2 →   0 In task E (div. 2) we need to find min-size enclosing octahedron, but it turns out a little bit difficult...
 » 5 years ago, # |   +3 My solution for D went stack-overflow on my computer but passed the pretest :v Guess it will fail the system test :v
•  » » 5 years ago, # ^ |   +8 Same happened with me. I wasted 25 minutes on this issue. Later I tested it through custom invocation and it worked.
•  » » » 5 years ago, # ^ |   +11 Same with me. I resubmitted in panic, only to realise it wasn't necessary!
 » 5 years ago, # |   0 Can someone give hint for DIV2 C ? Cheers =)
•  » » 5 years ago, # ^ |   +14 bruteforce , the max length of answer can be 7 as for answer more than 7 , atleast 1 digit will be repeated.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 My bruteforce seems to give TLE on pretest 13. Plz look at this code: http://codeforces.com/contest/686/submission/18685502
•  » » » » 5 years ago, # ^ |   0 dont use strings
•  » » » » » 5 years ago, # ^ |   0 Why do they take more time as compared to arrays?
•  » » » » » 5 years ago, # ^ |   0 I used strings and didn't get TLE
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Though an overkill, you can use digit dp to solve it too O(log(N) * 210 * log(M)) which is O(logN * log(M)) (Not really :P ).18689097I had to code both the solutions as digit dp didn't pass as I was missing returning 0 when the input was 0 in the base_7 function, so eventually writing this code so fast was of no use.
 » 5 years ago, # |   +8 Somehow misread that m ≤ 1000 (instead of correct 200'000), invented a n3 / 32 solution, implemented it... and finally noticed that I'd misread the constraints.***k.
 » 5 years ago, # |   +1 Going through the stats:pretest ones: Div 2 Problem B was solved by 2700+ and Div 2 Problem C was solved by only 791 which suggests that C should be of more points as compared to B
•  » » 5 years ago, # ^ |   0 Good thing it is I guess?
 » 5 years ago, # | ← Rev. 3 →   +3 Python is really troublesome:A: O(7^7) [7^7 is less than 1 million] run in >3s on custom invocation, need O(7!) [7 factorial] to pass pretest.B: Fast I/O required, otherwise it will be TLE on pretest 3, (I'm not sure if it can pass systest even after using fast I/O)So for this contest I spend most of my time optimizing slow pyhon solution.From next contest, I'll use faster language, goodbye beautiful Python! Hello div2 :D
 » 5 years ago, # |   0 this round is hard but interesting.what is the solution of Div2E,Div1C ?
 » 5 years ago, # |   0 How to solve Div 2B?
•  » » 5 years ago, # ^ |   +4 Bubble sort is the easiest way — just swap two neighbours, and there will be no more than n*(n-1)/2 swaps (approx 5000) so it should pass every test.
•  » » 5 years ago, # ^ |   0 You can just sort the animals with bubble sort, and just print all the swaps you do. Since bubble sort has complexity n^2 it is guaranteed to do no more than n^2 swaps. From the constraints of the problem, the maximum value for n is 100, so the bubble sort will do at most 10000 swaps (less than that really, but it doesn't matter). So you are always guaranteed to make less than 20000 swaps.
 » 5 years ago, # |   +16 Submitted at the last minute with this for div1 E...  for( int i = 0 ; i < q ; i ++ ) puts( ans[ i ] ? "YES" : "NO" ); It should be "Yes"/"No" instead of "YES"/"NO"....
•  » » 5 years ago, # ^ |   +3 Isn't checker case-insensitive? I think it is by default. Are you sure you get correct answers on sample tests, besides case?
•  » » » 5 years ago, # ^ |   +35 The checker is case-insensitive for a single yes-no. For a sequence of Yes\No wcmp is used, and it's not case-insensitive.
•  » » » » 5 years ago, # ^ |   +18 Can this be made case-insensitive? Such inconsistency is a bit confusing.
•  » » » » » 5 years ago, # ^ |   0 Testlib checkers' home is here. Perhaps one can combine yesno and fcmp/wcmp, and then propose a pull request to add it to the default checkers? Or just make a case-insensitive fcmp/wcmp version.
•  » » » » » » 5 years ago, # ^ |   0 Nothing that I have against it, but I sometimes wonder why problem setters not have binary values as output (0/1) instead of ("YES/NO", "ALICE/BOB") etc.
•  » » » » » » » 5 years ago, # ^ |   +5 Are you saying 0/1 is better than Alice/Bob? How? The former one needs explaining in the statement, the latter doesn't.
•  » » 5 years ago, # ^ |   0 So would you have got AC if you hadn't made this mistake?
•  » » » 5 years ago, # ^ |   0 Fortunately, Nope. It got TLE with time complexity O(NM).However, I still get AC with another O(NM) solution which has less constant.
 » 5 years ago, # |   +7 Yeah, Div2C/Div1A had a really bad english problem statement. I managed to understand it, but it must have been hard for some contestants whose first language is not english.
 » 5 years ago, # | ← Rev. 2 →   +4 The pretests were too strong. I didn't see any hack during the contest.
•  » » 5 years ago, # ^ |   +1 Yeah. But I have nothing to complain. I would have failed in two problems if they were weak. LOL
 » 5 years ago, # |   0 Anyone stuck on pretest 4 in Div 2 C ? If passed some test cases please ...
•  » » 5 years ago, # ^ |   +4 check for n=1 or m=1 case
•  » » » 5 years ago, # ^ |   0 thanks
•  » » 5 years ago, # ^ |   0 You may also want to check for n = 7^3 and m = 7^4, or 1 and 7^7
 » 5 years ago, # |   +10 Why Div1E's Time limit were set too strict?
•  » » 5 years ago, # ^ |   +15 Maybe intended solution is O(N2 + M)
•  » » » 5 years ago, # ^ |   +5 I don't think so. And I agree that it is too strict.
•  » » » » 5 years ago, # ^ |   +31 If it's really O(NM) it becomes very easy, strict, stupid problem
 » 5 years ago, # |   0 English is not my native language, for problem DIV2 D / DIV1 B what does "Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)." means?
•  » » 5 years ago, # ^ |   +2 Take a node in a tree. Remove it. You get some disconnected components (corresponding to the edges the node had). If none of these components contains more than half of the original tree, that node is a centroid.
•  » » 5 years ago, # ^ |   +1 If a tree has n nodes, then the centroid of that tree is a node such that when you remove that node (and its edges), the remaining graphs that are left from the tree all have at most n/2 nodes.
 » 5 years ago, # |   +38 OMG!!! 2 weeks ago on a Xellos's SRM hard problem was like "count centroid for every subtree and do something easy". Today's problem B was "count centroid for every subtree". On that SRM I did that problem and took 4th place, so I simply copy-pasted my code and printed computed centroids, but I got TLE on 14th test. After few tries of optimizing constant I thought that there is probably something wrong with the idea and maybe I was just lucky on SRM, because maybe proof of time amortization was not right. I thought that one of authors saw my description in the discussion of that SRM, found a counterexample and thought it is a good idea to give that as a problem on CF. That would be perfectly cruel, right :P? However it turned out, that I got that incredibly idiotic piece of code auto UpperTree = [&](int guy) { int upper_tree = sz[v] - 1; for (auto s : sons[guy]) { upper_tree -= sz[s]; } return upper_tree; }; computing number of vertices outside guy's subtree when restricted to v's subtree, whereas it should have simply returned sz[v] — sz[guy] --__--. I'm such a moron xd. On SRM that code passed because input was given by a random number generator there. "Broom test" obviously makes my solution TLE here. However that code was written at ~4AM, maybe that could be forgiven xD.
•  » » 5 years ago, # ^ |   +33
•  » » 5 years ago, # ^ |   +26 Shit, looks like I have to start competing in SRM again (
•  » » » 5 years ago, # ^ |   -11 Можете проверить у меня задача А отправилось 2 раза? 18677724 и 18677705
•  » » 5 years ago, # ^ |   +8 Wow, you're red and you can't handle broom test in tree problems. I totally did the same thing during the round
•  » » » 5 years ago, # ^ |   0 On Petrozavodsk camp there was a problem where many contestants had got AC even though broom test would have made almost all of them TLE :P.
•  » » » » 5 years ago, # ^ |   0 What is broom test? I couldn't find what it means
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +27 In that case: parent[i] = min(i - 1, n / 2)
•  » » » » » » 5 years ago, # ^ |   +5 Wow, I've should understand from "broom" xd
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 It's not like we didn't have a problem in a rated contest in which the editorial solution used to TLE on broom test :PEdit: I now see they changed the editorial to the official solution, which is correct :)
 » 5 years ago, # | ← Rev. 2 →   0 My E is still in queue :oEdit: It is judged now.
 » 5 years ago, # |   +25 Why does systest always get stuck on 100%?
•  » » 5 years ago, # ^ |   0 I think that's to eliminate the cases of cheating.
•  » » 5 years ago, # ^ |   +20 that's called suspense
 » 5 years ago, # |   +6 What I did for Div 2-D (Div 1-B) got Accepted, but it took 2 seconds and I'm having a hard time analyzing the time complexity.I computed centroids bottom up. So for current node u, if it is a centroid of the subtree rooted at u, great, else set the current node to the centroid of the largest subtree of the current node. While the current node isn't the required centroid, go to either the centroid if its largest subtree, or to its parent depending on which direction the centroid should lie (using sizes).I precomputed the largest subtree and the size of the subtree for each node in O(n) in advance.Can someone estimate the time complexity of this solution? Thanks a lot.
•  » » 5 years ago, # ^ |   +5 You're visiting every node at most 2 times. First time when computing it's answer, second time when testing it for another node's answer. (Assuming that you're breaking the loop that goes up after finding the centroid). 2*n -> O(n)
•  » » » 5 years ago, # ^ |   0 Hi,Sorry I didn't completely understand. Could you give me an intuitive reason why a node will only be tested once for another node's answer?
•  » » 5 years ago, # ^ |   +11 I did the same, it's O(N), surprisingly.Consider the paths formed by only taking the edges from each parent to its largest subtree child. These are the paths where you'll be "moving the centroids upwards", so to speak, so that part is O(number of edges) = O(N), and the rest are simple — e.g. finding the child with the largest subtree is also O(number of edges) = O(N).
•  » » » 5 years ago, # ^ |   0 Hi,Sorry I didn't really understand why those particular edges (connecting a node to its largest subtree) will be the only ones where I'll move centroids upwards. Also, why would each such edge be used only once?
•  » » » » 5 years ago, # ^ |   +6 My explanation was pretty bad actually :D It's kind of hard to explain though. But I'll try again in more detail.The centroid of a tree is always either its root or some node in its largest child subtree. If it's the latter, it's always the root of the subtree or in the largest "sub-subtree" of that subtree and so on. Therefore, when you want to calculate the centroid of a tree and you start "moving" the centroid of its largest subtree upwards, you're always following such "largest-subtree-edges", so to speak.As for why they each occur only once: Imagine taking the leaf, then following these edges upwards, each time calculating the centroid of subtree rooted at your current position. Since you're following these "largest-subtree-edges", at each step, you're going to adjust the previous subtree's centroid by moving it upwards. And you never move it down. So the only situation when you have to examine the possible movement of the centroid on the same edge multiple times is when you have chosen not to move it previously. But when you don't move the centroid, you finish calculating it for the current subtree, so there can be no more than N non-moving examinations. And each moving examination looks at a different edge, so there are also no more than N of those. All in all, it's O(N) checks!Phew, that was hard to clear rigorously... Hope it helped somewhat.
•  » » » » » 5 years ago, # ^ |   0 Thanks a lot!I understand why the complexity is O(N) now.Is it right then, that my second check (searching for the centroid further down) was unnecessary as the centroid can only move up (after initially setting it to the centroid of the largest subtree)?
•  » » » » » » 5 years ago, # ^ |   +3 Indeed, you're right :)
•  » » » » » » 5 years ago, # ^ |   +3 Yes. You're adding more nodes to the subtree at its top, so the centroid is going to move upwards, intuitively. (Unless you add so many nodes to the top that the previous subtree is not even the largest, in which case you'd pick a different child of the new root and you're never going to visit this subtree again.)
 » 5 years ago, # |   -17 I think there should be atleast one problem with weak pretests. Otherwise there is no meaning of keeping the hacking feature.
 » 5 years ago, # |   +23 Why Div1-C's points are 1250???? I think this problem is very hard...
 » 5 years ago, # |   +114
 » 5 years ago, # |   +13 It looks perfect when there are no fakes in div2 top
 » 5 years ago, # |   +22 I bet tourist will compete in next round!
 » 5 years ago, # |   0 Well Div2C is quite a tricky problem. You just have to decrement n and m then start solving, it is mentioned (numbers from 0 to n — 1/m — 1) And when converting a number to base 7 just make sure that you are considering the case of 0. I couldn't solve it in contest because of those two bugs.
 » 5 years ago, # | ← Rev. 2 →   0 Can somebody show me just one valid pair for div2C TC11: 16808 7 ?I just can't understand how there are 720 valid pairs
•  » » 5 years ago, # ^ |   +1 012345:6
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 ohhh, I thought we should take 2 places for 7but we need only 1 place for 7-1 = 6
•  » » » 5 years ago, # ^ |   0 Quite tricky :(,
 » 5 years ago, # |   +70 congratulations for the first Arabic/Egyptian Grandmaster TsunamiNoLetGo
•  » » 5 years ago, # ^ |   +11 Thanks :)
 » 5 years ago, # | ← Rev. 2 →   0 Why do I get WA (=5040) for my submission 18687880 for test case 7 (problem C)344 344whereas on my compiler and ideone I get the correct answer = 0.Any help is appreciated.
•  » » 5 years ago, # ^ |   0 log is at fault here.
•  » » » 5 years ago, # ^ |   0 fault where, at the CF server?
•  » » » » 5 years ago, # ^ |   +7 No, the log function (and floating point computation in general) is only an approximation. They do their best to implement the closest answer, but they are not necessarily exact. For example, in your solution, you have int(tmp), where tmp is a double. This simply truncates tmp (it does not round it). So if tmp=24.999999.., it would simply be truncated to 24 instead of giving the exact answer of 25 as you would expect.The take home message is to not use floating point computations unless you actually need to. If you have to use them, you should always check that no significant errors have occurred. Here are some common functions that lots of people mess up on: pow, sqrt, fabs, log.
 » 5 years ago, # |   0 Can anyone help me debug this?This solution got accepted http://codeforces.com/contest/686/submission/18688448 And this got Wrong Answer: http://codeforces.com/contest/686/submission/18688414However, the only change I made was comparing the subtrees of the centroid pretender and the current node, at line 28. This shouldn't change the program's behaviour. I'm following this solution: http://codeforces.com/blog/entry/45556?#comment-301968
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 sub[cur] - sub[cen[cur]] > sub[cur]/2 and sub[cen[cur]] < sub[cur]/2are not equal because sub[cur]/2 will round down. For example, lets say sub[cur] is 3 and sub[cen[cur]] is 1. 3 - 1 > 3 / 2 is true while 1 < 3 / 2 is false.
•  » » » 5 years ago, # ^ |   0 Thanks, it works declaring sub and msub as double. Didn't think this would affect.
•  » » 5 years ago, # ^ |   0 Hi,Not sure, but I think that in the second submission, your condition sub[cen[cur]] < sub[cur]/2 should use a <= sign?
•  » » » 5 years ago, # ^ |   0 Actually not. If it compares equal, the candidate is necessarily a centroid, as there would be a subtree with n/2 nodes and another (or more than one) with n/2-1 nodes.
 » 5 years ago, # |   +20 Is Petr going to cross tourist next time?????? Or tourist is gonna come back to defend the title???????????????? Keep watching on Codeforces!!!!!!!!!!! Yayyyyyyyyyyyyyyy :D
•  » » 5 years ago, # ^ |   +88 I think your keyboard may be broken. Some keys keep getting stuck.
 » 5 years ago, # | ← Rev. 3 →   -20 The "optimal point" problem only uses well known school topics.You needed to know how to expand module inequalities:|x - x1| ≤ A if and only if x1 - A ≤ x ≤ x1 + A.And then notice the simple replacement of variables.Very surprised about number of Ac's.
•  » » 5 years ago, # ^ |   0 I don't think you can do anything with it in this problem. Did you get accepted?
•  » » » 5 years ago, # ^ |   +18 He is author btw
•  » » » » 5 years ago, # ^ |   +72 But did he get accepted? :D
•  » » » » 5 years ago, # ^ |   +5
•  » » 5 years ago, # ^ |   -16 Unfortunately, this is not clear enough. And the fact that you don't have the editorial makes it look even worse.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 The editorial is been prepared, please wait.UPD. It is here: http://codeforces.com/blog/entry/45558
•  » » » 5 years ago, # ^ |   0 We don't have the editorial yet but we are working on this issue...
•  » » 5 years ago, # ^ |   +25 Measuring difficulty in terms of required knowledge is not a good idea. If you measure difficulty that way then why did you set E as E :)? Indeed this problem doesn't require sophisticated knowledge and I got a right idea pretty quickly, but got a hard time figuring out the details and carefully implementing it (at which I failed). And as already pointed out what you have said does not seem to be sufficient to describe main idea. However maybe there is some significantly easier solution than those I already know.
 » 5 years ago, # |   0 In Codeforces Round #359 (Div. 2) Problem 686B - Little Robber Girl's Zoo sample test cases Outputs were wrong. Correct me if i am wrong.
•  » » 5 years ago, # ^ |   +6 If it was wrong, how can 1000 users solve it?
•  » » » 5 years ago, # ^ |   -11 If it was right then check outputs of 18671047 . I am talking about sample testcases. Take a look at written outputs in sample testcases of problem and outputs of the submission (which has been accepted) .
•  » » » » 5 years ago, # ^ |   -8 Test case output is correct.This problem allows to have multiple correct solutions.
•  » » » » » 5 years ago, # ^ |   -8 But it is not mentioned in English version.
•  » » » » » » 5 years ago, # ^ |   0 <> (C) statement.
•  » » » » » » » 5 years ago, # ^ |   +4 Ohh My mistake. I wish i had read that during contest time.Thank you for pointing out cdkrot. I had already solved that using Bubble sort but, i thought it is wrong since it was not matching with sample test cases.
•  » » » 5 years ago, # ^ |   0 As Written on problem : 4 2 1 4 3 Output of 18671047 1 2 3 4 `How can it become correct ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.
•  » » » » » 5 years ago, # ^ |   0 It was not mentioned in the Problem statement that "any solution" that minimize the number of operations will be accepted.
•  » » » » » » 5 years ago, # ^ |   0 Just scroll down to the notes section.
•  » » » » » » » 5 years ago, # ^ |   0 Got it, It was my mistake. I wish, i had noticed that during contest. Even after solving i didn't submitted because it was not matching with sample test cases.
 » 5 years ago, # |   +43 It would be nice if in some of these problems, you would provide a formal definition using mathematical symbols to avoid ambiguity."Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)."That isn't correct English. I think "at least two times smaller" is the main problem :(
 » 5 years ago, # |   +1 Editorial posted.