Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 11 лет назад, По-русски

Обратите внимание на некоторые изменения в расписании. Дважды.

Доброго времени суток, сообщество Codeforces!

Рад Вам сообщить, что мы в очередной раз делаем раунд из задач одной из олимпиад для саратовских школьников. На этот раз — раунд для второго дивизиона. Раунд начнется в необычное для Codeforces время: 7 декабря в 11:00 MSK

Задачи были подготовлены большим коллективом сотрудников и студентов Центра олимпиадной подготовки программистов Саратовского государственного университета.

Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.

Наш текущий план: разбаловка задач будет динамической.

UPD: Перенесли с 13:00 на 11:00 из-за Kotlin Challenge.

UPD 2: Опубликован разбор задач.

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На всякий случай — новое время проведения перекрывается с квалой Kotlin Challenge (расписание). Все желающие могут прорешать div2 за час и после этого спокойно идти на Kotlin?

»
11 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

children*

»
11 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

children*

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Nice schedule for next two rounds!

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Надеюсь раунд будет обычным/рейтинговым? а то как-то не привычно видеть анонс от MikeMirzayanov))

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

thanks, have a nice contest:)

»
11 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

What will be the scoring?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

good luck everybody.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my answer is wrong for C's first test.My answer is 6 1 2 1 2 1 2 1 2 1 3 1 3

»
11 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Классный раунд.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    И задачи шикарные :)

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Согласен! Особенно, если "С" не свалится на сис. тестах, то будет просто идеально.

      "Е" — просто шикарная задача. Жаль, что немножко времени не хватило.

      UPD: Все 3 зашли. Спасибо за раунд, от души!

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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!

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    me too!

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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
    
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried same logic. Success.

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

      @array = @array x 2;

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

very terrific system test speed

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

тесты по видимому слишком хорошие:)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The fastest final test speed I've ever seen!

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

blazing fast system test :)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ratings, please :)

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    and it will fail for,

    1 1 1 1 2 2 2 3 3 3

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok, what will be the answer for this one?

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Nice!

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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 ?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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)

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

what's the test 5 for problem C?

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

what's the test 5 for problem C?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

More info

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Товарищи, нид йо хелп... Не могу понять почему у меня выдает ВА на задачу Д 5371231 Вроде же и все W покрывает, и размер тот же

»
11 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

why my contribution is negative?

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

tutorial link please.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Я все-таки запихнул куна в С, хотя всем и пофиг, но я рад)))

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.