### fchirica's blog

By fchirica, 6 years ago, ,

Hello everyone!

We invite you to participate at Codeforces Round #225, scheduled Monday, 20th January at 7:30 PM MSK. This is the third round I coauthor, along with Codeforces Round #198 (Div. 1) (and of course Div. 2 version of contest) and Codeforces Round #191 (Div. 2).

If you recall my old rounds, you'll see that main character is Iahub. The other writer of this round is... Iahub... the real person corresponding to "Iahub" character. Let me introduce you to Rares Buhai (rares.buhai). He's the author of Div. 2 C / Div. 1 A, Div. 1 D and Div. 1 E. You can expect those problems to be interesting, coming from a 2 times IOI gold medalist (being allowed to participate 2 more times). All other problems are created by me. I like them, but I wouldn't be objective if I said that they're interesting. Let's see if someone will think so after the contest :)

Like last time, I'll give you a little spoiler about the tasks. We tried to make the problem set as varied as possible. In order to get a good rank, one needs to be good at "ad hoc" problems as well as have good algorithmic knowledge.

As always, thanks to MikeMirzayanov for Codeforces platform, to Delinur for translating tasks, to Gerald for helping us prepare the round and to DamianS and ll931110 for testing it.

We wish everyone high rating and to have fun!

UPD Score distribution:

Division 1: 500 — 1500 — 1500 — 2000 — 2500

Division 2: 500 — 1000 — 1500 — 2500 — 2500

UPD Contest is over! Thanks for everyone who participated! I need to say we're impressed of your creative and totally unexpected solutions for Division 1 D.

Div. 1 winners:

Div. 2 winners:

UPD Editorial

• +353

 » 6 years ago, # |   -15 is the score distribution going to be dynamic ?
 » 6 years ago, # |   +15 Hm, what is an "ad hoc" problem?
•  » » 6 years ago, # ^ |   +1 It means that the problem has a unique, uncommon or unusual solution.
•  » » 6 years ago, # ^ |   +11 Problem that depend only on observation , doesn't need a special algorithm to be solved with
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +8 Majority of round 225 problems solved by greedy techniqe
•  » » 6 years ago, # ^ |   +11 problems which are not based on any particular algorithm, and usually based on observations and deduction of patterns.
•  » » 6 years ago, # ^ |   +21 Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.Of course, this makes the problems the fun ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.I took this definition from USACO Training Pages. I recommend it strongly if you want to improve your level of problem solving.
 » 6 years ago, # |   +14 It' s my first Div.1 contest, looking forward to it. And thanks to the authors, we can have another contest in a few days:)
 » 6 years ago, # |   0 Another round which is not during weekend :(.
•  » » 6 years ago, # ^ |   -21 But its at night (in India) so doesn't matter to me!
•  » » 6 years ago, # ^ |   0 If you're from the US, it's Martin Luther King Day, so there's no work or school.
 » 6 years ago, # |   +50 Cool! Another round with Romanian problem setters. I can't wait to participate. Will Iahub also be the main character this time, too? :) Or will you also have a Sufle character? :) [ the reverse of elfus ]
•  » » 6 years ago, # ^ |   +27 Thank you for the hint! It's just now when I realize what Iahub means (the reverse of Buhai).
 » 6 years ago, # |   -15 Good Luck to everyone!
 » 6 years ago, # |   0 Seems that it is going to be a very interesting round. Good luck to everyone..
 » 6 years ago, # |   +67 Div1 500, 1500, 1500 ?!I was aiming at solving A & B now I have to reconsider this :D :D :D
•  » » 6 years ago, # ^ |   +15 * insert a Courage Wolf picture *solve A, B and C instead
 » 6 years ago, # |   +6 A round with a very interesting score distribution... It seems that I'll back to Div2 again :)
 » 6 years ago, # |   +23 Do you wish good luck to everyone?
•  » » 6 years ago, # ^ |   +17 I think the publishing of such link at the contest-blog will reduce the number of similar comments :)
•  » » » 6 years ago, # ^ |   +8 Yeah, this is a sarcasm, and at the same time spam reducer :D
•  » » 6 years ago, # ^ |   +4 31% No?? LOL :D
•  » » » 6 years ago, # ^ |   +3 When nobody know who you are , you show your real face :D
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +4 So every body should ask him self , "What I did when I playing GTA "?
 » 6 years ago, # |   -31 where is the link for problems ofRound#225
•  » » 6 years ago, # ^ |   +8 Kindly, read the Help section. If you don't find your answer in it, feel free to ask :)http://codeforces.com/help
 » 6 years ago, # |   +25 Finally, a round where we can see the score distribution earlier than expected....
 » 6 years ago, # |   -18 GL & HF!))
 » 6 years ago, # |   0 I hadn't found any broken solution. Maybe pretests are too strong?
•  » » 6 years ago, # ^ |   0 yes...i am trapped in C....
•  » » 6 years ago, # ^ |   0 three successful hacks, all from the same room.
 » 6 years ago, # | ← Rev. 2 →   -7 NO HACKS for div2! :o
•  » » 6 years ago, # ^ |   0 Actually there are. I suppose most of the solutions of div1 B/div2 D will fail.
 » 6 years ago, # |   0 Problem C was interesting. Same for D where the answer was only 2n — 2 or -1. B was too boring a problem to waste time though.
•  » » 6 years ago, # ^ |   -13 I believe Answer is not always 2n-2 or -1 .#... .#.#. .#.#. .#.#. ...#. 
•  » » » 6 years ago, # ^ |   +36 You are not allowed to go up or left.
•  » » » » 6 years ago, # ^ |   +25 Thanks. I hope some day I'll learn how to read statements
•  » » » » » 6 years ago, # ^ |   +23 i feel you bro
•  » » » 6 years ago, # ^ |   +8 always, because you can't move up and left
•  » » » 6 years ago, # ^ |   +4 from (i, j) we can go only to (i+1, j) and (i, j+1)
•  » » » 6 years ago, # ^ |   +4 You cannot walk up
•  » » » 6 years ago, # ^ |   +10 the answer for that case is -1 , isn't it?
•  » » » » 6 years ago, # ^ |   0 yeah, you're right
 » 6 years ago, # |   +2 was it a very hard contest for you or just me??
•  » » 6 years ago, # ^ |   +4 I think it was good contest for me.I actually got quite much time to think on problem C which isn't usual for me in the contests.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 this is how a contest should be. neither too easy nor too hard. well done elfus0.PS: next time, try to improve the gradient of difficulty of the problems. that was the only thing lacking today. :)
 » 6 years ago, # |   0 Division 2B, it is intended that you can simply print every single pair?
•  » » 6 years ago, # ^ |   0 yaa..more like printing optimized bubble sort steps will do it within the limits of pairs allowed.
 » 6 years ago, # |   +13 what a terrible system test fail rate on Div 1 B...
 » 6 years ago, # | ← Rev. 2 →   -14 div 2 — A is too basic
•  » » 6 years ago, # ^ |   0 it always is! those problems is designed so that every participant can get it accepted, even if he/she does it after one or two wrong submissions. :D
 » 6 years ago, # |   +9 Very nice contest :)! The problems were very interesting and fun to solve!
 » 6 years ago, # |   0 This round taught me it's more important to think more than code faster! I could have much more time and points if I had thought some minutes more! Thanks for good problemset ;)
 » 6 years ago, # |   0 Wow, system test for div 2 D was powerful!
•  » » 6 years ago, # ^ |   0 The whole system test was powerful :) I've amazed the speed. Maybe need some sleep to be more interesting :)
 » 6 years ago, # |   +21 What's the point of additional constraints in div1E? It can be done in O(2K + N) regardless of how long are given strings. My solution passes in 280 ms.
•  » » 6 years ago, # ^ |   +3 Cool! Can you share your solution?
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +8 Suppose we have an array a of length 2K. We want to construct array b so that bi = . Partite a into two arrays a' = a[0..2K - 1) and a" = a[2K - 1..2K) and solve the problem recursively for them, obtain arrays b' and b". bi = b'i if i < 2K - 1 and bi = b'i - 2K - 1 + b"i - 2K - 1 otherwise. This is clearly a linear solution. Actually, this is a O(K2K) solution, my bad.
•  » » » » 6 years ago, # ^ |   +8 As I can see, it is k*2^k solution as we have k levels with O(2^k) merge for each of them. I have exactly the same soltuion but I do it in non-recursive way. 5753388
•  » » 6 years ago, # ^ |   0 Well, the "easy" solution I guess was O(N+2^K*K^3) — by precomputing the amount of words with all possible combinations of 1, 2 or 3 letters and then solving each query with inclusion-exclusion formula, but I managed to optimize it to O(N+2^K*K^2) by using some previous results and that was enough. But this solution heavily uses that the length is up to 3, so that we can stop inclusion-exclusion formula when there are more than 3 bits on.
 » 6 years ago, # |   +8 I've solved the Div1-C with heavy-light decomposition. This is the first time when I use this in contest :) . Is there any simpler solution?
•  » » 6 years ago, # ^ |   +3 I use heavy-light decomposition too.
•  » » 6 years ago, # ^ |   +7 It is enough to decompose the tree in such a way that every subtree is represented by continuous interval. You can use a simple pre-order DFS and build a standard segment tree on top of the resulting sequence (or Fenwick tree).
•  » » » 6 years ago, # ^ |   0 Ohh I see. Thank you!
•  » » » 6 years ago, # ^ |   +4 but if u do that, how will u know which nodes to add val and which nodes to add -val?
•  » » » » 6 years ago, # ^ |   0 I split the tree into 2. Something like node.edges.addAll(all node's children's children) This way, by skipping 2 layer each time, one tree will be a + val, the other will be — valhttp://codeforces.com/contest/383/submission/5755796
•  » » 6 years ago, # ^ |   +6 I converted the tree to linear brackets sequence. For each node, record the smallest begin time and largest the finish time of all the nodes with odd depth of the subtree. Also Record the even part.After that, just use segment tree to implement the add operation and the query operation.
 » 6 years ago, # |   +4 There is NO Accepted Solution for B in my room (16) ! I haven't seen any problem like this before!
 » 6 years ago, # |   +2 Really weak pretests for problem B Div1!
•  » » 6 years ago, # ^ |   0 actually, i dont think the pretests were weak. it's just that the system tests were really strong!
•  » » 6 years ago, # ^ |   0 There is no weak pretests for problem B div1, there is just a lot of weak solutions :)
 » 6 years ago, # | ← Rev. 2 →   0 How exactly does -50 on wrong pretests work ? Will it only get reduced from that problem if we actually submit an answer for that problem otherwise not ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Only if you pass the system tests on that problem. And the hacks on it should always count.
•  » » 6 years ago, # ^ |   0 Each wrong answer on pretests gives you -50 score for that problem , but you will only get the penalty if you actually manage to solve the problem correctly, otherwise your score for that problem is 0.
•  » » 6 years ago, # ^ |   0 You will get the penalty only if you get AC on that same problem later.
 » 6 years ago, # |   +6 I was stuck in B, and didn't take a look at D until there's half an hour left. This taught me to read all the problems before thinking.It's the first time I solve D :)
•  » » 6 years ago, # ^ |   +21 I took an unnecessarily long time on C — I could solve it quickly, but silly mistakes appeared. After I solved C, I solved D in about 20 minutes.D and B should've been swapped. The idea isn't really hard, but it's prone to mistakes.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -8 Perhaps D is D because it is not used in Div 2, while B is.
 » 6 years ago, # |   0 There is 150 test cases for B! But All of the failures are on tests less than 13!! :)) I think 13 test cases were enough!
 » 6 years ago, # |   0 thank you for great contest, but pretest was a bit weak on problem B div 1.
 » 6 years ago, # |   0 Hello.. I just want to ask something.. why my code got Wrong Answer on Problem A?? When I compile it from my laptop, it gives me the right answer.. And when I submit another for practice and just delete some STL include but my main code is still the same, it keeps get Wrong Answer and the Wrong Answer's test case is not the same.. First it is on Case 8, then second on case 7, the third one on Case 9.. What is going on???
•  » » 6 years ago, # ^ |   0 you are trying to use element with indicies -1 and n in your array, Besides, you are using data in that array that was never initialized
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I modified your code and got AC 5759068. Hope this help you understand.If i == 0 then you don't need to check peta[i-1][j], the same is for j. And since you fill the blank from small ij's, you don't have to check peta[i+1][j] and peta[i][j+1] either.
•  » » » 6 years ago, # ^ |   +3 Oh, now I understand.. Thanks, jonathan79717.. :-)
 » 6 years ago, # |   0 what was the tricky case for problem D div 2 ?!
•  » » 6 years ago, # ^ | ← Rev. 5 →   +5 for me it was this case ...... #..... ...... .##### ...... ...... i have to go left at some point which is not a valid move
•  » » » 6 years ago, # ^ |   0 hmm i don't think it was the fail case to my code since i used STL set container , hmm i would like to know what was the tricky for test 13 :'(
•  » » » 6 years ago, # ^ |   0 lol i see why i fail ;-; , thanks!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Something like this .#... .#.#. .#.#. .#.#. ...#. 
•  » » » 6 years ago, # ^ |   0 actually my code works for that case :'c
•  » » » » 6 years ago, # ^ |   0 Try new one
•  » » » » » 6 years ago, # ^ |   0 thanks so much i see why i fail...
 » 6 years ago, # |   +5 will there be any editorials for the problems? and when will be the ratings updated?
 » 6 years ago, # |   0 I got WA on pretest 2 problem B div2 and I lost 50 point :( . I am sure I saw this happened before for some participant and they didn't lose points for WA on given cases !!
•  » » 6 years ago, # ^ |   +1 There is no penalty only for pretest 1.
•  » » 6 years ago, # ^ |   0 You don't lose points only if you'v got WA on the first sample. not all samples.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 that participant probably received WA#1 or RE#1. submissions that fail on the first pretest do not receive a penalty.
•  » » » 6 years ago, # ^ |   0 Thank you for explaining .
 » 6 years ago, # |   0 Sad to get green again...T_T
•  » » 6 years ago, # ^ |   0 you are going to lose atmost 90 rating points xD , the same happened to me in the last contest
•  » » » 6 years ago, # ^ |   +1 I'll be back next contest...
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   -10 no you won't. you're just too__weak! :DPS: i was just kidding. hope u didn't take this seriously. :P
 » 6 years ago, # |   +24 Thank you for the contest, and, specifically, for the Div 1/D task.
•  » » 6 years ago, # ^ |   +5 For me, D was the least interesting xD
•  » » » 6 years ago, # ^ |   0 Considering that the reason I found it beautiful was because of how well the simple solution is hidden in the task, I do understand your point of view that if you haven't solved it, you might find it the least interesting problem of the lot.
•  » » » » 6 years ago, # ^ |   0 Let's not jump to conclusions here :) I began solving it 10 minutes before the end of the contest and finished it 1 minute after the end. So yeah, not interesting.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +13 OK, sorry, I thought that I had looked at upsolving results and somehow failed.Anyway, yeah, I most likely enjoyed it was because I didn't stumble upon that idea immediately. If one manages to immediately get to it out, I can even more see how it would be not interesting at all.Or maybe I just liked the problem so much with no logical reasoning behind it.And by the way, congratulations with the new colour!
 » 6 years ago, # |   0 I tried to hack this solution generating the worst case for bubble sort, in which it should TLE, at least in my opinion. Am I wrong ?
»
6 years ago, # |
+5

Nice contest. Good joob elfus&iahub.

# mlc

 » 6 years ago, # | ← Rev. 2 →   0 Does anyone has an idea why my program output for the first example test case in the problem B (Div 2) fails?http://codeforces.com/contest/384/submission/5758977It looks like as if it was correct..
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 initial state : 1 3 2 5 4 1 4 3 2 5 step 1 (pair 2 3): 1 2 3 5 4 1 3 4 2 5 step 2 (pair 2 4): 1 2 3 5 4 ( 5 > 2 no swap) 1 2 4 3 5 step 3 (pair 4 5): 1 2 3 4 5 (sorted) 1 2 4 3 5 ( 5 > 3 no swap) the second array is not sorted at the end ! 
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 for first index in output, your array becomes1 2 3 5 4 1 3 4 2 5for next index in output, your array becomes1 2 3 5 4 1 2 4 3 5for last index in output, your array becomes1 2 3 4 5 1 2 4 3 5Now see, second array is not sorted in ascending order. So it's wrong...
 » 6 years ago, # |   0 I didn't like Div2-B. But, C was an awesome problem.And the pretests of A,B,C was strong enough. Technically The system test of Div2-D was the strongest I have ever seen!!!Thanks to the authors for a nice contest. :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Div2-B is funny :)Show my solution: 5752434
•  » » » 6 years ago, # ^ |   0 Yes! With the restriction of output, you can easily realize that bubble-sort will always satisfy it. And generating the code in just a few minutes, like mine. -> 5754578
 » 6 years ago, # |   0 I just study C about 3 months so I feel very worst :(( . Can you share code of Div 2 for me ? My email: nhtrung13clc@gmail.com. Tks all :)
•  » » 6 years ago, # ^ |   +10 you can see anybody's solution ,just click the submission id :p
 » 6 years ago, # |   0 ratings are not updated yet :(
•  » » 6 years ago, # ^ |   0 Mine is updated. Yours should be soon.
•  » » 6 years ago, # ^ |   0 Rating has already updated!
 » 6 years ago, # |   0 Who's the lucker here???)))
•  » » 6 years ago, # ^ |   +12 Nice! I had +3 and became yellow :D
•  » » 6 years ago, # ^ |   0 Me :D
 » 6 years ago, # |   +4 Yes! 266 Points added! Any way, I still think that Div2-D is too tricky to solve. And I feel lucky that I solved Problem E first. :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +14 ur name is FastAC. no wonder u solved it first :D
 » 6 years ago, # |   +6 nice contest !!!!
 » 6 years ago, # | ← Rev. 2 →   0 What a good luck! One Codeforces round that I didn't [have time to] participate in, and exactly in this one, most of my div 2 friends got >= +100!
 » 6 years ago, # |   0 O(sqrt(N)*N) get accepted for div1 C! 5762148
•  » » 6 years ago, # ^ |   +14 Oh, if only you knew how many problems on trees I've solved in ...It's nothing rare, if the time limits aren't tight. Solutions in often have large constants, caused by the use of segment trees or some more complex operations. Simpler decompositions have worse complexity, but small constants, so they aren't much slower.
 » 6 years ago, # |   -9 Where is the Tutorial?
•  » » 6 years ago, # ^ |   +2
•  » » » 6 years ago, # ^ |   0 thank you~
 » 6 years ago, # | ← Rev. 4 →   -15 Thanks
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 nice contest