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

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

Всем привет!

Завтра, в 29.10.2011 17:00 (Московское время) будет проведен неофициальный контест Codeforces Testing Round #2. Во время него мы проверим на практике, что последние нововведения Codeforces не влияют на ход соревнований, а если это не так, то быстренько все исправим :) Так что этот раунд будет проходить as is, никаких гарантий на ход его проведения я не даю.

Задачи на раунде кому-то могут оказаться известными, но я постараюсь сделать так, чтобы это было верно не для всех. Будет около четырех задач, как совсем простые, так и что-нибудь похитрее.

Говорю заранее спасибо всем тем, кто придет и протестирует систему. Спасибо!

UPD: Контест перенесен на 29.10.2011 17:00 (сначала был анонсирован на другое время, будьте внимательны).

UPD 2: В контесте, наверняка, будут известные задачи для участников из Саратова. Просьба не участвовать тем, кто живет или вырос в Саратове - не портите fun другим участникам.

UPD 3: Раунд будет нерейтинговым.

UPD 4: Всем спасибо за помощь. Я думаю, получилось довольно весело для вас и полезно для нас!

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

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

Чтобы администрация была ещё больше мотивирована на успех сего действия - может сделаем его рейтинговым? Типа кот в мешке :-)

  • 13 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится
    Давайте проведем рейтинговый раунд на задачах A+B, A*B, |A - B|, A xor B и гробом будет atan2(B,A) - в нем можно перепутать порядок операндов. Вот синие и зеленые повылазят!
    • 13 лет назад, # ^ |
        Проголосовать: нравится -35 Проголосовать: не нравится
      Какая то слишком глубокая мысль, однако :-)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      А за неверные посылки очки прибавлять, а не вычитать - тогда точно получится отличный стресс-тест
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А можно ссылочку на нововведения?И раунд будет не рейтинговым?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В основном это внутренние изменения. Раунд будет нерейтинговым.
13 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Will it be rated?


Edit: To those who minused this, when I originally asked this question, the "It will be unrated round" part wasn't present in the text above (this was added later), which is why I asked it.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А школьникам, выросшим в Саратове можно?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Зайдёте - посмотрите задачи, если поймёте, что их знаете - выйдете, иначе - напишете. Всё)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится
    Только если вы не впитали эти задачи с молоком матери))
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а взломов получается не будет?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, забыл зарегистрироваться :(((((
Ладно, Belonogov, рассказывай, как решать А.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


13 лет назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

А +32 / -3 хака одного чеолвека это нормально тоже тестирование?

13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Задача А забавная, я повзламывал пока не пришла идея насчет B, набрал немного баллов.
Но.. разве это нормально?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Раунд нерейтинговый, так что да :)
    Пусть развлекаются
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я думаю, что это некрасиво. Но раунд не рейтинговый, пусть кликают раз им нравиться. Кому-то интересно решать задачи, а кому-то заниматься вот этим.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится
      Одно другому не мешает.
      А вот лимит на взломы одного участника по одной задаче очень напрашивается.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится
        Зачем? Неужели такое никто не заметит? А два-три раза взломать одного человека это вполне нормально, если в задаче много крайностей.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится
      Кстати, снимите несколько успешных взломов с участника Belonogov, он у меня их воровал)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Мне знакомый сказал, что там решение craus отправляет в стиле 
    if (n == 117) cout << "-3737373";
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    По-моему, было смешно)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      А по-моему было смешно только вам.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Даже немного жаль, что убрали и перестали ломать. Было бы красиво: первое место с двумя задачами и +INF взломов, а второе - все задачи без взломов :)
       

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И даже бана никакого не дадут? :(
Ну и ладно, что)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Похоже, их сделали участниками вне конкурса
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Ага.

      Кстати, это не "вне конкурса", а "разрегистрация", несмотря на то, что в комнате и в списке участников я себя вижу (со звездочкой). Сабмитить задачи не могу. Так и должно быть?

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

I have tried enough but I cannot understand problem C.

Now taht the contest is over could someone explain me what the problem wanted to say.

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

    Find the largest complete graph with at most N edges.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Yes, since a man can only be invited 0 or 2 times.
      At this view, a Day is actually a node, a man is an edge, the problem then becomes so obvious
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        It is amzing that it can tranform to this graph.How can you think this?
        • 13 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

          I didn't notice this until I saw hex539's post. I passed pro.C by a construction method
          something like:

          1 2 3 4 5     1 2 3 4 5     1 2 3  4  5
          1             1 6 7 8 9     1 6 7  8  9
          2         =>  2 6       =>  2 6 10 11 12
          3             3 7           3 7 10
          4             4 8           4 8 11
          5             5 9           5 9 12 ...
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          I didn't notice this until I saw hex539's post. I passed pro.C by a construction method
          something like:
          1 2 3 4 5     1 2 3 4 5     1 2 3  4  5
          1             1 6 7 8 9     1 6 7  8  9
          2         =>  2 6       =>  2 6 10 11 12
          3             3 7           3 7 10
          4             4 8           4 8 11
          5             5 9           5 9 12 ...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    For every pair of days (A,B) a person must be invited to both. But no person can be invited to more than 2 days.
  • 13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I think it can be solved this way. For n=3 you have this solution:

    1 2
    1 3
    2 3

    You can extend this solution by adding the smallest number available (4).

    1 2
    1 3
    2 3
    4

    Now, you have to "adjust" all the rows, in order to keep the property described in the statement.
    This is a way to do that:

    1 2 4
    1 3 5
    2 3 6
    4 5 6

    This one is a valid configuration for n >= 6 (because you must have the 6th hobbit).
    Extending the solution to higher N is fairly simple:

    1 2 4 7
    1 3 5 8
    2 3 6 9
    4 5 6 10
    7 8 9 10

    (Valid for N >= 10)
    And so on...

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    10
    5
    1 2 3 4
    1 5 6 7
    2 5 8 9
    3 6 8 10
    4 7 9 10
    every 2 lines at least have one same hobbit, and one hobbit can't be in 3 lines.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите пожалуйста как решать D
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Первый элемент в любом случае попадет в первую последовательность.
    Далее для любых 2 последоватеьлных элементов у нас есть 4 вариант их размещения - либо оба в первую, либо оба во вторую, либо 1 в первую, либо 2  в первую.
    Каждый раз заполняем вот так всевозможные 4 разбиения, если на каком-то шаге мы не смогли так сделать - решения нету вообще, иначе продолжаем.  В конце выводим ответ
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Правильно ли я понимаю, что это всё равно, что перебирать все возможные "начала" первой последовательности (вернее только вторые элементы первой последовательности, так как первый элемент это, понятно, A[0]) за O(N), и потом за O(N) проверять, валидно ли такое решение, у которого начало первой последовательности (A[0], A[i]) такой логикой: если текущим элементом (A[j]) можно продолжить либо первую, либо вторую последовательность, то, соответственно, добавлять к ответу элемент, иначе же попробовать новое "начало"? 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А для Е жадность бы прошла? Ну, то есть, Построить МСТ, далее, если у столицы не хватает рёбер, добавить ребро минимального веса и убрать ребро максимального веса в образовавшимся цикле. 
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Странно, что у большинства WA34 по D.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тест, вроде, несложный.
    Мое неправильное решение проходит этот тест (:
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Sorry wrong observation!.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
D это вроде задача  с прошлогоднего ВКОШПа    
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
first i make unsuccessful hacking then i discover my A problem will fail because different values of output between my code and this code then
I make 8 successful hacking  with this value -->35
code output 0 12 and the result have to be 1 0
and also my code ouput 0 12 but passed system test :)

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
please can someone explains how to solve problem D?
Thanks in advance.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    The first element in any case goes to  the first sequence.
    Then for any two adjacent elements  we have 4 variants of their placement -  both in the first sequence, both are in the second one, or  first of them is in the first sequence or the first is in the second sequence.
    Every time we check each variant of partition, if at some stage we were not able to do so - no decision at all, otherwise continue. In the end we print the answer

    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      so will we do a backtracking to try each of the 4 variants or what ??
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Did you guys ACed it to explain solution here?

      General idea is right, but I think many failed on, e.g., the following test:

      7
      1 2 3 8 4 0 -4

      So, important thing: after finding the largest progression (by inclusion) for every two elements of the first three, you should check whether we get solution if delete first or last elements of the progression obtained (and, correspondingly, add them to the second progression).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    out of first 3 numbers 2 will belong to a particular seq. rest is easy.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      could you please explain the rest - it is not easy for me. if you know 2 numbers, say, A and B, from particular sequence, and there are lots numbers (2B-A) further in the sequence, how you deal with that situation. which one you take, which one - release for the second sequence?

      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        If there is a solution, one of the two progressions must have its first two elements among a[1], a[2], a[3].  That makes three separate cases to check. 

        Now, read the a[i] from left to right, put them in either one list or the other. 
        The problematic i are those for which a[i] could be in both lists. 
        If i=n, it doesn't matter which one.  Otherwise, look at the difference a[i+1]-a[i]:
        - If it's the difference of the first list, put a[i] in the first list.
        - If it's the difference of the second list, put a[i] in the second list.
        - Otherwise, a[i] is the end of the first list, a[i+1] is in the second.

        See my submission here; the first and second list are called b and c.


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

      a naive approach based on this observation is probably wrong

      try

      7
      0 3 4 5 6 12 18
      
      you can't use greedy algorithm here, it will occupy [3, 4, 5, 6]
      and leave [0, 12, 18] unsolvable.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        I agree with bjin , my submission on D is wrong on this test but is passed the system test. 
        • 13 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится
          I found the way how to skirt this around: after you bilt a candidate for answer (some progression largest by inclusion), try to check as an answer this progression without the first element, and this progression without the last element.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Since the greedy algorithm is not correct,I want to know what is the best solution.Thank you!
13 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

как смотреть тест полностью?

Test: #19, время: 50 мс., память: 1800 КБ, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER
Ввод
30000

-1 -2 -4 -6 -8 -10 -12 -14 -16 -18 -20 -22 -24 -26 -28 -30 -32 -34 -36 -38 -40 -42 -44 -46 -48 -50 -52 -54 -56 -58 -60 -62 -64 -66 -68 -70 -72 -74 -76 -78 -80 -82 -84 -86 -88 -90 -92 -94 -96 -98 -100 -102 -104 -106 -108 -110 -112 -114 -116 -118 -12...
Вывод
No solution
Ответ
-2 -4 -6 -8 -10 -12 -14 -16 -18 -20 -22 -24 -26 -28 -30 -32 -34 -36 -38 -40 -42 -44 -46 -48 -50 -52 -54 -56 -58 -60 -62 -64 -66 -68 -70 -72 -74 -76 -78 -80 -82 -84 -86 -88 -90 -92 -94 -96 -98 -100 -102 -104 -106 -108 -110 -112 -114 -116 -118 -120 -122 -12...
Протокол тестирования
wrong answer Jury found the solution, but participant didn't [n=30000]

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нельзя. Просто скопируй достаточно большой префикс теста - на нем ты тоже пофейлишься.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    вообще можно, если будешь выводить каждый раз следующие 255 байт входного фаила. намучаешься правда....
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
I'm having trouble looking at source code sometime. Not sure this is a part of what you're testing but sometimes i get a blank view of source (nothing inside the white box... happened during the contest too when i was trying to hack) or it shows the source i lastly checked (which is not the one i clicked)... however when i refresh the page and click on it again it works no prob. But then when i check a couple of source codes more it happens again. I'm using chrome btw. Just wanted to let you know
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Is Pro.E = MST + cycle detection ??
I've tried greedy approach which firstly selecting k capital road with min weight and select the rest non-capital roads with min weight, but it seems to be incorrect idea.... 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    K capital roads with min weight is WA
    e.g.
    k = 2
    1 2 100
    1 3 100
    1 4 110
    2 3 1
    the right solution is (1,2),(2,3),(3,4)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Then can anyone give some ideas Orz....

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


        The question in problem E is to find a minimum spanning tree, such that the degree of node 1 is equal to k. 

        It is easy to find if we don't have this additional constraint with k. 
        The trick is to modify the graph a bit so that the MST in the new graph is the one we are looking for.

        Separate all the spanning trees into groups, depending on the degree of node 1.
        Consider the MST within each group.

        What happens if you increase by the same value x all the weights of edges incident to 1?

        In group i, the MST is the same set of edges, but the optimal weight is now increased by i*x.

        So the optimal weight of group i+1 increases more than that of group i:
        (i+1)*x>i*x

        So the MST of group k is the MST of the new graph with the right increment x.  This increment can be found with binary search.

        See the code by MBabin.

        UPDATE: systems test are a bit too weak; some solutions break on this example:

        4 3 3
        2 1 62
        3 2 3
        4 2 27


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

Посмотрел, на каком тесте у меня падало решение и заметил маленький баг системы:

Вывод
-1
Ответ
1
1
Протокол тестирования
wrong answer Jury answer 1 is better than participant 2147483647

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ещё баг: только что отправил решение в дорешку (12 с мелочью на часах), а время посылки пишет 30.10.2011 10:02:16
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For problem D, my solution is like this: i used pigeon hole principle: max of 3 element is enough to get a sequence, and if we analyze 5 elements, one of the sequence will definitely get 3 elements..so i made all the cases for 3 out of 5 elements. This way one sequence is fixed, if we cant get a match for a number in this sequence we will put it into another sequence if it fits there otherwise try next case. This is greedy approach. The only problem is when both the sequence allows a number and this will happen only once for a case...so a simple backtrack would work. My solution is here: http://www.codeforces.com/contest/125/submission/821110 
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Про задачу Е.
Если все веса ребер были бы разные, ее можно бы было решать как сказано сверху(бин- поиск по тому, что прибавляем к ребрам, выходящим из 1-ой вершины) . Но так как у нас могут быть одинаковые веса ребер, это надо немного изменить, иначе мы ножем считать, что решения нет, когда оно есть. Хотя тесты правда слабые - и без этого задача проходит. Некоторые принятые решения валятся на таком тесте:
4 5 2
1 2 1
1 3 1
1 4 1
2 3 1
3 4 1
(Дают ответ -1, а решение есть - например (1,2), (1,3), (3,4))
(Потому что, когда строим MST и есть равные ребра, мы не контролируем порядок их поступления)

13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
В задаче D многие принятые решения, не проходят теста:

15
1 2 3 4 5 7 9 11 13 15 5 6 7 8 9

Выдают no sulutions, хотя решение есть:
1 2 3 4 5 6 7 8 9
5 7 9 11 13 15

Жадный алгоритм ставит первую 5ку в первую последовательность, а вторую потом девать уже некуда
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Все числа различны, прочитайте условие еще раз.