MikeMirzayanov's blog

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

Please take a notice that recently the schedule has been changed. Twice.

Greetings to the Codeforces community!

I'm glad to announce that we again decided to introduce a round based on one of the programming olympiads for schoolchildren in Saratov. This time it is a round for participants from Division II. Round will start at unusual time for Codeforces: Dec. 7, 07:00 UTC.

The problems were prepared by employees and students of Programming Competitions Training Center of Saratov State U.

Members of the first division can participate out of competition, as usual.

Currently we are planning to use dynamic scoring system.

UPD: Moved from 09:00 to 07:00 because of Kotlin Challenge.

UPD 2: Tutorial has been published.

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

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

children*

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

Nice schedule for next two rounds!

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

Could you please move 1 or 2 hours earlier? It overlaps 1 hour with Facebook Hacker Cup. Thanks.

EDIT: Sorry, I confused the times. They don't overlap.

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

    No, it doesn't. The hacker cup starts 9 hours after this round ends.

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

    Round 1 lasts for 24 hours and time penalties don't matter for advancing to the next round, feel free to participate at whatever time you like -- there's no advantage to doing the problems right at the start of the round.

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

thanks, have a nice contest:)

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

What will be the scoring?

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

    It's dynamic score, thats mean, the problem most solved will have 500 points, etc.

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

good luck everybody.

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

What's the intended solution for problem C? I tried many different greedy approaches, yet they all fail in test 10. And maximum cardinality bipartite matching TLE's in test 12!

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

    me too!

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

    Sort all the numbers in array a, then reverse them in array b. Then the pairs with the same numbers can form only a single subsegment. Then try to swap some numbers from b in this subsegment with some numbers from b either at the start or the end. One can prove this is optimal.

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

      Does this rely on a well-known greedy algorithm? something like load-balancing I mean? I always have a very hard time with problems that have greedy solutions :D

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

        As far as I know it doesn't. It's just a hunch for this problem.

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

    bipartite matching works, build the graph with color of mittens as the vertex and the number of each mittens as capacity of the vertex from super-source to each color and each color to super-sink, it works in O(m^3) which is enough to pass the time limit.

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

      Aha I see, this approach depends on M, my approach depended on N that's why it TLE'd. Nice idea!

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

    My idea was to build another array and send it to output with

    res[i] + " " + res[ (i+offset)%size ] ; // i = 1..n

    where array looks like

    1 1 1 2 2 3
for
1 2 2 1 3 1

// (I've just found that I simply need to sort it, xd)

    so, "offset" is maximal count of 1..m types (or colors, I don't remember)

    and this method gives output

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

      How did you think of such a solution? :D. The only thing I could think of was to match the two colors with the maximum frequency in each step

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

      I tried same logic. Success.

      @array = sort {numeric, reverse} @array;

      @array = @array x 2;

      $multiline .= $array[ $i ]." ".$array[ $i + max_repetition ]."\n" FOR @array

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

    There was a stupid solution: sort left mittens, sort right mittens. shift right mittens cyclically by n/2. P.S. almost the same problem was in one russian contest last year: https://zaoch.olympiads.ru/zaoch/2012-13/final/problems.shtml

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

    Here is a solution that seems intuitive to me: First sort the colors with descending number of occurrences We note that if the majority color is <= size / 2, we can get everything to be distinct by simply shifting the majority color to the guy who is at the start of the second majority color

    E.g.

    111111222333

    222333111111

    On the other hand, if the #majority color is > size /2, our best choice is still to do the above assignment, because the number of matches is at least 2*#major — size

    Code: http://codeforces.me/contest/370/submission/5369409

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

    Sort all children by colors, and then iteratively check.

    At the i-th child, check if it is possible to find someone before with unchanged mittens, then swap one mitten with him/her. If everybody before has got changed mittens, then find someone before with mittens share two differenct color with the i-th child, then swap. If there's nobody satisfying these two conditions, then just wait and see.

    i.e. Initial distribution: 1 1 2 3 3

    The first two children can only wait: 1 1 2 3 3 1 1

    Then 2 can swap with the first one: 1 1 2 3 3 2 1 1

    Then 3 insert to the second place to 'save' that child: 1 1 2 3 3 2 3 1 1

    The Last one swap with the first one: 1 1 2 3 3 3 3 1 1 2

    The end.

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

very terrific system test speed

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

Did you use the Hopcroft-Karp algorithm? I also tried a greedy aproach but realised it fails even on the first example. I didn't manage to finish the maximum matching afterwards.

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

    Well I thought about implementing it during the contest but I thought that it wouldn't pass, the time limit is so strict (1 second)

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

The fastest final test speed I've ever seen!

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

blazing fast system test :)

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

ratings, please :)

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

Prob-C (Div2): Missed the statement "Note that the left and right mittens are different: each child must end up with one left and one right mitten." ... Paid for my carelessness :(

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

    My first solution had WA10, because I did not read this sentence, but I fixed this bug :)

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

Why is this o/p wrong for pretest 1? 6 1 2 1 2 1 2 1 2 1 3 1 3

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

    http://codeforces.me/blog/entry/9854#comment-153240

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

      ok.But i still dont get it? What am I missing here? :(

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        1. On the i-th of these lines print two space-separated integers: the color of the left and the color of the right mitten the i-th child will get.
        2. Note that the left and right mittens are different: each child must end up with one left and one right mitten.

        You're trying to wear a right mitten on the left hand. It's impossible in this problem.

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

For C, I thought of the following: 1. Find frequency of each color. 2. Sort the list as per frequency. 3. Pair color with highest freq with color with lowest freq and then decrement frequencies of both colors by 1. 4. Continue till we cant create any more pairs.

for example, 1 1 2 1 2 3 would give {1: 3, 2: 2, 3: 1}.

i. Make pair (1,3). List now becomes {1: 2, 2: 2} ii. Make pair (1,2). List now becomes {1: 1, 2: 1} iii. Make pair (1,2). End. The answer will be 2*(no. of pairs we make).

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

    and it will fail for,

    1 1 1 1 2 2 2 3 3 3

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

      Ok, what will be the answer for this one?

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

        Hmm.. Many possible answers. But in any case we can pair each one if we do it optimally.

        e.q.
        1 2
        1 2
        1 3
        1 3
        2 3

        and the reverse! :)

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

      My solution passed systests with such logic, and it also works well on your test.

      It depends on what color to choose in a case of tie. Choosing max of max, min of min gives WA66, choosing max of max, max of min gives AC.

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

        Nice!

        It didn't click me. :| Have to check your code! :)

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

        What do you exactly mean by max of max and max of min here? Can you explain for the above example, 1 1 1 1 2 2 2 3 3 3 ?

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

          On your example WA solution gives

          10
1 3
3 1
2 1
1 2
3 2
2 3
1 3
3 1
2 1
1 2

          and AC solution gives

          10
1 2
3 1
2 1
1 3
3 1
2 3
1 2
3 1
2 3
1 2

          max of max — from all colors with max number of items i'm choosing one with largest id. Max of min — from all colors with min number of items i'm choosing one with largest id (or with second largest, if at this moment min=max).

          UPD. I found a bug) Actually my first solution was max of max + max of max, and second one is max of max + min of max)

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

            I'm slightly confused. Finally, which combination gave you AC? (max of max, max of min), or (max of max, min of max)?

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

              max of max, min of max.

              I don't know, is it OK, or just tests are weak:)

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

                I am unable to think of a reason for a number with larger ID to be included in the optimal solution.

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

            What's wrong with the WA in the case 1 1 1 1 2 2 2 3 3 3? I thought it is correct?

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

              Both my solutions works well on this case. But one of them got WA66, and other one got AC.

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

              Let's wait for the test cases to be put up. Probably we'll have a better idea then.

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

            @LeBron I think I know why, your setting will help to avoid this case 1 2 3 4 5

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

what's the test 5 for problem C?

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

    why system doesn't show the tests? and also other's code??

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

      Because this contest is now running in Saratov. Soon the system will show everything.

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

I'm curious for the solution for problem C……My solution doesn't depend on m……it's just O(n^2),and get accepted,but in fact,i can't prove it's correct

can anyone tell me why it's correct? http://codeforces.me/contest/370/submission/5371522

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

|   | Sent | Accepted |
| A | 1094 | 781      |
| B | 820  | 654      |
| C | 449  | 151      |
| D | 130  | 17       |
| E | 11   | 2        |

More info

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

Hmmm, I registered but didn't take part in the contest... So sad :(

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

er.I want to know the Pro C -- test58.why my answers is TLE while I get:

for(i=1;i<=n;++i)
  for(j=i+1;j<=n;++j)
     if(color[i]!=color[j])
     {
        add_edge(i,j);
        add_edge(j,i);
     }

http://codeforces.me/contest/370/submission/5379683 , and I get Accepted when I code as:

for(i=1;i<=n;++i)
  for(j=1;j<=n;++j)
     if(color[i]!=color[j])
     {
        add_edge(i,j);
        //add_edge(j,i);
     }

http://codeforces.me/contest/370/submission/5379655

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

tutorial link please.

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

Could there be more contests that are held at 07:00 UTC on Saturdays? I'm a Chinese student. Most contests are held at 11:00 p.m in China, and I hardly have time to take part in the contests.

→ Reply