### Serega's blog

By Serega, 6 years ago, translation, ,

Hello everyone!

November 14, 19:30 MSK will take place Codeforces Round #212 (Div. 2), which was prepared by group of authors from Saratov State University: Artem Sedanov (FunkyCat), Sergey Sukhov (Serega), Olga Chikatueva (Helga), Dmitriy Zaycev (My-my).

We thank coordinator of Codeforces rounds Gerald Agapov (Gerald) for useful hints and Maria Belova (delinur) for translation of problem's statements into English.

Good luck and high rating to all!

UPD1. In this round will be used dynamic scoring system (see here).

UPD2. Tutorial is published here.

UPD3. Rating is updated. We congratulate the winners who solved four problems:

• +115

 » 6 years ago, # |   0 Sereja's round :D Hoping for a good increase again !!! Good-luck to all ...
•  » » 6 years ago, # ^ |   +5 Sorry But this is Sereja http://codeforces.com/profile/SerejaNotice the name difference.Still hoping for an increase in rating :D
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +11 Yeah, that was weird to see Sereja being violet Serega.
 » 6 years ago, # |   +8 Hope that we have an interesting contest. ^^
 » 6 years ago, # |   +8 Problem statements of previous Serega's contest were horrible! I hope problem statements will be easy to understand!
•  » » 6 years ago, # ^ |   0 I think so! I feel tonight it will be a hard work especially for the poor English participants..
 » 6 years ago, # |   0 I hope the problems will short for understand :)
 » 6 years ago, # |   +1 It seems that the final judge in this contest is not sorted by submitting time !
 » 6 years ago, # |   +15 Problem C and Problem E. Waiting eagerly for their editorial. Especially E, that was really beautiful.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 In E you can use min-cost-max-flow algorithm for some graph. Tutorial will be published soon.
 » 6 years ago, # |   0 Problem D can be solved with Union-Find, right?
•  » » 6 years ago, # ^ |   +1 I think we can use Heap to solve D.
•  » » 6 years ago, # ^ |   +1 Pretty sure the solution for D is a combination of greedy (for choice of roads) + implementation of choice (union-find, heap...)
•  » » » 6 years ago, # ^ |   0 You're right. I solved that way. But I had 2 stupid bugs that made my solution fail.
 » 6 years ago, # |   0 This indeed was a fun contest. Problems were nice, they were composed in a way that it would be likely for contestants to make some mistakes which later could be hacked. :) Can anyone tell if third problem was solvable with a segment tree. That may not be the optimal way, but I guess it would pass.
•  » » 6 years ago, # ^ |   -11 Kos nagoo ! :|
 » 6 years ago, # |   +13 Most of the solutions for problem B got accepted only because of pure luck. Solutions that use: if(s[0]==1||s[m-1]==n) { cout<<"NO\n"; return 0; }should get 'Runtime error' becase m can be 0 :).
•  » » 6 years ago, # ^ |   0 You're wrong at least because almost all of theese people check this case like  if(!m){  puts("YES");  return 0; }
•  » » » 6 years ago, # ^ |   0 I am afraid I am not wrong :). Please check my room: http://codeforces.com/contest/362/room/44Positions 1, 3 and 7 have this error. There are also others with this problem in the same room :). Accessing v[-1] memory is undefined behavior :).
•  » » » » 6 years ago, # ^ |   0 Luckers :) It must be runtime, really.
•  » » 6 years ago, # ^ |   +1 I tried to hack a solution using this but it didn't work. It depends on what value is at address s-1.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 this case is covered, check Test #8
•  » » » 6 years ago, # ^ |   +1 I got AC without handling m=0 as sorin said "It depends on what value is at address s-1"
•  » » » 6 years ago, # ^ |   0 Correct.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 I do think that if(s[0]==1||s[m-1]==n) { cout<<"NO\n"; return 0; } would pass, but (saw it while reviewing my own code) if(s[m-1]==n||s[0]==1) { cout<<"NO\n"; return 0; } could cause RTE. If the first case is true, it won't produces a positive output without testing the another.
 » 6 years ago, # |   0 Good Problem set, with the wonderful dynamic scoring :) #loved it
 » 6 years ago, # | ← Rev. 4 →   0 in problem B, for the simple test case 1 1 1, which means that he does not have to make any move. My code gives output "YES", i.e. it is reachable, but the answer is "NO", why? I still think the answer should be "NO", for he managed to reach the nth stair. please help me understand if i am going wrong.
•  » » 6 years ago, # ^ |   0 read problem statment carefully"One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only."
•  » » » 6 years ago, # ^ |   0 but for that case, he does not have to step, he was standing on the dirty stair.
•  » » » » 6 years ago, # ^ |   0 he got 1 stair which is dirty and he already step on it , how do you want to find a path with clean stairs only if the starting stair is dirty !!! read the problem again
•  » » » » » 6 years ago, # ^ |   0 and his path should start from the next stair he steps to. I knowingly wrote in my code that if n equals 1, then he manages to reach.
•  » » » » » » 6 years ago, # ^ |   0 he musr start from the stair 1 and stop at stair n , so if one of them is dirty he can not find a path
•  » » » » » » » 6 years ago, # ^ |   0 I still think I should be correct, but am bound to accept. thank you BAHOSAIN
•  » » » » » » » » 6 years ago, # ^ |   0 u r welcome
 » 6 years ago, # |   +3 In problem A, I tried marking every position K1 can go in matrix a,and every position K1 can go in matrix b. Then I checked for every post if(k1[i][j] && k2[i][j] && original!='#') . why did this algo gave wrong answer in test case 7?
•  » » 6 years ago, # ^ |   0 This is because they have to meet at the same time. An example is the test given in the statement.
•  » » 6 years ago, # ^ |   0 Because that does not take into account the fact that the knights have to move at the same time.
•  » » 6 years ago, # ^ |   0 About problem A, I also want to ask for why the first board of test case 6 can output 'YES'? Could anyone help to explain it?
•  » » 6 years ago, # ^ |   +3 Check out this case: ........ ........ ........ ........ ........ ..K..... ........ K....... Since the knighs move simultaneously they can never reach the same position. For every possible position they can reach one knight has to make an odd number of moves to reach that position while the other has to make an even number of moves. That means they can never be at the same position.
•  » » » 6 years ago, # ^ |   0 Please tell me, how half-knights can meet on this map? K###K### ######## #######. #.###### ######## ######## ######## #######. 
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +7 .###.### ######## ##K####. #.###### ######## ######## ######## #######. .###K### ######## #######. #.###### ######## ######## ######## #######. Half-knights in both cases are on the one square.
•  » » » » » 6 years ago, # ^ |   0 oh, they can meet at starting position...thanks
•  » » » » » 6 years ago, # ^ |   0 Thanks,I got it. Just neglecting to take 'K'-value-position into account. What a pity.
•  » » » » » » 6 years ago, # ^ |   +1 Yes the bad squares had no use. If they can be on same place they can be on start pos.
•  » » » » 6 years ago, # ^ |   0 both of them go to 2, 2 then both of them go to 0, 0
 » 6 years ago, # |   -9 UPD4: Ratings is fucked!
•  » » 6 years ago, # ^ | ← Rev. 3 →   -12 UPD5: Ratings is updated again.UPD6: Ratings is fucked again.This is an infinitive loop :|
 » 6 years ago, # |   -14 k = 0; new_rating = old_rating + k;
 » 6 years ago, # |   +17 In problem B, problem statement says, "The second line contains m different space-separated integers...". But actual test cases did not have the second line if m = 0. That's reason why many answers written in script language got RE.
•  » » 6 years ago, # ^ |   0 Why it is so important to have the second line in test case if m=0 ? I believe that m=0 is enough to check if solution is correct for this case.
•  » » » 6 years ago, # ^ |   +16 Script language like Python or Ruby, there are no easy way to read integer tokens like scanf or iostream, so programs must handle input by lines and split them into integer list.Please compare these two submissions. 5103785 5103965
•  » » 6 years ago, # ^ |   0 Yes, I run into the same problem. I spend half an hour to check my program. Only after the contest do I know where the problem is with practice mode.
 » 6 years ago, # |   +1 Ratings are back ... yeyy, +168.
•  » » 6 years ago, # ^ |   0 Old rating again!
 » 6 years ago, # |   -6 In problem C n^2 solutions have passed but my (n^2)(lg n) gave tle. :( . It passed the test case with n=4500 but gave tle with n=5000.
 » 6 years ago, # |   +1 Does any one except me used DFS for A ?!I didn't understand the main solution but simulation worked perfectly ;) Code
•  » » 6 years ago, # ^ |   +1 My solution: if semiknights can meet in first step then "YES" and "NO" otherwise.
•  » » 6 years ago, # ^ |   +1 I use a BFS.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 a better way is to check if (x2-x) mod 4=0 & (y2-y) mod 4=0 then the answer is "Yes" otherwise "No" :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 a much easier algo is just to check if abs(x2-x1) and abs(y2-y1) are both divisible by 4, then answer is YES. if either of them not then NO.
 » 6 years ago, # |   +1 I fail in the most simple test case, a graph with one node.
 » 6 years ago, # |   0 Great round!
 » 6 years ago, # | ← Rev. 2 →   0 question of problem C: the third test data: 5 1 3 0 4 2 It can swap(0,2) to get '0 3 1 4 2',so this premutation only needs 3 times of 'swap',but why the standard answer is 4 ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 The third test data is 5 1 3 4 0 2 but not 5 1 3 0 4 2.
•  » » » 6 years ago, # ^ |   0 Oh,thx..I have made a mistake.
•  » » » » 6 years ago, # ^ |   -24 Kos nagoo !
 » 6 years ago, # |   +4 It would have better if pretests had less details especially at problem B like dirtiness of first or last stair ...
 » 6 years ago, # | ← Rev. 2 →   -8 These problems seem too hard for div2.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 EDIT: Deleted (I mistook the thread for round 214 :D)Well, E was quite hard, and A was definitely much harder than B. Other than that, it was all right.
•  » » » 6 years ago, # ^ |   0 In fact ,I mean A is a trap, and many people delay on it.