Ripatti's blog

Codeforces Round #133
By Ripatti, 12 years ago, translation, In English

Hello everyone.

That is the 133th Codeforces round. Specially for the 2nd division. Contestants from the 1st division can solve the round out of competition.

Round is prepared by Ripatti , Gerald , Aksenov239 , Delinur and MikeMirzayanov .

The round will use dymanic scoring system. Problems will be ordered in random manner (see UPD1). If you want get more happiness from solving that round, please, read statements of all problems.

Good luck!

UPD1. Jury members discussed and have decided to rearrange problems in expected order of difficulty.

UPD2. Contest ended. Winners:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
solved all 5 problems. Congratulations!

Editorial will be soon tommorow (I am very tired =_=, but now you can try to read russian editorial here).

UPD3. Editorial in English.

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

Comments Comments (44)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

:)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Thanks so much for arranging the problems in expected order of difficulty.

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

This contest started horribly for me (it took me a very long time to correctly deduce the formula for A, noob :P), but ended as my best placement ever (35th). I'm really happy, and I really enjoyed this entire competition, all the tasks were very interesting! Especially the Web one (even though the idea behind it is not that difficult, the formulation was very nice :D).

Gratz everyone!

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

First time used Yandex's notepads to solve problem A :D

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

so quickly rating!

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

    Thanks MikeMirzayanov!

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

    This time the tasks was not difficult to be writen in programing language but they were difficult to solve. For the first time i was thinking about A task 40 mins.

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

      Contests are going in the direction of the ideal everyone love! Think more than Code! :)

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

hard questions really! specially question A. I hope the editorial will be available soon. And really thanks to all of you who prepared this great contest.

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

in the problem-B forming teams

is it not correct to just find the number of odd length cycles in graph described by 1..n??

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

    It's incorrect

    try test "5 0"

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

    it is correct (ofc with also removing one more player if the number of players left is odd), but look at the test which you failed:

    n = 4 3 -> 2 4 -> 2 4 -> 3

    There is one cycle here, and also this leaves us with an odd number of people left so we got to remove one more, rendering the final solution of 2. Your program outputs 0.

    My only conclusion could be that you implemented something wrongly. (since you passed the pretests I guess you already minded the case when the remaining number of players is odd)

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

      yeah... i saw that... i went wrong trying to implement the graph in a different way..

      anyways i think i corrected this and resubmitted after the contest...

      link --> 2013484

      still can't figure out what's wrong..? :(

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

        Please don't write in crippled English on purpose, it is very disturbing.

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

    It's also necessary to check if there are the same number of people on the two groups

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

    After excluding exactly one element from each odd length cycle, you can get odd number of left (not excluded) students; in such case, we must exclude one more student.

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

      Yes. That is my mistake on that task. :(

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

sorry for this question(on this blog), but i am intrested why next round time is difference 08/18/2012 11:00AM

→ Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +9 Vote: I do not like it

UPD: cout << (a+c-1)*(b+c-1)-c*(c-1) << endl;

You can see this submission 2013799.


some tips about problem A

a=2 b=3 c=4 total=18

    O O O O   
   O O O O O
  O O O O O
   O O O O

a=1 b=4 c=5 total=20 X:2 O:18

    O O O O X
   O O O O O
  O O O O O
 X O O O O

a=4 b=1 c=6 total=24 X:6 O:18

X X O O O O   
 X O O O O O
  O O O O O X
   O O O O X X
	   
a=5 b=6 c=1 total=30 X:12 O:18

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

    Instead of exact formula, use simple loop (I'm think that this is simplest solution :))

    example: http://codeforces.net/contest/216/submission/2007291 [w > 0 check is not necessary]

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

    In condition reads: (2 ≤ a, b, c ≤ 1000).

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

    it seems all of the solutions for problem A are different with each others !! there are no two same formula for this problem in AC codes :D

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

      i found a lot in O(1) solution :D

      (B*C) + (B+C-1)*(A-1)

      if we suppose we have an rectangle B*C(here A is 1) for any extra of A, we are adding a line containing B hexagons and line containing C hexagons that one of them overlaps each other, so total answer will be : B*C + (B+C-1:(one edge of B + one edge of C — one overlapped)) * ( A-1 :(for any extra of A))

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

Here is my submission to problem B: 2014265. It gives correct output on my system as well as ideone. But it fails on codeforces judge. Is there some problem with my code ? Comments are welcomed!!

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

    Function int cycle() doesn't always return a value. Maybe this is the bug you're looking for :)

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

My submission for Problem D results in runtime error at test case 35. i have no idea why this is happening. I am using the same concept as many other people during the contest.

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

    Perhaps there are some bugs in 69th line and 71th line, and the bug may be "Array index out of bounds". You shoud rewrite like this.

    while(lpos < threads[left].size() && threads[left][lpos] < threads[i][0]) lpos++; while(rpos < threads[right].size() && threads[right][rpos] < threads[i][0]) rpos++;

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

      Still the same error.

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

        You still miss the array bound check on lines 69 and 71.

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

        You should rewrite not that while statements, but the above two while statements.

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

I am getting an incorrect answer for problem B on test case #18. I wish there were a way to get the test case (it's being truncated currently).

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

    Try using the information available, and you are very probably going to see your problem. Remember to change the value of M to the number of lines you have.

    You are probably partial visiting/coloring a component, check this case

    5 4

    1 2

    1 4

    3 5

    3 4

    Maybe it works for that case, but the idea is when you get to 4, if you didn't paint all the component, then 3 and 1 are visited, and it might think it's an odd cycle.

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

      Thanks, that indeed is the error. (Edit: No, it's not!)

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

        I was not keeping a proper track of connected components.

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

I have found a very easy approach for problem A. The idea is to calculate like this if a>1 && b>1 && c>1 //it means its a hexagon: so ans = ans + 2*(a+b+c)-6 (calculating the tiles on perimeter)...

else //i.e. a==1 || b==1 || c==1 it means its a square now... ans = ans + (a*b*c);

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

for those who couldn't AC Problem D : i prefer learning function upper_bound(first_iterator, last_iterator, data); (in C/C++) (which uses binary_search and it's order is O(logN))

i think CLEAN BruteForce algorithm gets AC too... but with this function, implementing is SO EASY, it does all the job...

all you have to do is find four upper_bounds(two for each side of cell) and calculate distances see if they are equal...

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

In Problem B,

This Test Case : 

6 4

1 2

1 3

4 5

4 6

The expected ans is 0 but how will we make 3-3 pairs with this configuration ?

→ Reply