### tourist's blog

By tourist, history, 6 months ago, translation, ,

Hey!

On Oct/16/2019 17:35 (Moscow time) we will host Codeforces Global Round 5.

It is the fifth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

The round will last for 2 hours 30 minutes, 8 problems are waiting for you, and one of them will be proposed in two versions.

Scoring distribution: 500 — 750 — (750 + 750) — 2000 — 2500 — 3000 — 3750 — 4000

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me, and here is the list of people who can't take part in the round as they know the problems beforehand:

Coincidentally, this is also the list of people I'm thankful to for making this round what it is.

The round will be perfectly balanced. As all things should be.

Welcome!

UPD: The round is over! Editorial is here. Congratulations to the winners:

Announcement of Codeforces Global Round 5

• +3664

 » 6 months ago, # | ← Rev. 3 →   +524 I think this is tourist's way of telling Um_nik "Go ahead, enjoy being the highest rated guy on CF while you can".
•  » » 5 months ago, # ^ |   -179 TOURIST!!
•  » » 5 months ago, # ^ |   +98 Press F for Um_nik
•  » » 5 months ago, # ^ |   0 Lol :D
 » 6 months ago, # |   -82 Omg, the GOD of CP talking to us
 » 6 months ago, # | ← Rev. 2 →   +9 Reason for so early registration opening or this has been done before?
 » 6 months ago, # |   +51 So, characters are from the Avengers in this round..
 » 6 months ago, # |   +340 Can tourist even think about question of level A and B
•  » » 5 months ago, # ^ |   +19 I bet they all sound to him like something of "what time is it?" difficulty.
•  » » » 5 months ago, # ^ |   +59 Actually I find it pretty hard to identify time in standard clocks xD
•  » » 5 months ago, # ^ |   +39 Duh bro...... Every question is A or B for tourist xD!!!
 » 6 months ago, # | ← Rev. 3 →   +387 normal setters(hours before contest) — We have tried our best to keep the round balanced, tourist(days before contest) — The round will be perfectly balanced. _/\_
 » 6 months ago, # |   +30 Codeforces be like : best , better , bestest :D
•  » » 5 months ago, # ^ | ← Rev. 2 →   +176
 » 6 months ago, # |   -19 I want to win a T-shirt, I hope I'll get it.
 » 6 months ago, # |   -29 hope c is c and not e or f.
 » 6 months ago, # |   -27 But it is a soul for a soul
 » 5 months ago, # |   -50 You forgot to thank MikeMirzyanov and Codeforces.
 » 5 months ago, # |   +118 Come on, snapping half of living beings sounds very short-sighted.
•  » » 5 months ago, # ^ |   +369 Sounds as round will be semi-rated
•  » » » 5 months ago, # ^ |   +307 More like only half of CF servers will be alive
•  » » » 5 months ago, # ^ |   +3 omg, "semi-rated"
•  » » 5 months ago, # ^ |   0 haha
 » 5 months ago, # | ← Rev. 2 →   +108 GLHFYou ready?! Let's go!Yeah, for those of you that wanna know what codeforces all aboutIt's like this y'all (c'mon)This is ten percent bruteforceTwenty percent greedyFifteen percent concentrated power of geometryFive percent hacksFifty percent wrong answerAnd a hundred percent reason to participate in contest.GLHF everyone !!
•  » » 5 months ago, # ^ |   +13 And still you are unrated
•  » » » 5 months ago, # ^ |   -28 at least i am not participating in contest with alternate account
•  » » 5 months ago, # ^ |   +8 Mike shinoda
 » 5 months ago, # |   +374
•  » » 5 months ago, # ^ |   -44 who the hell even reaches C lol
•  » » 5 months ago, # ^ |   0 also here :))
•  » » 5 months ago, # ^ |   +22 Then hacked:-(
 » 5 months ago, # |   +270 $-150$ after the round feels like "Mr. Mike... I don't feel so good..."
•  » » 5 months ago, # ^ |   -28 Mr. Radewoosh... I don't feel so good...
•  » » 5 months ago, # ^ |   +5 +124 feels like 'I am the one the one, who need no gun to have respect on the street' Huge respect Radewoosh :)
 » 5 months ago, # |   -17 TOURIST!!!!!
 » 5 months ago, # |   -13 A tourist written round? immediate upvote of round announcement
 » 5 months ago, # |   +4 Here is the reference https://knowyourmeme.com/memes/perfectly-balanced
 » 5 months ago, # |   +30 Why on weekdays!!
•  » » 5 months ago, # ^ |   +8 Maybe because they want less no of coders with their ratings fall ? :P .... Wait a minute, who's gonna miss Tourist's round xD ?
•  » » 5 months ago, # ^ |   -11 Yes, why let more people to participate. Why would someone do that?
 » 5 months ago, # | ← Rev. 3 →   +12 This contest announcement will definitely going to become the most upvoted contest announcement :) UPD -: It has become the most upvoted contest announcement :)
•  » » 5 months ago, # ^ |   -10 Yes, and after this, tourist might enter in Codeforces Top Contributors list as well :)
•  » » » 5 months ago, # ^ |   0 he was top1 after hello 2018
•  » » » » 5 months ago, # ^ |   -9 I know, I meant by again he will enter the list :P
 » 5 months ago, # | ← Rev. 3 →   -71 This is the first time I registered to participate in tourist's contest on Codeforces. Hope for high rating and a T-shirt as a souvenir.
 » 5 months ago, # | ← Rev. 2 →   -22 tourist !!!
 » 5 months ago, # |   0 Yes, I did nothing wrong. All things should be perfectly balanced.
 » 5 months ago, # |   -48 For normal people tourist = Someone who visits a city, town, or historic site just for the pleasure of exploring it can be described as a tourist. For a programmer tourist = Gennady Korotkevich
 » 5 months ago, # |   +17 Everytime I refresh this blog, I can see an increase in the amount of upvotes.
 » 5 months ago, # |   0 Yeah Finally a tourist round :)
 » 5 months ago, # |   +65 Hope there won't be any DDOS attacks...
 » 5 months ago, # |   0 I hope this round will be rated till the end
 » 5 months ago, # | ← Rev. 3 →   +10 i just upvoted the blog and then refreshed it ...then i was like Wait!..Am i worth 20 votes ?...because the number of upvotes are raised by 20
 » 5 months ago, # | ← Rev. 2 →   -49 <3 <3
•  » » 5 months ago, # ^ | ← Rev. 4 →   -50 <3 <3 <3 <3 <3 <3
•  » » 5 months ago, # ^ | ← Rev. 4 →   -44 Sorry
•  » » » 5 months ago, # ^ |   -60
 » 5 months ago, # | ← Rev. 3 →   +31 Wowwww.. tourist is writer o.0 this is opportunity for Um_nik to break rank 1 CF =))
 » 5 months ago, # | ← Rev. 2 →   +7 I wonder what "perfectly balanced" means?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +30 It means that the difficulty of problems in this round perfectly matches its id.
•  » » 5 months ago, # ^ |   +10 You doesn't even spell it correctly. It should be "wonder"!
•  » » » 5 months ago, # ^ |   +77 *didn't
 » 5 months ago, # |   +17 tourist's round=upvote the announcement
 » 5 months ago, # |   0 great ! so exited for the contest !
 » 5 months ago, # | ← Rev. 2 →   +45
•  » » 5 months ago, # ^ |   0 LOL
 » 5 months ago, # | ← Rev. 2 →   -9 It will be the best contest everI can't wait :)
•  » » 5 months ago, # ^ |   0 But the other writers are also very good!
 » 5 months ago, # | ← Rev. 2 →   -28 Finally, So happy to see that tourist is setting problems after a long time.
 » 5 months ago, # |   -20 "The Round will be perfectly balanced." tourist has surely earned this confidence over the years of his Competitive Programming.
 » 5 months ago, # |   -40 The round will be perfectly balanced. As all things should beSo do you wanna wipe out half of our rating? :3 I'm quite a bit afraid
 » 5 months ago, # |   +147 )
•  » » 5 months ago, # ^ | ← Rev. 2 →   +50 All of them worked very well not only tourist
•  » » » 5 months ago, # ^ |   -10 Relax, I just meant that everybody wants to participate in tourist's round.
•  » » » » 5 months ago, # ^ |   0 ^^ yass bro
•  » » » » 5 months ago, # ^ |   +22 It also meant that you dislike other writers round which is not good.
 » 5 months ago, # |   -19 I wanted to upvote for the contest but downvote for the tags so this balanced perfectly as all things should be. thanosdideverythingwrong but me, I am his greatest creation.
 » 5 months ago, # |   -77 It's tourist!!!The GOD!!!
 » 5 months ago, # |   -19 Will Um_nik overtake tourist in tourist's round?
 » 5 months ago, # | ← Rev. 5 →   +71 As always, Pretests_Passed, Accepted and SuccessfulHackingAttempt shall be welcome to the round. Meanwhile, may _Wrong_Answer, TLE, Runtime_error_, MemoryLimitExceeded and Hacked stay away from our land. And let's all hope that queue, DDos and unrated do not cast doom on this contest.P.S. And the occasional appearance of PresentationError is also less than desirable.
•  » » 5 months ago, # ^ |   +81 How can SuccessfulHackingAttempt and Hacked not be in the same round at the same time?
•  » » 5 months ago, # ^ |   +62 you just mentioned 11 people for a stolen yet terrible joke. good one mate
 » 5 months ago, # |   -35 When I’m done, half of humanity will still exist. Perfectly balanced, as all things should be. --Thanos.
•  » » 5 months ago, # ^ |   -12 Now i got it why they are saying this round perfectly balanced
 » 5 months ago, # |   -21 Tourist=Thanos xD Him be like-I am inevitable
 » 5 months ago, # |   +27 Upvote too.
 » 5 months ago, # |   -15 Hmm, interesting...
 » 5 months ago, # |   -45 When you just comment your opinion or a random comment:
•  » » 5 months ago, # ^ |   +10 Same, I saw some other good comments got massive downvotes, I don't understand why there are so many random downvotes.
•  » » » 5 months ago, # ^ |   0 Yeah.I think so, too.
•  » » » 5 months ago, # ^ |   +6 Well, I mean there is also comments with upvotes too. Votes will be perfectly balanced. As all things should be.
 » 5 months ago, # |   -12 Tourist posting meme is something quite special
 » 5 months ago, # |   -52 Everyone is too much excited for the contest because of tourist.... I am also excited and also frightened about the difficulty level... Anyway hope this will be interesting...
 » 5 months ago, # |   -38 WOW, tourist entered top contributors list
 » 5 months ago, # | ← Rev. 2 →   -59 Wish everyone lots of good luck.
 » 5 months ago, # |   -55 rating++; CBGer are champions :>>>>>>>>>>
 » 5 months ago, # |   -68 I hope this round is not balanced according to tourist, else A be like use segment tree D:
 » 5 months ago, # |   -66 Wish no DDOS attacks.
•  » » 5 months ago, # ^ |   +132
 » 5 months ago, # | ← Rev. 2 →   -19 Writers::TouristWow.....It's Really Amazing
 » 5 months ago, # |   +26 Can upvotes become equal to tourist rating?
 » 5 months ago, # |   -32 Good luck and high rating to all! Can’t wait to see the problems :)
 » 5 months ago, # |   -34 It's the time for Um_nik being the highest rated guy!
 » 5 months ago, # |   -16 tourist nb!!
 » 5 months ago, # |   -16 I really don't know why i left a courteous comment but many people disliked it :< Because of my poor english??
•  » » 5 months ago, # ^ |   +7 it's seem interesting with you but not everybody. you should comment something useful or amusing
•  » » » 5 months ago, # ^ |   0 or amusing How does one know what is amusing to everybody, even top standup comedians don't know if they will bomb or kill.
 » 5 months ago, # |   -19 Awesome!! hoping for good ratings :)
 » 5 months ago, # |   +8 The comment is hidden because of too negative feedback, click here to view it
 » 5 months ago, # |   0 Probably it's gonna be my last round this year, I hope to do well in it, at least to stay in Div. 1
 » 5 months ago, # |   -28 Finally a tourist round :) Yeah Enjoy.........:)
 » 5 months ago, # |   +162 if we have a long queue in the contest
 » 5 months ago, # | ← Rev. 2 →   0 The upvotes just crossed the number of upvotes in Good Bye 2018.
 » 5 months ago, # |   -33
 » 5 months ago, # | ← Rev. 2 →   0 Hopefully this contest is as good as iberico ham made from pigs fed entirely with acorns.
 » 5 months ago, # |   +1 While everyone is waiting for the round to begin, I am also waiting for the editorials. Damn sure, the editorials are going to be short and crisp and with bags full of learning. All the best everyone!
 » 5 months ago, # |   0 I love tourist!
 » 5 months ago, # | ← Rev. 2 →   -22 Wow! This blog makes tourist one of the top contributors.
 » 5 months ago, # |   -37 Omg!! I can't wait!! I bet I'll learn a lot in this round.(hopefully without minus ratings.)
•  » » 5 months ago, # ^ |   +33 Come on. Such comments only suit when immature kids like greens and greys post them. You are orange. Maintain some dignity
•  » » » 5 months ago, # ^ |   -16 Omg!! I can't wait!! I bet I'll learn a lot in this round.(hopefully without minus ratings.)
 » 5 months ago, # |   +1 please , how many problems are prepared?
 » 5 months ago, # |   -11 Oneday, I will precede you, tourist.
•  » » 5 months ago, # ^ |   +72 BREAKING NEWStourist tripled his practice after reading this
•  » » » 5 months ago, # ^ |   0 How making jokes is preferred than encouraging others? Idiots are spreading all the time. Go ahead, do whatever you’re good in! :D
•  » » » » 5 months ago, # ^ |   +39 Okay let me motivate you. Tourist is even sweating head to toe. Go ahead man. Give him a tough fight. My best wishes with you
•  » » » » » 5 months ago, # ^ |   0 Thanks a lot.
 » 5 months ago, # |   +24 What will be the scoring distribution and the contest length?
•  » » 5 months ago, # ^ |   0 Contest length will be 2.5 hours, you can see it in contests page
 » 5 months ago, # |   0 hey guys watch me become grandmaster
 » 5 months ago, # |   -23 Who are these people, that they still don't upvote at this round?
 » 5 months ago, # |   -16 I want to be a Candidate Master in this month :)
 » 5 months ago, # |   -19 He is the chosen one... He will...bring BALANCE...And he is the guy with the high ground.
 » 5 months ago, # |   -9 I hope there won't be a DDOS attacks sincerely.
 » 5 months ago, # |   0 Rank 3 contributors will come soon
 » 5 months ago, # |   +2 i hope problems grammar is clear as this blog :D
 » 5 months ago, # |   +10 Hoping for a CodeForces round, not an AtCoder round :P
•  » » 5 months ago, # ^ |   +28 Hoping for no DDOS, no stuck queue, correct statements, no bugs in test data.
•  » » » 5 months ago, # ^ |   -23 I hope attacker buys a bunch of server and becomes poor and fails in attack eventually
 » 5 months ago, # | ← Rev. 2 →   -8 perfect Hello from tourist
 » 5 months ago, # |   0 "On Wednesday, October 16, 2019 at 15:35UTC+1 we will host Codeforces Global Round 5."Real version:"On Wednesday, October 16, 2019 at 15:35UTC+1 we will lost a lot of points."
 » 5 months ago, # |   +27 After reading the names of the problems in the contest, one realizes what he meant by The round will be perfectly balanced.
 » 5 months ago, # |   0 I am not able to submit my code. It is saying that "you have submitted the exact same code before". Why so? Did anyone facing the same problem?
•  » » 5 months ago, # ^ |   +24 I wrote to you in PM
 » 5 months ago, # |   -28 I misunderstood perfectly balanced as perfectly balanced contest and not perfectly balanced problem statements.
 » 5 months ago, # |   +29 Achievement unlocked: pass pretests on (Harder) problem, fail pretests on (Easier) problem.P.S. I had at least two severe mistakes in my code, still passed C2!
 » 5 months ago, # |   0 How to solve C1 ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 Choose any point, and pair it with point that area will be minimised.
•  » » » 5 months ago, # ^ |   0 Are there any corner cases for this solution? I did exactly the same but failed on the pretest 4.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 I think you might have had integer overflow; I also failed pretest 4 and had that issue.
•  » » 5 months ago, # ^ |   0 sort by x,y,z 1. first if two adjacent(in the sorted list) x,y are same then they can be pair 2. Once all with x,y equal pairs are done processing all adjacent pairs with same x can be pair 3. rest of adjacent two points can be pairneed to wait system test but I solved it this way, hope its correct
•  » » » 5 months ago, # ^ |   +3 me too. but it's WA :( i don't understand
•  » » » » 5 months ago, # ^ |   0 Actually I did the same and I got TLE. I’m surprised
 » 5 months ago, # |   +47 In E, I misunderstood for a while the condition of being perfectly balanced: 'max of depths" instead of "sum of depths". In that case it becomes a true counting problem, which I think is solvable in O(N log N)... If only I faced that version!
•  » » 5 months ago, # ^ |   +14 Are they both not the same thing?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +15 If you only restrict max depth then you get a lot of play with some of the other vertices and can place them suboptimally; for example in the n=10 case for restricting sum of depths you are forced to have the complete binary tree on 7 nodes as your first three layers, and then the last three nodes can be distributed in the fourth layer, but when you only restrict max depth then you can take some of the nodes in the third layer and put them in the fourth layer without messing up the restriction.
•  » » » 5 months ago, # ^ |   +16  6 / \ 3 7 / \ / 2 5 8 / / 1 4 
•  » » » » 5 months ago, # ^ |   +5 yeah sorry my bad. i understood something else.
•  » » 5 months ago, # ^ |   0 ohh i thought it was max depth til now lol
•  » » 5 months ago, # ^ |   0 Did you come up with something that can be solved by FFT?
•  » » » 5 months ago, # ^ |   +5 Exactly.
•  » » » 5 months ago, # ^ |   0 Well, I did and i was wondering why i was getting WA6 and after the contest i realized that it's sum and not max...
•  » » 5 months ago, # ^ |   0 I realized that was sum instead of max only after reading your comment.
 » 5 months ago, # |   0 What is the pretest 4 for C1?
•  » » 5 months ago, # ^ |   0 I initially failed pretest 4 then converted all of variables to long long :D after which it passed the pretests
 » 5 months ago, # |   0 Spent 1h30m debugging C1, I can't pass pretest 5, did anybody have a similar problem? What was the mistake in your case? (I still can't find my error)
•  » » 5 months ago, # ^ |   +10 I have some error and failed test 5. I don't understood what I did wrong. I wrote the stress, stressed some test with $n=50$, then remove some sorts which did nothing in the code, change some variable names and the second solution becomes correct. lol
•  » » 5 months ago, # ^ |   0 I had WA6. I reduced the 3d problem to 2d problem (for each x), and then to 1d problem (for each y). Whenever I could not find a pair from the same vertical line, I was looking for a matching point in another vertical line in the same vertical plane, and then was deleting it. Then some lines did not contain any points, and I was still iterating through them, so that made a mess (=WA).
•  » » 5 months ago, # ^ |   0 Well in my case I had 3 wrong submissions for pretest 5 .. but later on upsolved it.. What I did in my algo was first sorted the points on the basis of x and then y and then z. Then picked out pairs which are on the same line.. then on the same plane and then the remaining I failed pretest 5 because I didn't find the pair on same line correctly. What I did previously was that when in the sorted points list I found a pair I started searching for the next pair with first point ahead of the second point of the found pair. I changed it to first point should be ahead of the first point of the found pair and it worked! Hope it helps!
•  » » » 5 months ago, # ^ |   0 Thanks, I just realized my stupid, stupid mistake, I had forgotten to add a return in one of the cases ...
 » 5 months ago, # |   0 Wasted more than a hour in D because I forgot to return value in query and Codeblocks does not even show that. From now on I will use pre-written codes.
•  » » 5 months ago, # ^ |   0 same problem in C :(
 » 5 months ago, # | ← Rev. 2 →   +18 I think I missed 2 characters for H....................UPD: Yep it was actually just 2 characters from my last minute submission.
 » 5 months ago, # |   0 How to solve B?
•  » » 5 months ago, # ^ |   +1 iterate through all b[i] reverse. keep a variable tmp and each time you iterate, update it to the smallest j such that a[j] corresponding to the b[i] has occured. Now for each b[i], it pays a fine if curresponding a[j] occured after tmp, else update tmp. (curresponding means the choosing j such that a[j]=b[i])
•  » » 5 months ago, # ^ |   0 use two i,j indices for in and out arrays, then if in[i]!= out[j] remove out[j] element from in array and j++otherwise i++,j++ while (y < n - 1) { if (in[x] != out[y]) { auto pos = find(in.begin() + x, in.end(), out[y]); in.erase(pos); ans++; y++; } else { y++; x++; } 
•  » » » 5 months ago, # ^ |   0 You might fail sys tests as it looks n^2.
•  » » » » 5 months ago, # ^ |   0 you are right :(
•  » » » 5 months ago, # ^ |   0 I use a similar approach but i use a set where to keep track of outgoing cars, i check every time if a[i] is already out then i++ otherwise increment j while a[i] != b[j] and adding b[j] in the set and the final answer is the size of the set.Here is my submition.
•  » » » » 5 months ago, # ^ |   0 Thanks! I used set and changed auto pos = find(ALL(s), in[x]); to auto pos = s.find(in[x]);,then it passed.the solution in O(n) is more elegant.
•  » » 5 months ago, # ^ | ← Rev. 4 →   +3 My thought process during the contest went like this:Let t[i] be the time the i-th car entered the tunnel.So for instance: in[i]: 3 5 2 1 4Then t[3] = 0, t[5] = 1, t[2] = 2, and so on..Also keep the opposite array so you can determine which cars to fine, that is: inv[t[i]] = in[i]When the cars leave the tunnel, if there are two cars j and i such that j < i but t[j] > t[i], then that means that even though j entered the tunnel after i, it left the tunnel before i, so in that case car j definitely surpassed car i and j must be fined.Let's create a set s which will contain the entrance times of the cars that already left the tunnel.Now let i be the i-th exiting car, for every car j that's already left the tunnel and hasn't been fined (so they are in s) such that t[j] > t[i], j must be fined and removed from the set (you can do that by using upper_bound).Note this is $O(n\log{}n)$ because you insert and remove each element at most once.But after the contest I realized you actually don't need that set! You can just keep the minimum entrance time :), though at least to me this way of thinking was more natural.
 » 5 months ago, # |   +15 How to solve problem E?
•  » » 5 months ago, # ^ |   +71 ..<----
•  » » » 5 months ago, # ^ |   0 can you please explain?
•  » » 5 months ago, # ^ |   0 Not sure. Thought answer is 1 if $n$ is between $[2^i , 2^i + 2^i/2)$, otherwise 0. got $WA$ on test case 6.
•  » » 5 months ago, # ^ | ← Rev. 6 →   +5 I completed the code at the last moment but couldn't submit in time.Here's my solution in short:Perfectly balanced tree must have the condition that every level, except possible the last, must be completely filled.What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $u$, $\text{key of parent} = u + \text{size of right subtree of } u + 1$This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $u$, $\text{key of parent} + \text{size of left subtree of } u + 1 = u$This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $h$ like this,For height $1$, there is only one tree, one node with no children. For height $2$, there is only one tree, one node with one child on its left and no child on its right.For each height $h$, let's store all the possible trees as a pair $(a,b)$ where $a$ is the number of nodes in the left subtree of the root and $b$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:For height $1$ possible trees: $(0,0)$, possible sizes: $1$For height $2$: $(1,0)$, possible sizes: $2$For height $3$: $(1, 2)$, $(2,2)$, possible sizes: $4$, $5$For height $4$: $(4, 4)$, $(5,4)$, possible sizes: $9$, $10$For height $5$: $(9,10)$, $(10,10)$, possible sizes: $20$, $21$Can you spot the pattern and prove it? For every height $\geq 3$, there are exactly two trees possible.Proof: If for height $i$ we have possible trees $(a,x)$ and $(b,x)$ where $x$ is even, $a$ is even and $b$ is odd, then for height $i+1$, we can have the right child only as $(b,x)$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $(a+x+1,b+x+1)$ and $(b+x+1,b+x+1)$, which can then be replaced with new $A$, $B$ and $X$ having $A = b + x + 1$, $B = a + x + 1$ and $X = b + x + 1$. Thus, we can say that the pattern holds by induction.Base case has $i = 3$, which is satisfied as $a = 2$, $b=1$ and $x=2$.So, find all possible trees till height $\log(\text{max value of n})$ and output $1$ if $n$ is one of those values and output $0$ if it isn't.AC Code: 62737057
•  » » 5 months ago, # ^ |   +2 1 can be used on the left, 2 can be used oh both sides4 can be used on both sides, 5 can be used on the left9 can be used on the left, 10 can be used on both sides20 can be used on both sides, 21 can be used on the leftso int solve(int x) { int cur[] = {1, 2}; int st = 0; while(cur[1] < x) { if(st == 0) { cur[0] = 2 * cur[1]; } else { cur[0] = 2 * cur[0] + 1; } cur[1] = cur[0] + 1; st = 1 - st; } return (x == cur[0] || x == cur[1]) ? 1 : 0; } 
 » 5 months ago, # |   -11 Awesome round tourist. The questions were very clear and easy to understand. This made my day.Thanks a lot!
 » 5 months ago, # |   -8 After a long time most difficult problem of codeforces will be changed.
 » 5 months ago, # |   -6 How to solve D ?
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Here is my solution — First for each element calculate the next number in direction of clock which is less than half of this value. Build minimum segtree over this values. Then iterate elements in non-decreasing order, you can use segtree to get the moves from i then set value at i to infinity.Maybe there is not so coding solution.
 » 5 months ago, # |   +154 Duh, I spent freaking hour on C, it was so hard to come up with for me >_>
•  » » 5 months ago, # ^ |   +91 I am not retard anymore, thanks man for the motivation
•  » » » 5 months ago, # ^ |   +11 Exactly, now I can sleep peacefully at night knowing that I took 25 minutes for a problem that a red needed 1 hour for.
•  » » » » 5 months ago, # ^ |   0 He is exaggerating, he only took 35 minutes
•  » » » » » 5 months ago, # ^ |   +11 No, I am not, I spent fair amount of time thinking on this problem before getting E, probably even more than on E itself.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   -8 .
•  » » 5 months ago, # ^ | ← Rev. 3 →   +16 Same happened with me...finally submitted at last minute. And didn't got time to even read D,E,..
•  » » » 5 months ago, # ^ |   -16 You are lying!! :XD
•  » » 5 months ago, # ^ |   +31 Agreed, C was much harder than DEF for me (at least if you include implementation)
•  » » 5 months ago, # ^ |   +17 Good to know I'm not alone xD
•  » » 5 months ago, # ^ |   0 I thought there are more AC of C than D. Anyway how to solve F guys ?
 » 5 months ago, # |   -41 thanks tourist for the greatest contest of all time. great round whit great tasks!
 » 5 months ago, # |   0 editorial?
 » 5 months ago, # |   +2 We all love G because of the reconstruction ;_;
 » 5 months ago, # |   +3 What is the solution for C1 that fails on C2?
•  » » 5 months ago, # ^ |   +43 For each point, select the closest one? $O(N^2)$, I think.
•  » » 5 months ago, # ^ |   0 You can solve C1 in n^2, but not C2.
•  » » 5 months ago, # ^ |   0 I did this. For each point, iterate over all other remaining points, find the point which forms a cuboid with minimum area, and delete these two. Repeat till no points remain. O(n^2).
 » 5 months ago, # |   0 Are there any easy implementations for C? My approach to C1+C2:For all vertical lines (x = const, y = const) containing points, just pair them (and forget) in order of increase of z. Then, you do not care about z anymore, so just drop all the points on the floor and solve 2d problem (reducing it in the same way to 1d).Looks simple but, damn, took hours to make it work.
•  » » 5 months ago, # ^ |   +18 Well, you can just sort them by z, then y and then x.Then for adjacent points in this sorted set if they have same y and z, pair them.Then you do another round and pair those with same z.Then finally pair the remaining ones.
•  » » » 5 months ago, # ^ |   +5 Haha, it is actually the same approach, but very much easier to implement when phrased like this. Thanks mate!
•  » » 5 months ago, # ^ | ← Rev. 3 →   +9 C2. Simple greedy solution with much sort. Easy implementation. 'Pseudocode': Sort, scan and remove pairs of points which lies on the same line: 1.1. Sort by x,y,z, scan and remove pairs of x1==x2 and y1==y2 1.2. Sort by x,z,y, scan and remove pairs of x1==x2 and z1==z2 1.3. Sort by z,y,x, scan and remove pairs of z1==z2 and y1==y2 Sort, scan and remove pairs of points which lies on the same plain: 2.1. Sort by x,y,z, scan and remove pairs of x1==x2 2.2. Sort by y,x,z, scan and remove pairs of y1==y2 2.3. Sort by z,x,y, scan and remove pairs of z1==z2 Sort x,y,z, and remove all pairs left. Edit. Same as errorgorn's explanation.
 » 5 months ago, # |   0 Problem C: My answer seems to be correct in the first example but in the secound one it apears to me as if it was inverted (first line is at the end etc.). My code is in Java 62732376. (I think in this exact submission I changed the output order therefore the TreeSet in ex 1 apperas to be inverted)My idea is to eliminate the negative values by shifting all values by 10^8. Then I maintain a TreeSet, which is ordered by the manhattan distance to (0,0,0) (Alternatively I would have tryed euclidian distance). Then I go on to say that the first element of the TreeSet together with the last will be contained in the last "Snap" (the next two in the pre-last and so on). This should allways remove two elements that are closest together, hence there is no other element in the bounding box.Is my solution wrong or did I mess something up?
•  » » 5 months ago, # ^ |   0 Nevermind everything works as intended. I just didn't notice.
 » 5 months ago, # |   +34 The queue times today were amazing, best I have ever seen. Thanks Codeforces!
•  » » 5 months ago, # ^ |   +13 one reason can be questions were good, so random submissions were less.
 » 5 months ago, # | ← Rev. 2 →   -46 I am not smart as tourist, but I am smart enough to tell that this statement came out wrong- "The round will be perfectly balanced. As all things should be."(not talking about name of problems). I guess overconfidence is bad for everyone.
•  » » 5 months ago, # ^ |   +79
 » 5 months ago, # |   +24 Anyone use BIT to solve B?
•  » » 5 months ago, # ^ |   +19 I almost did. Used ordered_set, shame on me
•  » » 5 months ago, # ^ |   0 I used segment tree.
•  » » 5 months ago, # ^ |   +8 I did, though it seemed ridiculous to use BIT in B (which is supposed to be at Div2B level)...
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +5 I actually thought the same but BIT is intuitive. Don't want to waste time thinking.And then I found no one use BIT in my room XD.
•  » » » » 5 months ago, # ^ |   +8 I actually had no idea how I can do without BIT until I heard the solution from others lol Was kind of confused...
•  » » » » » 5 months ago, # ^ |   0 Me too,I'm stupid QAQ.
•  » » » » » » 5 months ago, # ^ |   0 QAQ...
 » 5 months ago, # | ← Rev. 2 →   +3 In problem F, if there are no dominoes initially, number of ways for a (h, w) grid, $f(h,w) = f(h, w-1)+\sum_{i=1}^{h}f(i-1,w-2)*f(h-i,w-2)+\sum_{i=1}^{h-1}f(i-1,w-1)*f(h-i-1,w-1)$where $f(h, 0) = 1,f(0, w) = 1$. Is this recursion correct? Edit: Okay, it was wrong.
•  » » 5 months ago, # ^ |   0 Why is it wrong?
•  » » » 5 months ago, # ^ |   +8 The two parts (upper and lower) created by placing a domino in the leftmost column are not independent.
 » 5 months ago, # |   0 I got runtime error on test 1, but it works fine on my pc. It is simiar to this erorr: . Why does this happen? How can I get identically same compilers etc. on my machine? Because this is really frustrating.
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   +3 Have you tried custom invocation?
•  » » » 5 months ago, # ^ |   0 Yes, I am fixing it to work on custom invocation right now, but the contest is over so who cares now. I am just wondering why codeforces judge doesnt work same as mine. How can I configure my compiler to be same as cf custom invocation?
 » 5 months ago, # |   +8 Protip: to win a contest, solve problems quickly and correctly. if you want to see the front of the queue + failures on systests, filter by verdict Rejected and go to the page where the queue ends. You'll also see your solutions there if they fail.
 » 5 months ago, # |   -8 How to solve D ?
•  » » 5 months ago, # ^ |   +5 Can't you wait for editorial
 » 5 months ago, # |   +19 Funny solution for C2 (surprisingly not the one I was unsuccessfully trying to debug for 1h30min...):Use WSPD to solve the all-nearest neighbors problem in $O(n\log n)$. Observe that in the resulting graph, there is always some matching of size $\theta(n)$, which can be found greedily (max. degree is bounded).We can surely print the matching and recursively solve the rest. The complexity of this is actually $O(n\log n)$, since we always divide $n$ by some constant.
•  » » 5 months ago, # ^ |   0 What's WSPD?
 » 5 months ago, # |   +36 tourist making Reds and Oranges go derp on problem A
 » 5 months ago, # | ← Rev. 2 →   +14 The problem-set was indeed balanced.Atleast by their names. XD
 » 5 months ago, # |   +90 Is the heuristic solution intended to solve H?You can kill many heuristic solutions by setting the problem to sort a signed permutation instead of a binary sequence.And I think this problem is also easy to solve by Google and find a paper of it.
•  » » 5 months ago, # ^ |   +37 This was not intended, I probably should've done a better research beforehand, sorry about that.The intended solution uses exactly $n+1$ reversals, and I think it heavily utilizes the fact that it's a binary sequence.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +44 My solution is deterministic and works for sequences over an arbitrarily large alphabet. More specifically, it does the following:Given a sequence of numbers $\pm1$, $\pm2$, ..., $\pm n$ where each absolute value occurs exactly once, we can do the following operation: choose a prefix, reverse it and multiply it by $-1$. Using no more than $2n$ operations I can transform it into $(1, 2, \ldots, n)$.Basically on each move we spend $2$ operations to do one of the following: put some $k$ and $k + 1$ together in this order and then merge them into one block thus reducing the size by $1$ put some $-(k + 1)$ and $-k$ together in this order and then merge them into one block if we have $k$ and $-(k + 1)$ in any order, it's also possible to merge them somehow if we have $n$, we can move it to the end and pop back (after each operation we renumber the whole sequence for convenience, but it is more about the details)When it's not possible to do any of the above, it means that our sequence is exactly $(-1, -2, -3, \ldots, -n)$, and now we can alternate "flipping" prefixes of length $n - 1$ and $n$ ($2n$ operations in total).When we are lost with a sequence of length $1$ we may need to spend one more operation to make it positive. It couldn't occur in the last case, so in this case we spent no more than $2n - 2$ operations and the total number of operations is $2n - 1$. If we ended up transforming the $(-1, -2, -3, \ldots)$ then we spent $2n$ operations in total.
•  » » » » 5 months ago, # ^ |   0 Could you clarify what exactly is done when the sequence is $(-1, -2, \dots, -n)$?
•  » » » » » 5 months ago, # ^ |   +10 Do the operation with prefixes of sizes $n-1$, $n$, $n-1$, $n$, etc. Each pair of operations moves the last number to the beginning, multiplying it by $-1$. Consider it for $n=5$: -1 -2 -3 -4 -5 4 3 2 1 -5 5 -1 -2 -3 -4 3 2 1 -5 -4 4 5 -1 -2 -3 2 1 -5 -4 -3 3 4 5 -1 -2 1 -5 -4 -3 -2 2 3 4 5 -1 -5 -4 -3 -2 -1 1 2 3 4 5
 » 5 months ago, # |   +1 with same code I got WA_on_33 for C1 and AC for C2 :3 and I should have got WA for C2 also :3 have you forgot to add the same cases for C2 which have been used for C1 ? :3
 » 5 months ago, # |   +62 Congratulations to Um_nik on the tenth place!
 » 5 months ago, # |   0 .This was not all that balanced, to be honest. Though, I am not the one to complain, as I was too slow to write F in time.
•  » » 5 months ago, # ^ |   +48 I'll opt for a response that's balanced between "completely balanced" and "not all that balanced": it was quite balanced for a combined division round. There's one problem that can separate the winner, one problem that can separate the top few from the rest of skilled contestants, two that can separate the skilled contestants from the rest, two that can separate roughly div1 from div2 and then some easy shit.The number of solutions in longer contests can be misleading if they span a wider range of points and situations like yours add some variance too.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +10 Well, you're right, it was a good contest. But it was the first time I was participating in a Global Contest and maybe I just like the classic format more, when you have time to think on harder tasks.
•  » » » » 5 months ago, # ^ |   +8 I prefer that format too. I just don't care much about quickly solving easy problems or competing against low-rated people.
 » 5 months ago, # |   +8 300iq, top 10 codeforces !!!
•  » » 5 months ago, # ^ |   +2 nope :P
•  » » 5 months ago, # ^ |   0 top 11((
 » 5 months ago, # |   -40 I think the contest should be rated for everyone who opens contest page not only for those who submit answers. Because one can check the problems and if they look unsolvable for him then he can leave the contest and nothing will happen!!!
•  » » 5 months ago, # ^ |   0 The downvotes depict how much people care about what you think
•  » » » 5 months ago, # ^ |   0 It shows how many people do this cheat!!! :))))
•  » » 5 months ago, # ^ |   +7 I don't think so. Some people, like me, like to open the problems, think about how to do each question in their mind, and then do other things.Also, if you're strong enough, you don't need to care about these people. Every game will be as fair as possible, but it will not be absolutely fair.
 » 5 months ago, # |   +44 when will T-shirts winners announce ?
 » 5 months ago, # |   +7 I let one of my friends borrow my laptop... -198 :):):)
 » 5 months ago, # | ← Rev. 2 →   +18 I'm still unable to view other users' submissions for this contest. Is that intentional? (Submission links appear the way they do when the contest is still in progress.)Edit: now it's working as expected.
•  » » 5 months ago, # ^ |   0 Mike is busy playing Pubg
 » 5 months ago, # |   0 Runtime Error in B on SysTests is not what I exactly expected. I mean I understand that is my fault, but it is really strange.
 » 5 months ago, # |   0 What on earth is this pretest 5 of C1!!!!
 » 5 months ago, # | ← Rev. 2 →   +8 Since the test cases are still hidden, could anybody please help me find what is wrong with my solution for C1? Codeusing ll = long long; using ull = unsigned long long; long long calc(ll xa, ll xb, ll ya, ll yb, ll za, ll zb) { ll xd = xa - xb; ll yd = ya - yb; ll zd = za - zb; return xd * xd + yd * yd + zd * zd; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int N; cin >> N; vector x(N), y(N), z(N); for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> z[i]; vector> ans; vector used(N, false); for (int i = 0; i < N; ++i) { if (used[i]) continue; long long dist = 0; int closest = -1; for (int j = 0; j < N; ++j) { if (i == j || used[j]) continue; const long long cur = calc(x[i], y[i], z[i], x[j], y[j], z[j]); if (closest == -1 || cur < dist) { dist = cur; closest = j; } } ans.push_back({ i, closest }); used[i] = true; used[closest] = true; } for (int i = 0; i < N / 2; ++i) cout << ans[i][0] + 1 << " " << ans[i][1] + 1 << '\n'; return 0; } 
•  » » 5 months ago, # ^ |   +1  const long long cur = calc(x[i], y[i], z[i], x[j], y[j], z[j]); is incorrect, it should be  const long long cur = calc(x[i], x[j], y[i], y[j], z[i], z[j]); 
•  » » » 5 months ago, # ^ |   0 Thanks a lot for your help! What a silly mistake that I couldn't find for hours!
 » 5 months ago, # | ← Rev. 2 →   -10 62736318 62724834 Can anyone explain what is wrong in both submissions?
•  » » 5 months ago, # ^ |   +1 If you want to divide a negative number by 2, doing (x >> 1) is wrong ._. It will break the structure of the int, for example, it will become positive.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 62747147 then why this one passed?
•  » » » » 5 months ago, # ^ |   0 Similar thing happened to me.. i think it's because float has -0 .. so without converting to int it can print -0.. which is not int... int has no -0, only 0. You can test it by giving -1 as input multiple times.
•  » » » » 5 months ago, # ^ |   +1 This is interesting. I was wrong.Ok, so it was because of double 0.0 was outputted as "-0". It happens.
 » 5 months ago, # |   +8 I'm really comfuse that I only change vector to array then TLE bacame AC on problem D, can anyone help me. TLE AC
•  » » 4 months ago, # ^ |   +8 (this comment is old, but in case you didn't figure that out) It's simply an out-of-bound write to array. The ans array is written to at indices > n+5.(It took me way too long to realize that it triggers undefined behavior, while if vector is used for ans then it would just cause WA and Codeforces can run the diagnostic.)When v is a local array, writing to indices past n in ans array would actually write to indices approx. i-n` in array v (because of how GCC implement VLA), so it doesn't affect the result.
•  » » » 4 months ago, # ^ |   0 Thanks you for looking my code and reply, that was really hard to figure out.
»
5 months ago, # |
+102

Finally, people who will receive T-shirts!

List place Contest Rank Name
2 1237 2 Petr
3 1237 3 300iq
4 1237 4 ecnerwala
5 1237 5 RomaWhite
6 1237 6 zemen
7 1237 7 izban
8 1237 8 mnbvmar
9 1237 9 rng_58
10 1237 10 Um_nik
11 1237 11 maroonrk
12 1237 12 LHiC
13 1237 13 wxhtxdy
14 1237 14 ksun48
15 1237 15 krijgertje
16 1237 16 Golovanov399
17 1237 17 tmw168_orz
18 1237 18 hbi1998
19 1237 19 bip_oqq
20 1237 20 yosupo
21 1237 21 zdolna_kaczka
22 1237 22 beginend
23 1237 23 pashka
24 1237 24 betrue12
25 1237 25 Cinro_9baka
26 1237 26 Egor
27 1237 27 zscoder
28 1237 28 rainbow_tree
29 1237 29 DmitryGrigorev
30 1237 30 dreamoon_love_AA
45 1237 45 nikolapesic2802
56 1237 55 86723zyxjf
106 1237 106 train_driver
127 1237 127 socketnaut
145 1237 145 codelegend
149 1237 149 user202729_
179 1237 179 ei133333
215 1237 215 RobeZH
225 1237 225 buko
242 1237 242 Simon
312 1237 312 hamlet
333 1237 333 777777777
419 1237 419 seekluna_xrc
432 1237 431 dilsonguim
439 1237 439 Okrut
455 1237 455 Infinityedge
481 1237 481 UtahaSenpai
497 1237 497 hocky
498 1237 498 anayk
•  » » 5 months ago, # ^ |   +30 Great!
•  » » » 5 months ago, # ^ |   +28 Congrats
•  » » 5 months ago, # ^ |   +18 Wow! I can't believe I won a T-shirt. How and when do we receive it?
•  » » » 5 months ago, # ^ |   +1 Our team will contact you pretty soon, no worries.
•  » » » » 5 months ago, # ^ |   0 Cool, thanks.
•  » » 5 months ago, # ^ |   +24 Alhamdulillah
•  » » 5 months ago, # ^ |   0 Wow!
 » 5 months ago, # | ← Rev. 2 →   0 {Del}
 » 5 months ago, # |   0 Did anyone use Kd tree to solve C2?
•  » » 5 months ago, # ^ |   0 Can you elaborate more on how to use Kd tree for this problem?
•  » » » 5 months ago, # ^ |   0 Yes, it can be used to solve C2.Just use Kd tree to get the closest point for each point and pair them together, there are O(logn) phases and each phase is O(N * sqrt(N)) or O(N * logN) if you assume points are randomly distributed. Overall the complexity is O(N * sqrt(N)) or O(N * logN) because the number of points gets at least halved in a phase.