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

Автор vepifanov, 14 лет назад, По-русски
Добрый вечер!

Сегодня автором задач выступаю я. Учусь в Нижегородском государственном университете (2 курс, мех-мат). Хочу выразить благодарность коллективу codeforces за помощь в подготовке контеста, и, персонально, Артему Рахову и Марии Беловой (за перевод условий на английский язык). Также отдельное спасибо Алексею Шмелеву (Нижегородский гос. университет) за написание альтернативных решений.

P.S. К сожалению, на этот раунд можно было по ошибке зарегистрироваться командой. Для команд участие в этом раунде будет засчитано "Вне конкурса", т. е. рейтинг участников не изменится. Если вы зарегистрировались командой по ошибке, вы можете отменить регистрацию и зарегистрироваться лично.

UPD: Как только начнется соревнование, то будут доступны задачи в PDF:
UPD: Контест завершен, поздравляю Ивана Попелышева, который стал победителем этого раунда. Он оказался единственным, кто успешно решил все 5 задач.

Ссылка на результаты.

UPD: Доступен разбор задач.

С наилучшими пожеланиями,
Владислав Епифанов.
  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Всем Удачи!
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Ждем отличный контест!!))))
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Удачи всем!
Надеюсь сегодня стану желтым!
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Good luck to everyone.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Сегодня должен быть хороший контест!!

Всем удачи !!

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's the tricks in Problem B?? orz
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите пожалуйста тест № 3 в задаче B!!!
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Тест номер 3:
    10 100 5
    61 3
    55 2
    12 6
    39 5
    21 10
    39 7
    16 1
    10 1
    70 5
    100 7

    Один из возможных ответов:
    YES
    21 6
    0 10
    15 9
    17 1
    18 2
    19 6
    20 5
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня полконтеста валилось на этом тесте, потому что я "плохо читаю секцию формат выходных данных, где написано, что когда босс мертв, применять свистки не нужно."
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В данном конкретном случае была явная бага в условии, ибо без кларификешна в нем было написано, что босс может помереть только в конце хода - то есть уже после прочтения свитка
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Прочитайте кларификешн, разосланный во время контеста. Мне он помог пройти именно 3й тест :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Clarification это хорошо. Единственное, что нужно было, так это важные фразы не вставлять в конец параграфа, где описывается формат выходных данных.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дайте пожалуйста 8 тест для В.
14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Была похожая ситуация(с третьим тестом в B). Причём, в условии же написано:
Босс считается поверженным, если в конце какой-то секунды количество здоровья стало неположительным ( ≤ 0).
+
Свитки выводите в том порядке, в котором их нужно использовать. Запрещается использовать свитки после того как босс повержен.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What was pretest 3 in Problem C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Pretest #3:
    10
    4 4 4 4 4 4 4 4 4 4
    Possible answer:
    YES
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001


    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      How about pretest 4 in same problem, please?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Test #4:
        20
        6 7 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 6 7

        Possible Answer:
        YES
        000000, 0000110, 0000111, 0001000, 0001001, 000001, 0001010
        0001011, 0001100, 0001101, 0001110, 0001111, 0010000, 0010001
        0010010, 0010011, 0010100, 0010101, 000010, 0010110



14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче C, как я понял, сначала нужно было отсечь заведомо неправильные входные данные по неравенству Крафта-Макмиллана. А где можно почитать про быстрое составление префиксных кодов заданной длины?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    строится жадно, обходом бинарного дерева в данном случае
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
86 тест по задаче B можно?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тест 86:
    10 1000 8
    100 1
    100 1
    100 1
    100 1
    100 1
    100 1
    100 1
    100 1
    100 1
    100 1
    Возожный ответ:
    YES
    509 10
    0 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    8 9
    9 10
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's the pretest 3 in Problem B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Test #3:
    10 100 5
    61 3
    55 2
    12 6
    39 5
    21 10
    39 7
    16 1
    10 1
    70 5
    100 7

    Possible answer:
    YES
    21 6
    0 10
    15 9
    17 1
    18 2
    19 6
    20 5
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Можно 36 тест задачи C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тест 36, как ни странно, довольно тривиальный :)
    3
    1 1 2
    Ответ - NO

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      мда... бага была очень глупая... как дошло до 36 теста не представляю)))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Нельзя ли узнать тест 15 к задаче Д или хотя бы его вид? Не у одного меня на нём упало:P
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тест 15 - один из средних рандомных тестов:
    31
    12 7 5 30 8 17 6 8 0 6 0 15 9 11 9 11 0 1 8 8 4 39 17 2 5 2 1 9 39 4 13
    19 18 13 35 27 29 14 23 0 16 0 18 9 37 48 49 0 23 50 9 32 47 39 45 24 13 19 16 50 37 14

    Ответ - 59922858
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Ну ошибка очевидна у меня. В конце, когда домножаю ответ динамы на C(x, y) бежал до n, а не до m. Дебил, конечно. Обидно.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Стандартный баг)) Привычка всегда бежать до n))))
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А я в этой задаче схитрила: с самого начала поменяла n и m местами
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Наталия, Вы на одном из недавних контестов уже наступили на эти "грабли" (там задача на LCA была). Видимо только это способно пробудить осторожность в программистах... Теперь и я буду внимательнее набивать циклы. 

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня на нем Run-time Error. Делений у меня там точно нет. А, значит, упало из-за размеров массива. Вроде как такого быть не должно. Хотелось бы посмотреть этот тест.
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Во время тестирования опять упал сервер. С этим надо что-то делать:-)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хех. А у меня в D TL, т.к. я налету считал цешки и забыл учеть это когда считал сложность. Всего-то меморизации нехватило.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Ура, целых 2 полковника в нашей армии, мои поздравления !
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можно 34 тест к B ? спасибо
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Большой тест из почти 900 свитков, но в ответе их всего 2, и соответственно минимальное количество секунд также равно 2.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Классный контест. Особенно задача С порадовала. Получил -5 за свое мега-длинное палево, а прошли 10 dfs-подобных строк кода
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Да, в С можно было неудачно выбрать алгоритм построения кодов, и в результате получить много много строк глючного кода :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Именно так я и сделал) Самое удивительное было, когда это чудо зашло) 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
sorry but when will be the practice available ? find out my mistake  5 minute later, after the contest ended. (Problem c)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
how to get all pretest during contest???
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
So, what is the idea about problem C ??
I have constructed a prefix tree like that in Huffman coding, and traversed it to get the solution, and if I can't add the new item then it is invalid

so what is wrong in this solution, as I failed in case 21 in the final test!!

Thanks in advance,
14 лет назад, # |
Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится
Спасибо за контест.

Aфигеть как просто.
B условии была вся нужная информация, но многие читают по диагонали.
Сообразить как присваивать номера полегче, в порядке возрастания длины.
ПоDумал что возможен случай Y[i]<X[i] и ресабмитнул, зря. Dинамика по текущему кабинету и числу свободных на второй паре групп, занимавшихся до этого в более левом кабинете.
Посмотрите решениЕ gawry. Задача сводится к баяну, возможно все её испугались после решения Dинамики. Была бы на месте С, сдавали бы массово.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне лично C показалась больше баяном, чем E.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А какое именно дп, а именно как туда добавить учитывание перестановок(то есть, называем группу первой и получаем отличное расписание от расписания, где эта же пара названа второй группой)?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Можно посчитать для какой-то одной перестановки, ну а потом ответ умножить на факториал от всех людей и поделить на факториалы от X[i].
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      Пронумеруем группы следующим образом. Всего способов расставить группы на первой паре Z = S! / X1! / X2! / ... , можно посчитать через произведение биномиальных коэффициентов, а их через таблицу. Будем рассчитывать случай когда в кабинете номер 1 занимаются группы с номерами с 1 по X1, во кабинете номер 2 с X1 + 1 по X1 + X2 и так далее. В конце домножить результат динамики на коэффициент Z.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно просто расставляя очередные Xi групп домножать на число сочетаний из количества групп у которых не определена 1-я пара (т.е Xi + Xi +1 + ... + Xm) по Xi. 
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Верно, это то же самое :) Просто я над этим задумался только в конце, вот и написал отдельно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Это неправда, что в B  в условии была вся нужная информация. Там было написана очередность действий во время секунды (последнее действие - чтение свитка), написано, что проверка на смерть делается в конце секунды (то есть после всех этих действий) и написано, что нельзя колдовать по уже мертвому монстру. Но в такой формулировки к моменту чтения монстр еще не умер, хоть у него и не положительное здоровье. На топкодере с такой поздней кларой это был бы анрейт, хотя контест просто отличный
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can anyone tell how to do the problem C ?
Thanks
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Hi arpit_s

    1- Sort the data, but keeping information about original positions.
    2-Starting with an empty string s ( representing a binary number), do the following for each number:
       -If s is not the empty string, increment s by one. If this implies using an additional binary digit, then just     print NO.
       -Add as many zeros to s so that it has as many digits as the value for the current number.
    3-In this way you build a prefix-free dictionary, so now you just have to print it in the desired order.

    Regards.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I'd apreciate test 87 for problem B.....Thx in advance
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А по-русски, кто нибудь может изложить план решения задачи С? Спасибо.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Imagine a big binary tree which has empty string as root, and traversing left appends a "0" and to right appends a "1". So all possible 0-1 strings of same length are at same level. Each node in the tree is associated with its corresponding 0-1 string, which is just the path from root to it.

    Now, count the number of strings of each length we need from input. You start at "0" : len=1 and keep moving.

    1.) We are at level k and we need n strings of length k . If you are at node X, you can pick nodes X , X+1 , X+2 , . . . , X+n-1 ( each node has a 0-1 string associated with it, and +1 is just binary arithmetic ) .

    2.) After picking n strings at this level, you have to move to next level below. But, that should not have the previously chosen ones as your prefix. So, move right one more time and then go down left, such that none of its ancestors were chosen before.

    3.) If n=0, you can just go down left. Going down is same as X*2 ( left shift by 1 = one more 0 at end )

    In step 1, if X+n-1 exceeds length k, then its not possible "NO". Try on paper with the tree figure to make it clear. I have used this in contest. So here is my code for reference http://www.ideone.com/tkipH .
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно четвертый финальный тест E?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Тест #4:
    9 29
    BWBBBBBBBBBWBWWBBBWBWBBBWWBWW
    WBWBBWBBWBWWBWBBBWBWWWBWBBBBB
    BWBBBBWWBBBWBWBBWWBBWBBBBBBBB
    BBBWWBBWWBBBWBWBBBWWWWWWBBBBW
    BBWWWWBBBBBBBBBWBBBBBBBBBBWBW
    BBBWWBBBBWBBBWWBBBWBBBBWBBWBW
    BBBBBWBWBBBWWBBWBBBBBBBBBBBBW
    WWBBBWWBWBWBBBBWBBBBWWWBBBBBB
    BWWBWBBBBBWBBWBBBBBBBWBWBBBWW

    Ответ - 4
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is it possible to have a look at Problem C test 9 ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
And test 8 of problem C as well...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
As there is no a function to see test cases, maybe you could share the folder with these tests, so that we could have a look at them in the following way: codeforces.ru/contests/37/tests/C?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
May you provide me with test 76 in problem B?
Thanks.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I have found that the 3rd case of problem D has Xi = 0, but the problem statement guarantees that Xi > 0.
This makes some contestants' solution get wa.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
There is a mistake in problem D

The problem said 1<=Xi<=100.But in pretest 3,the Xi becomes 0 which causes me get wrong answer  on it during the competition.

But it's too late now...

Someone should take the responsibility of the mistake!!!
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Why late?
    I think your solution will be rejudged.
    Email private message to the contest's author.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I read accepted solutions for problem E, but I couldn't understand. How do you paint this board in 4 days?

13 13
WWWWWWWWWWWWW
WBBBBBWBBBBBW
WBWWWBWBWWWBW
WBWBWBWBWBWBW
WBWWWBWBWWWBW
WBBBBBWBBBBBW
WWWWWWWWWWWWW
WBBBBBWBBBBBW
WBWWWBWBWWWBW
WBWBWBWBWBWBW
WBWWWBWBWWWBW
WBBBBBWBBBBBW
WWWWWWWWWWWWW
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    0000000000000
    0111110111110
    0122210122210
    0123210123210
    0122210122210
    0111110111110
    0000000000000
    0111110111110
    0122210122210
    0123210123210
    0122210122210
    0111110111110
    0000000000000


    First time we paint all the board into black.
    Second turn - all cells except cells with distance 3 into white.
    Third - all except 2 and 3 into black.
    And last - cells, except cells with 1, 2, 3 (cells with distance 0) into white.