Serega's blog

Codeforces Round #212 (Div. 2)
By Serega, 11 years ago, translation, In English

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:

  1. CleRIC

  2. i_must_learn_matan

  3. Dshavn

  4. gzh1998n

  • Vote: I like it
  • +115
  • Vote: I do not like it

Comments Comments (65)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope that we have an interesting contest. ^^

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the problems will short for understand :)

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think we can use Heap to solve D.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're wrong at least because almost all of theese people check this case like `if(!m){` ` puts("YES");` ` return 0;` `}`

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am afraid I am not wrong :). Please check my room: http://codeforces.me/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 :).

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Luckers :) It must be runtime, really.

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    this case is covered, check Test #8

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like 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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I still think I should be correct, but am bound to accept. thank you BAHOSAIN

              → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please tell me, how half-knights can meet on this map?

      K###K###
########
#######.
#.######
########
########
########
#######.
      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it +7 Vote: I do not like it 
        .###.###
########
##K####.
#.######
########
########
########
#######.

.###K###
########
#######.
#.######
########
########
########
#######.

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

UPD4: Ratings is fucked!

→ Reply
»
11 years ago, # |
  Vote: I like it -14 Vote: I do not like it

k = 0; new_rating = old_rating + k;

→ Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Ratings are back ... yeyy, +168.

→ Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does any one except me used DFS for A ?!

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

Code

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I use a BFS.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I fail in the most simple test case, a graph with one node.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    The third test data is 5 1 3 4 0 2 but not 5 1 3 0 4 2.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,thx..I have made a mistake.

      → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

These problems seem too hard for div2.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply