dalex's blog

Codeforces Round #124
By dalex, 12 years ago, translation, In English

Hi all!

Today, June 12, when Russia celebrates Day of itself, Euro 2012 second round starts and I_love_natalia has a birthday, we present you Codeforces Round #124.

Contest was prepared by team Samara SAU Teddy Bears (craus, dalex, Hohol) and I_love_natalia. Also thanks to Alex_KPR and Codeforces team (Gerald, Delinur, MikeMirzayanov). We think that contest is very easy, and your task will be prove of refute this assertion :)

Scoring system is dynamic (Learn more about dynamic problem scoring).
Authors think that problems are sorted by difficulty in non-descending order.

Accepted solutions and successful hacks to you!

UPD. Contest is over, congratulations to the winners!

Div-1 (full results):

  1. tourist — the only one who solved all problems!
  2. RAVEman
  3. aropan

Div-2 (full results):

  1. bmerry
  2. littlefriend
  3. gstsclq

UPD 2. Tutorial is available.

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

Comments Comments (61)
| Write comment?
»
12 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Will the contest be ranked?

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

In ascending order by difficulty?

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

    The authors believe so.

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

    No, non-descending :)

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

      I'm not sure if the smiley indicates irony or that sweet feeling of disagreeing with the master, but for me the order actually seemed descending in difficulty (div2).

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

The contest doesn't seem to me as very easy :/

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

Subject narrative is a big problem！ It's too fuzzy to read...

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

What was the solution for Div2 problem A? I feel I'm missing something easy.

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

    If at least one circle can be placed in the rectangle, then first wins, because he can place circle in the center and then play symmetrically. In other case second wins.

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

Nice questions...Short uncontradictory statements and all requiring to think..Although I did not perform well but still I got to learn a lot :)

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

Can someone please explain logic behind div 2 — A.

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

    See this: http://codeforces.net/blog/entry/4708#comment-96099

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

    I took few cases , and In every case If FIRST can place the circle inside the rectangle then He can win otherwise , He can not win.

    Some idea might be thought like if there are even no of circles possible in the rectangle , then He can just place a circle midway of two circles ,,, Means He can always change the configuration for winning move.

    more clearer : if in the optimal path , if there are even no of circles inscribed in rectangle , then First can change the path by placing a circle midway of two circles . otherwise FIRST will win because last movement will be of FIRST , because no of turns are odd .

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

for problem D , can anybody tell me whether my idea is correct ?? for grid with position S if you are able to go to another S in it's adjacant 4 grids , Then I can walk infinitely , ans will be YES, other wise No

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

    No.

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

      thank you for your reply , Firstly I had an idea that if an (3 * n ) * (3 * m) grid ,,, We can go from one S to some other S then we can find a infinite cycle ,, But this used too much memory and got memory limit exceeded :(

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

        i used the exactly idea that create an (3*n)*(3*m) maze. and while searching in the 9 times larger maze, i just terminate the process as soon as i find two 'S', then, i got an AC:) I just tried waht happened if i waiting for the searching process until it is finished, then, i got a MLE:(

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

          Do you mean two 'S' including the stating 'S' (in the central block)? In other words, the starting 'S' and at least one another?

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

            Yes. Actually, which 'S' is the starting one does not matter. But when you arrived a "border" of the larger maze, you should transfer your searching position to the oppsite "border" —— it does matter a lot :)

            → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 6   Vote: I like it +3 Vote: I do not like it 
    No, example:
##.#
...#
.###
.#S.
##.#
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I think if we can go to any of the 'S' of 8 adjacent grids then it "Yes"

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

    only itself is sufficient..

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

"We think that contest is very easy" You are kidding, aren't you?

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

I wonder how many people just guessed the answer to div2-A, without actually proving it. (I got to a proof, after I finally submitted the guessed one.)

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

    may you explain your proof?

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

      If First player can place even one disc, answer is "First". Since first player can always win by placing first plate at center of board. Then he can copy the moves of second player . (Because there will always a similar space available due to symmetry)

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

Happy birthdays dalex and I_love_natalia! The problems are nice. By the way, the start time is unusual, that makes me late for some minutes.

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

    Actually, only I_love_natalia has a birthday today...

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

    1 hour after contest is a football match in group A in Euro2012. In this group is Russia too :)

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

    ...I started the contest about 15 minutes later... To my surprise, I was in the top 20...... I had once thought that my rating would have descended dramatically... So strange...

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

Div1-A is exactly the same as SRM 518's Largest Subsequence, except that the constraint is larger... This might have given unfair advantage to those who have seen it before.

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

You will have to add a new level above IGM.

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

Hello, I suppose it's better if you use just ordinary math. not something that like limit. I don't have any information about it. It's better if you would use some algorithmic problem or other problems related to programming instead of pure math. just my recommendation. I'm not a very professional participant. just participating here and don't know about other places. it's just a recommendation. and anyhow I appreciate your hard work for creating such a great contest. thanks.

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

    Actually, the solution was given in the link below the test cases explanation.

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

really liked the content, although i found it difficult. particularly task A, which in my opinion was rather the hardest than the easiest... good job, guys!! :)

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

Any idea why my practice solution for div1 E TLEs (http://codeforces.net/contest/196/submission/1798783 ), while RAVEman's (slightly modified version: http://codeforces.net/contest/196/submission/1798819) easily passes? Both use Prim's algorithm in almost the same way. I went over his code line by line and can't find the key improvement.

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

    I found 2 reason. 1. set is slightly slow than priority_queue so you solution take much more time. 2. test case is not strong enough. the way you choose start vertex is different from RAVEman (Reminder : portal might not be in order in input), he's lucky so choose largest portal number pass in time, but choose lastest portal number (in input) not.

    After I fix #2 in your code to the same way as RAVEman , it's TLE at test case #39 1799522 and after I fix both #1 and #2 it's pass in 300 ms

    UPD. fix font size

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

      That's bad, I was too imprudent :( These solutions get TLE on 'reversed' test 36 where any vertex i is renamed to n - i + 1.

      UPD: New tests (76-95) were added. Try to pass them.

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

      Thanks!! I'm surprised set vs priority_queue would make such a big difference. TopCoder's STL tutorial says "the difference is about ~%0.1 of time", yet RAVEman passed test case #39 in only 50 ms. When I tried his code with set 1798838, it failed case #39.

      As for the other reason, it seems the problem is that non-portal vertices can be visited multiple times. I haven't thought of a solution for this yet...

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

        Actually, the set vs priority_queue issue might just be another vertex ordering problem in disguise. Submission 1801347 also fails case #39 even though the only change from the "modified RAVEman code" in my first post is changing the priority_queue< pl > to a priority_queue< pl, vector< pl >, greater< pl > >.

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

          Alright, someone explained the real solution so I went ahead and implemented it! The trick is to make a sparse version of the graph of vertices which have portals. The "edges" in the portal MST will be shortest paths between pairs of portals in the original graph. There could be n^2 of these, but we don't actually need them all. MST edges are always minimum weight among edges in some cut of the graph. This solution is guaranteed to include all such edges.

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

          Yeah, I just got lucky. I had just 15 minutes after I submitted D till the end of the round, so I decided to submit the most stupid solution that I could think of...

          Usually that strategy works pretty well for me :)

          And thanks for noticing the crap I wrote. This made me read the editorial to understand the intended solution.

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

            Defeating the judge in 10 minutes is quite amazing ;)

            It's nice to see a growing community around programming competitions; I still have lots to learn from all of you! (this was my first time coding MST)

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

In Div-2 Problem-B:

Test Case: 8

3 2
4 3 1 2
-5 7 0

Why the answer is "-Infinity" instead of "Infinity"?

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

Input
cantouristsolveitlessthaninoneminute

Output
unfortunately, he can't
but he solved all problems less than 100 minutes

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

/*found my mistake*/

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

right

→ Reply