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:

Sereja's round :D Hoping for a good increase again !!! Good-luck to all ...

Sorry But this is Sereja http://codeforces.com/profile/Sereja

Notice the name difference.

Still hoping for an increase in rating :D

Yeah, that was weird to see

~~Sereja being violet~~Serega.Hope that we have an interesting contest. ^^

Problem statements of previous Serega's contest were horrible! I hope problem statements will be easy to understand!

I think so! I feel tonight it will be a hard work especially for the poor English participants..

I hope the problems will short for understand :)

It seems that the final judge in this contest is not sorted by submitting time !

Problem C and Problem E. Waiting eagerly for their editorial. Especially E, that was really beautiful.

In E you can use min-cost-max-flow algorithm for some graph. Tutorial will be published soon.

Problem D can be solved with Union-Find, right?

I think we can use Heap to solve D.

Pretty sure the solution for D is a combination of greedy (for choice of roads) + implementation of choice (union-find, heap...)

You're right. I solved that way. But I had 2 stupid bugs that made my solution fail.

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.

Kos nagoo ! :|

Most of the solutions for problem B got accepted only because of pure luck. Solutions that use:

should get 'Runtime error' becase m can be 0 :).

You're wrong at least because almost all of theese people check this case like

``if(!m){` ` puts("YES");` ` return 0;` `}``

I am afraid I am not wrong :). Please check my room: http://codeforces.com/contest/362/room/44

Positions 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 :).

Luckers :) It must be runtime, really.

I tried to hack a solution using this but it didn't work. It depends on what value is at address s-1.

this case is covered, check Test #8

I got AC without handling m=0 as sorin said "It depends on what value is at address s-1"

Correct.

I do think that

would pass, but (saw it while reviewing my own code)

could cause RTE. If the first case is true, it won't produces a positive output without testing the another.

Good Problem set, with the wonderful dynamic scoring :) #loved it

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.

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."

but for that case, he does not have to step, he was standing on the dirty stair.

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

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.

he

musr startfrom the stair 1and stopat stair n , so if one of them is dirty he can not find a pathI still think I should be correct, but am bound to accept. thank you BAHOSAIN

u r welcome

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?

This is because they have to meet at the same time. An example is the test given in the statement.

Because that does not take into account the fact that the knights have to move at the same time.

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?

Check out this case:

Since the knighs move

simultaneouslythey 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.Please tell me, how half-knights can meet on this map?

Half-knights in both cases are on the one square.

oh, they can meet at starting position...thanks

Thanks,I got it. Just neglecting to take 'K'-value-position into account. What a pity.

Yes the bad squares had no use. If they can be on same place they can be on start pos.

both of them go to 2, 2 then both of them go to 0, 0

UPD4: Ratings is fucked!

UPD5: Ratings is updated

again.UPD6: Ratings is fucked

again.This is an infinitive loop :|

k = 0; new_rating = old_rating + k;

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.

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.

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

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.

Ratings are back ... yeyy, +168.

Old rating again!

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.

Does any one except me used DFS for A ?!

I didn't understand the main solution but simulation worked perfectly ;)

Code

My solution: if semiknights can meet in first step then "YES" and "NO" otherwise.

I use a BFS.

a better way is to check if (x2-x) mod 4=0 & (y2-y) mod 4=0 then the answer is "Yes" otherwise "No" :)

a much easier algo is just to check if

`abs(x2-x1)`

and`abs(y2-y1)`

are both divisible by 4, then answer isYES. if either of them not thenNO.I fail in the most simple test case, a graph with one node.

Great round!

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 ?

The third test data is

`5 1 3 4 0 2`

but not`5 1 3 0 4 2`

.Oh,thx..I have made a mistake.

Kos nagoo !

It would have better if pretests had less details especially at problem B like dirtiness of first or last stair ...

These problems seem too hard for div2.

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.

In fact ,I mean A is a trap, and many people delay on it.