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

Codeforces Beta Round #61 (Div. 2)
Автор Seyaua, 13 лет назад, По-русски
Здравствуйте!

Приглашаю всех принять участие в знаменательном раунде! Сегодня будет первый за всю историю Codeforces раунд для второго дивизиона, когда в конкурсе будут участвовать синие участники!

Сегодня авторами задач являюсь я и sdya. 
Выражаю благодарность всем тем, кто помогал готовить раунд, то есть Артему Рахову, Марии Беловой, Дмитрию Матову.

Всем удачи!

UPD #1: ссылка на разбор.

UPD #2: Поздравляем победителя второго дивизиона Kepnu4, а также победителя среди внеконкурсных участников и среди всех участников cerealguy!
  • Проголосовать: нравится
  • +115
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Насколько я помню, это не первый ваш контест с братом.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
О! В етот раз я уже поучаствую, а то в прошлый раз не получилось :)
Надеюсь задачи все ровно будут более-мение матиматические ?

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

YES

First Div 1 : Codeforces Beta Round #39

and now

First Div2 : Codeforces Beta Round #61 (Div. 2)

Good Luck man ..... :D
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Похоже сегодня рекорд по количеству участников для второго дивизиона
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    С расширением дивизиона, это прогнозируемо.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      В количестве зарегистрированных отображаются все. Участники первого и второго дивизиона.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И кто же опубликует разбор в первые минуты после контеста? Ждем :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У тебя есть ещё 10 минут, чтобы самому порешать :o)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я уже залочил все свои решенные задачи и ужасаюсь решениями других.
      Не то чтобы чужие решения были страшными. Скорее это шок осознания ничтожности моих :).

      ЗЫ Я смотрю, смайл клоуна в моде
      → Ответить
13 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

D классно ломается:) Сам ресабмитил, так как увидел глупую ошибку не сразу)

Интересно будет почитать разбор, есть у Е красивое решение или нету? Некрасивое было влом писать)

И на С было бы интересно посмотреть "самое короткое решение"".

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    Может стоит подождать окончания контеста с такими заявлениями?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Из всего моего заявления, как по мне, стороннему человеку только одна польза - пойти попробовать завалить кому-то D :)


      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Или пойти найти ошибку у себя
        И это серьезная польза
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, потому что число посылок в последние минуты сегодня зашкаливает. :)

          Была даже посылка в 01:59:59
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +2 Проголосовать: не нравится

            еще у меня был взлом на последней секунде:)

            10892     07.03.2011 21:00:00     diogen     l0nwlf     D - Петя и его друзья     Успешный взлом

            → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        ignore
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
У меня вопрос по задаче Б.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Во-первых, вопросы надо задавать в интерфейсе участника
    Во-вторых, перечитайте формат вывода
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Ответ - это количество участков под дождем, а не номер участка.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    мне нравится, что вы не поленились сделать понятную картинку.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Моя внимательность ступает со мной нога в ногу с детства...
    Я фактически написал решение. Только загонял в вектор все суммы и выводил номер максимальной... Fail.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Мне одному показалось, что задача С была самая сложная?)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Объясните Е, пожалуйста. Я думаю, если Вы считаете С самой сложной, значит Е Вы решили с легкостью.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В A написал на шарпе используя BigInteger и получил ошибку компиляции. Может быть, стоит добавить в нем поддержку System.Numerics?
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится
Не хватило 2 минут, чтобы решить С. Сейчас только написал решение, с нетерпением жду дорешевания. Долго тормозил с А. В целом контест интересный, спасибо.

UPD. Чуть говорит мне о fail'e)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice problems. Good job , guys
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот как так вроде читал по D что есть варианты для которых ответ не существует, но не позаботился обработать этот случай при N = 2, в итоге под конец взломали и ошибку искал совсем не там, хотя решил задачу верно, очень обидно(
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обидно, я забыл написать if на случай когда N = 2 в задаче D. =(
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Охота узнать хорошее решение на С, а то пытался написать структуру так и не дописал.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можешь посмотреть мой код. Использовал map <string, set<string> > и map <string , int>. Короткое решение ;) (максимум 20 строк)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
so many problems were solved with BigInteger....


→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I feel a litlle unfair about D because a solution using BigInteger is too much easier to come up with.
    (I usually use C++ but used ruby to solve D.)

    But thanks for a nice contest! I really had fun.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      C++ can also solve this problem without a biginteger ...
      you can make the first three number 6 , 10 , 15  and then the numbers follow are 15*2^1 ,15*2^2,15*2^3 and so on
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    That's why CPP programmers must always have their BigInteger codes ready
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а что за раунд такой следующий? объясните пожалуйста.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
nothing
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  1. if(s.length()<=19)
  2.                   {
  3.                           d=0;
  4.                       for(i=0;i<s.length();i++)d=10*d+int(s[i])-48;
  5.                           if(d<=9223372036854775807LL)cout<<"long"<<endl;else cout<<"BigInteger"<<endl;
  6.                   }else
  7.                           cout<<"BigInteger"<<endl;
  8. Please, tell me why this code work on test "9999999999999999999" (9x19)?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
twitpic I messed around A due the a quick misinterpretation of minus symbol as dash (hyphen). I request from next time on while writing out negative numbers, don't put a space or linebreak between the minus symbol and the number, so that the negation remains intact and I (lol, just for me) don't get confused. 

:(
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за традиция такая пошла, в задачу A кидать что-то вонючее? :o)

500я должна быть простой, ясной, понятной, что называется "Прочитай и напиши", и уж тем более во втором дивизионе!

Задача D была явно проще и понятнее задачи C.
Задача B была явно проще задачи A.

Авторам спасибо за хорошие задачи!
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    По задаче А. 
    Ключевое слово - прочитай. Из условия следовало, что числа натуральные. К сожалению, немногие обратили на это внимание. Если это учесть, то решение будет более чем простым.

    По сложности задач: 
    Задача С не требует сложных идей для решения. Единственная сложность - техническая реализация, что для дивизиона 2 может быть существенным. В задаче D надо было придумать идею, и авторам с тестерами показалось, что идея не самая очевидная.
    По поводу сложности задач А и B - довольно часто они бывают примерно одинаковыми по сложности.

    Но вообще, в следующий раз постараемся учесть ваши замечания :)
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Ну по крайней мере сейчас по задаче A 486 решений, а по B - 643, что как бы намекает. :-)

      Да и D сдали много больше чем C.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Уверен, что задача А не сложнее B, просто в ней было намного больше возможностей ошибиться, чем успешно воспользовались множество участников. 

        Ну и, несолидно давать на B задачу, которая решается несколькими ифами...
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится
      Вообще надо было давать В за линейку. 
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Тогда это уже C.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да я не согласен. Я именно за линейку ее и придумал, по-моему за линейку придумывается естественнее чем за квадрат
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я ****ся-****ся за линейку, а потом понял, что ерундой маюсь и написал за квадрат)
            → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вообще есть такая мысль: можем запускать дождь над количеством участков <= K, всего участков до 100000. Попробуйте решить :)
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Я ее именно в таком виде и решил:) 
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            дождь над количеством участков <= K?
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
              Сорри, зачеркнул. Ну а вообще-идея кстати не отличается от моей. В массиве храним сколько соседних участков зальется, если в тот в котором мы стоим поместим поливалку. Над массивом строим дерево, для узлов храним максимум. Когда вставляем шланг над этим местом апдейтим минус единичками. Сложность в итоге-на построение дерева О(n*logn), на поиск и апдейт-O(min(n,k)*logn).
              → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Проблемсет был очень интересный, авторам спасибо. Обидно, что, отложив решение технически сложной, но тривиальной задачи C на самый конец, я так ее и не сдал.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задача Е уж очень лёгкая для 5-ой, а так задачи хорошо подобраны.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Эх, самый легкий контест за все время. А я полное нубье:
B сдал на 5 минут позже, чем надо было,
D сдал на 10 минут позже, чем надо было,
E сдал на час позже, при этом изначально писав бред,
C - самая сложная, ее долго кодить, и на нее не хватило времени.
И в итоге занял позорное 55 место...
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По поводу С - ее сложность зависит от выбора реализации. Авторское решение на Java занимает меньше килобайта.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Test: #31, время: 270 мс., память: 4684 Кб, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER
Ввод
100000
95 84 39 98 24 29 65 22 17 27 48 80 21 96 50 71 37 46 7 21 69 29 6 14 8 75 2 8 7 70 94 97 17 72 93 59 84 81 42 6 10 7 17 26 89 45 99 45 83 29 74 61 6 29 26 3 64 17 84 92 68 99 54 4 55 36 4 98 14 57 29 33 10 52 63 5 55 94 82 74 52 75 73 14 46 42 15...
Вывод
50482
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 124 126 128 130 132 134 136 138 140 142 144 146 148 150 1...
Ответ
50483
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 124 126 128 130 132 134 136 138 140 142 144 146 148 150 1...
Протокол тестирования
wrong answer 1st numbers differ - expected: '50483', found: '50482'

ммм... Как бы увидеть ошибку?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Вообще нельзя.
    Но т.к. ты из Саратова, можешь спросить лично админов :)

    И вообще исправил бы пост, а то он как-то поганит тред
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как бы ошибку увидеть, где баг?
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну так я же говорил.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Блин, обидно-сдал бы ее, поднялся бы сразу в синие наверно. А вообще меня ппц лихорадит. То последний в контесте-то на грани первой сотни или даже выше.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится
      >А вообще меня ппц лихорадит. То последний в контесте-то на грани первой сотни или даже выше.
      Один контест с пометкой "div2", другой без нее. Вот и все
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скажу по секрету: у вас не хватает в ответе числа 100000. Проверяйте...
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
thnx for nice contest :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

it was a really nice contest...except for problem c that i didn't even try to solve it!!

i actually hate text ones.

thanks every one

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
someone has accidentally swapped C and D problems :D
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
What's wrong with problem C in these div.2 contests? #57 was just as bad as this one
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Извиняюсь, если вопрос тупой... Кто-нибудь знает, почему в С++ значение логического выражения (111111 >= -2147483648) равно 0 (т.е. false) ? У меня 1-я задача из-за этого упала..
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    я тоже как-то не понял
    присвоил переменной
    int t =-2147483648; и потом сравнивал все норм
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И, что еще более странно, это только в Visual C++ так. В gcc все в порядке (т.е. значение равно 1).
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Попробуй (111111 >= -int(2147483648))
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это равно 1. Но тут вроде все понятно.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Видимо 2147483648 покастилось в unsigned int, а минус для него дал такой странный эффект.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, похоже на то... Обидно. Это ж так было написать компилятор
          → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
loved the contest. thanks for nice contest :).
also, Is it possible to see the test cases ? otherwise can you please share test case #71.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Даа... Контест был замечательный, спасибо авторам! Я даже получил +20 по его итогам... Но я в течении часа дебажил задачу С! Объявил две рекурсивные функции для подсчета числа файлов и папок, назвал их fi и f соответственно, но в первой вызывал рекурсивно ф-ию f, а не fi!!! И в течении часа не мог понять, почему у меня рекурсия проскакивает и получается какой-то дикий ответ... Но за две минуты до конца я все-таки нашел этот баг и сдал задачу даже без тестирования..) И она прошла тесты! В результате не осталось времени на более простую задачу D и тем более на E (хотя я бы наверняка ее все равно не решил :) )
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Большое спасибо за контест!) Получила удовольствие и плюс к рейтингу). 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сейчас обнаружил, что мое решение С, которое прошло системное тестирование, на тест:
C:\a\11\1.qwe
C:\a\1\1\1.qwe
Дает ответ: 2 1
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Значит, вам повезло :) Подобные тесты делались, но видимо, недостаточно тщательно... Трудно подобрать тесты против всех возможных ошибок :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А если сделать штук 10 тестов с большим количеством строк, только символом 1 и произвольно расставленными \, получится то, что надо?
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится
        Да, вы безусловно правы, но не всегда понятно, какие тесты стоит добавлять, а какие нет. Заранее нельзя сказать будет ли участник, который на этом попадется. Мы старались добавлять те тесты, где потенциально решение участника могло упасть. К сожалению, тесты именно такого вида сюда не попали...
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    o_O у меня тоже такой ответ! Спасибо за тест, а то я никак ошибку не мог найти! :)
    → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
Why each test case is given twice to each code?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
for problem D, 
use 6,10,15, and 6*n (2<=n<= around 60)
can generate the required result
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I feel that contests on codeforces are based a lot on string manipulations which becomes a lot easier for advanced coders who are used to STL data types. At least Div. 2 problems should not have so many questions like that.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, почему у меня на дорешивании задача E не отправляется?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please use Codeforces.com for linking the names to their profiles in English posts, Thanks.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
      Маленькое замечание по поводу тестирующей системы:
Весьма обидно тратить время и получать штраф только за то, что в задаче D в каждой строке после числа выводился еще и пробел. Совершенно случайно исправил это во время контеста, а так было бы ну ооочень обидно. По идее, обработчик OUTPUTов должен подобное игнорировать, вроде во всех тестирующих  системах (в случае побайтового сравнения) это предусмотрено. 
→ Ответить