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

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

Приветствуем всех на первом летнем раунде - Codeforces Beta Round #73

Авторами этого соревнования являемся мы: kuniavski (Павел Кунявский) и Zlobober (Макс Ахмедов). Соревнование проходит одновременно в двух дивизионах. Суммарно вам будет предложено 7 различных задач с вариациями в разных дивизионах, по 5 в каждом дивизионе. Мы надеемся что все смогут показать свой результат и решить как можно больше задач.

Мы хотим поблагодарить RAD (Артем Рахов) за помощь и множество полезных советов во время подготовки контеста, а также Delinur (Мария Белова) за перевод задач и MikeMirzayanov (Михаил Мирзаянов) за Codeforces в целом.

Удачных решений и взломов!

GL & HF!


UPD. А тем временем появился разбор: Div1,Div2

Поздравляем победителей!
Div1 - ilyakor 
Div2 - peter50216

И еще немного статистики. Первые успешные посылки и хаки по дивизионам:

Div1-A Dmitry_Egorov 4:09
Div1-B ilyakor 13:05
Div1-C A_A_Lunyov 8:05
Div1-D hos.lyric 30:57
Div1-E rng_58 75:20
hack VArtem 26:15

Div2-A epizend 5:27
Div2-B random.johnnyh 19:15:29
Div2-C RomaFurko 11:31
Div2-D peter50216  41:18
Div2-E peter50216 54:00
hack  diogen 55:33

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

13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Молодцы! Я верю, что раунд пройдет успешно. Желаю всем удачи-и организаторам, и участникам.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня вопрос, возможно не по-теме контеста: только у меня на главной одинокая надпись "Домен зарегистрирован", но все остальное открывается прекрасно? Это беда на сайте или опять наш провайдер что-то запретил?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Нажми ctrl-F5 - это закэшировано утреннее состояние сайта.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Значит прокси тупит. Спасибо
      • 13 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        Нет, это не прокси. Вчера вечером КФ и некоторые другие саратовские сайты отвалились из-за каких-то локальных неполадок и поэтому, насколько я понимаю, компания, делегирующая домен, поставила информационную плашку, что этот домен просто пока недоступен.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится
      А меня спасло ctrl+r
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
wow 7 problems.. nice..!! :D
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какие рамки 2-го дивизиона? Синие вроде в 1-м, но меня пускает только во второй
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Весело. Пытался зайти, но все время висела надпись "Домен зарегистрирован". Зашел только сейчас, но уже поздно...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Эта надпись была у вас закэширована. Лечилось простым ctrl-F5, сайт жив уже с утра.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    Да, обидно. А так хотелось порешать...
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Вождь Винни-Пух и бог Гомори-Ху ^__^
13 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

какие возможные баги в В?
у меня WA3 О_о  
 UPD теперь WA7 О_о 
UPD2 нашел баг, теперь не знал что можно писать что-нибудь типа typedef errtype a))) 
UPD3 сдал
и в С же должна Гранди заходить?
UPD по С вопрос снят, условия надо внимательнее читать :(
UPD2 не могли бы сказать, где баг в этом коде ? писал первый раз Гранди, может где накосячил...
сейчас не пашет для теста 873 - выдает вместо 18 6 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно забыть, что в typeof тоже могут быть & и *. У меня на этом валилось.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    мб такое?

    typedef a b

    typeof b

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а такой тест возможен разве??
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        "Попытка использовать не объявленный ранее тип данных так же приведет к типу errtype."

        видимо да)))

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

          я идиот!!!!!!!!!!!!

          UPD а почему тогда не RE... у меня тогда просто в мапе не найдется такой строки, должен быть рантайм!
          UPD2 да, понял, что вердикт абсолютно правильный
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Если в мапе нет ключа, то возвращается значение по умолчанию.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              спасибо... буду знать
              ВА конечно в мапе не искал :(
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              *и создается
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                А вот про это я не знал, спасибо. Я думал, что просто возвращается. Хотя логично - оператор = возвращает ссылку и должен создавать объект, на который ссылается.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            не runtime,и не только возвращается,а создается новый и заносится в map:

            map<int,int>x;
            int main()
            {
            int y=x[0];

            printf("%d\n",x.size());
            }

            проверьте так.

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              спасибо, я понял....
              читать условия бы еще научиться...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А почему нет? Если мы обращаемся к типу, который не был объявлен, то получаем errtype.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Как мне проперло то. Я этого не заметил и по чистой случайности обозначал errtype за null в своей мапе :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        А еще D прошла со временем 1970 мс (при тл 2 с)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Везунчик.
        И вот как такие ошибки ловить в тестах - непонятно :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Гранди вроде бы должна. По моим оценкам там что-то вроде n^1.5 получается, если через ленивую динамику делать.
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      да уж...
      я не сортил делители числа 2*l когда искал число Гранди для l...
      только после контеста заметил что k должно быть минимальным... 
      жду открытия дорешки, чтоб убиться об стену

      UPD не проходит...
      UPD2 теперь все нормально, Гранди коряво писал раньше
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        У меня без делителей...Достаточно смотреть k, пока выполняется (2+k-1)*k<=2*l. Это проверено, т.к. прошло систесты. Условие взято из того, что для правильного k l=(2*a1+k-1)*k/2
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Я убил минут пятнадцать, чтобы понять, что надо исправить правую часть неравенства с l на 2*l :(
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            У меня на это ушло минут 5, но тоже ничего хорошего. Буду упорно учиться складывать дроби...
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Можно и через обычную динамику, но тогда приходится подхачить немного %) У меня где-то 1,6 с на макстесте на сервере.
      И так, кстати, ИМХО, лучше. Сразу видно, в TL всё-таки влазит или нет. А если с ленивой - непонятно.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        У меня ленивая рекурсия зашла за 30мс. Жаль, что только в дорешивании
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      *извиняюсь, вижу, на это уже ответили*
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а если еще и сразу заполнить grandi[2^l] нулями, то вообще хорошо должно быть))
      я проверял до 1000, нельзя разложить кучки с количеством камней, равным степени двойки, и только их :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В D div 1 нужно было в порядке не возрастания длины рассматривать ребра, считать количества вершин по разные стороны от этого ребра, и брать максимум, по ходу удаляя ребра тяжелее текущей?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    Я делал наоборот (добавлял)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вот блин забыл вставить в sort() фун-ю сравнения для того что сортировать по невозрастанию =(
      • 13 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится
        Там на самом деле надо очень аккуратно с равными значениями обходится, в этом вся задача, собственно. Если бы не было равных она бы решалась в 2 строчи СНМом
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я во время контеста боролся с окошечком взломов? У меня после нажатия первой кнопки "Взломать" никак не получалось нажать вторую: я пытаюсь прокрутить вниз, но ничего не выходит...
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Мне в div.2 очень понравилась С(про метро с поездами). Спасибо. Хорошая задача.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Нам тоже она понравилась.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Мне условие понравилось. Выкинуть фразу, что девушки друг про друга не знают, и получается наш один хороший друг :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я пользовалась идеей, что если gcd(a, b) = 1 и b > a, то время когда поедят в строну b равно (1 + a)*a / 2 (в силу различных остатков) . А в сторону a = a*b - (время в сторону b). Если gcd(a, b) != 1, то разделим а и b на gcd и решим для них задачу. Ответ верен, так как ситуация отличается от исходной гомотетией в точке 0(на временной прямой) и коэф. 1/gcd . А при гомотетии отношения каждых кусков отрезков сохраняются.

    При взломе, стала читать решения других. Оказалось что многие решали проще и хитрее. Может кто-нибудь напишет отличную идею решения.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В разборе описаны две идеи.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        почему-то в моей комнате оказалось больше программистов)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ещё мы не собирались давать "4 6" в качестве претеста, чтобы проходили решения, забывающие про gcd. Но решили, что тогда у всех будет по 30 хаков, и всё-таки вставили его в претесты)
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

      Я сокращал a и b на НОД. Тогда числа получались взаимно простые, и a*n % b пробежит все возможные остатки. Тогда за a*b минут цикла юноша едет в одном направлении, если попадает в интервалы общей суммой 1 + 2 + .. + a минут, а в другом - (b-1) + (b-2) + ... + (b-a) минут (случай b>a). равенство возможно очевидно при b = a+1, иначе он едет к первой девушке


      UPD. Я математик, палюсь))
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, не мог бы кто-нибудь по C дать тестов, на которых ломали...У меня получилось много кода ;( хотелось бы его проверить
13 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Чорт, пару минут не хватило чтобы додебажить Д. Ждем дорешивания.
UPD. И она все равно упала, так что даже и не обидно :D
UPD. Минус 3 символа и оно зашло.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть идеи, почему этот генератор для Div 2 B получает 
"FAIL text charater should be latin letter, not "?


print 30, 30, 1

c = 97
for i in range(29):
print chr(c) * 30
c += 1
if c > 122:
print "b" * 29 + "S"
c = 97

print 500000


s = ""
for i in range(20000):
s += "B"
for i in range(20000):
s += "Z"
for i in range(10000):
s += "Y"
print s



Во время контеста мне сначала сказали "Пробелов не является латинской буквой.",
потом "Генератор выводит символы { | и }"

Проверял у себя и на сервере через вкладку "Запуск" - нет ни лишних пробелов, ни скобочек.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Ваш генератор обещает 30 строк в клавиатуре, а выдает 29. С чем связан именно такой вердикт как приходил мы понять не смогли.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Еще раз запустил, проверил и пересчитал - 30 обещает и 30 выдает.
      Там же кроме for i in range(29) еще дополнительно одна строка выводится print "b" * 29 + "S".
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У вас обещается 500000 символов в последней строке, а выводится 50000. Валидатор вычитывает 50001й символ, находит \r и сообщает, что это не латинская буква.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Старнно, я насчитал 29. В любом случае вы обещаете 500к символов, а выводите 50к.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Is DIV 1 .harder than combined  division previously.?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    May be.
    I think, it was at bit disbalanced: first two problems was simple, C was classical, D and E required a lots of code.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Can anyone explain how Div1-C is solved ?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Its a direct Grundy problem, no special tricks or patterns or observations needed. I'm (almost) sure you know grundy :).

        Fill the grundy table g[0...N] and each g[X] means you have a game of X piles. Try all possible moves, i.e., all possible K such that X = a * K + (K*(K-1))/2 , which results in subgames {a,a+1,a+2,....,a+K-1}. The grundy of the collection of these subgames is ( g[a] ^ g[a+1] ^ ... ^ g[a+K-1] ). Some coders just iterated and found this value, but you can simply maintain a prefix xor on g[ ] , say pg[ ] and get it using pg[a+K-1] ^ pg[a-1] in O(1). g[X] = the mex among all grundy values reachable from X. Complexity is O( n . sqrt(n) )
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Thanks for the reply. I'm familiar with grundy numbers, but I don't believe this problem is a direct one. Typically a transition in a game leads to another state of the same game, so we start by assigning grundy numbers to states (no xor operation is involved here) and then xor the grundy numbers once for the collection of initial games (an example is the knights problem here http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames). 
          While in this problem as each transition creates many states then we need to xor their grundy numbers to get the "combined" grundy number of this transition.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
блин, обидно, кучу раз слышал задачу типа С, и неудосужился прочитать как решать задачу такого типа...(
13 лет назад, # |
Rev. 7   Проголосовать: нравится +12 Проголосовать: не нравится

I like to compete in Codeforces.
This round may be easier than past round (Div2). Normally, I solve only one problem during contest, but today i solve  3 problems
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Вот я молодец :)
Сначала написал "почти верное" решение с желаем дооптимизить позже :) Забыл и радостно получил TL
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Вообще 15-ый тест порадовал. Я на нем видел как минимум 4 различных вердикта.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, на каком тесте в Div.2 задаче С ломали людей, которые использовали int и писали что-то такого типа: int nok = a * b / gcd(a, b)?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1000000 999999

    a*b идет переполнение.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    казалось бы, на любом - хотя бы a = 99999, b  = 99998 - уже будет переполнение при умножении.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Переполнение то будет, но некоторые люди писали так:

      int nok = a * b / gcd(a, b);
      int t = 0;
      int x = 0, y = 0;
      while (t < nok)
      {
      ...
      }
      if (x == y)
        cout << "Equal";
      ...

      Понятно, что на тесте 1000000 999999 переменная nok примет отрицательное значение. while не выполнится и ответ будет равен "Equal", что будет верно.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        чтобы получить переполнение больше 0 можно заюзать например 65536 65537

        PS: не знаю поможет ли это, не читал таких решений и не очень представляю)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Да я уже понял, что тупил и можно завалить тестом 1000000 999997, где правильный ответ "Masha", а неправильное решение с типом int выведет "Equal"
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Анти-qsort тест в D это жесть...
Печаль :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится +67 Проголосовать: не нравится
    Ну нефиг потому что. Может начнете писать с рандомом.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      А по-моему это называется Паскаль-анфрендли. С++ный то сорт (и явовский, полагаю, тоже) таким не завалишь. А зачем валить людей на алгоритме сортировки, я не понимаю. С таким же успехом можно было больше отвечать на вопросы по условию "read the statement", из-за этого задачу бы не сдал еще приблизительно такой же процент человек, как те, что завалились на анти-сорте. Но этого не делалось, потому что на КФ вроде бы другая политика. Непонятно мне..
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        Имхо, если человек сам пишет qsort, то пусть уж пишет рандомизированный...Как известно, код это меняет совсем немного.
        Codeforces имеет в целях в том чисел и подготовку к более продолжительным и серьезным олимпиадам, и если например на Всеросе ты теряешь 20-30 баллов потому, что не написал рандом в qsort, то становится обидно
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        А мне кажется, писать алгоритм, который в худшем случае работает O(n^2), и получать OK - это не правильно на ACM-подобных турах, которые проводятся на CF.
        Но это, конечно, моё мнение.
        • 13 лет назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится
          Ага, а еще можно подобрать тест, на котором валится кьюсорт с рэндомом без рэндомайза. Добавить рэндомайз - тоже одна строчка. Может его тоже стоит добавить? Свалится, наверное, еще пару решений.

          А еще есть хеши, которые в хучшем случае не работают, с суровым набором тестов слетит немало решений, квадродеревья, которые работают за квадрат и тп.

          Возможно, если ориентроваться на школьников на Всеросе, то это действительно хороший "воспитательный эффект.". Я просто поставил себя на место участника, словившего из-за этого ТЛ (участника - студента) и мне бы было очень обидно. Особенно учитывая достаточно лояльную политику КФ, и, в часности, то, что вы позволили проходить решениям в С с рекурсией. 

          ПС. Я в общем авторов ни в чем не хочу обвинять, автор никому ничего не должен. Просто лично меня такая политика, особенно в отношении кусорта, немного раздражает. Вот такое вот ИМХО.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +9 Проголосовать: не нравится
            Кстати, насчет хешей. Встретил один раз задачу в которой 2 разные строки дают одинаковый полиномиальный хеш по модулю 2^64 (строки специально подобрали), не зависимо от ключа который используется. Подумал, не дать ли где-нибудь задачу на это, чтобы хеши послетали, но потом одумался, а то каждый будет норовить такие тесты использовать и хеши больше не поюзаешь, это не круто :)

            Насчет qsort: по-моему здорово, что благодаря хорошим тестам, участники могут выявить слабые места в своих алгоритмах и исправить их в будущем, особенно на обычных тренировочных раундах, как прошлый. 

            Случайный выбор элемента гарантирует мат ожидание работы qsort O(nlogn). Не помню что там насчет фиксированного элемента, скорее всего не доказывается, могу ошибаться. 

            Мне, например, из-за того, что на контесте есть взломы, стремно использовать фиксированный seed для рандомизации в декартовом дереве, потому что увидев его можно сгенирировать тест на n^2. Почему бы не сделать код надежным не проиграв по сложности и размеру кода?
            • 13 лет назад, # ^ |
              Rev. 5   Проголосовать: нравится -13 Проголосовать: не нравится

              Это же не совсем тренировка - рейтинг ведь есть, поэтому поддерживаю наколовшихся на этом коварном тесте участников в праве на обиду.

              Даже с рандомизированными алгоритмами ведь вообще такая фигня, что если решить их позволять, то у какого-нибудь эпичного неудачника может не пройти, а если решить их не позволять, то жюри навряд ли сумеет сделать тесты, кототые валят по всем возможным рандсидам, однако это будет несколько проще сделать тем, кто будет взламывать, - ведь они будут видеть код (ну, это озвучил уже и предыдущий оратор). Да и неравноправие языков усиливается, ведь где-то есть встроенные рандомизированные алгоритмы, в которых этот самый сид зависит от погоды, а где-то нет (Java & C++ vs Pascal). Поэтому минусуйте меня семеро, но я скажу, что в идеале во избежание Q-срача надо не давать задачи, в которых требуется сортировка за O(N * logN), а во избежание хешесрача - соответственно, задачи, где вообще можно решать с ними, с хешами.

              Ну и ещё, кстати, такой момент. На ACM можно увидеть, что не прошло, и переделать. На школьной олимпиаде можно потерять только часть баллов. На TopCoder ограничения маленькие, там даже всякие лишние линии вместо логарифмов не повредят. А вот здесь, на Codeforces...
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Да, и получить на ACM бревно, на школьной олимпиаде -5%-10% от суммы своих баллов... совсем необидно!
                Насчет хешей и сортировок: у авторов же всегда есть решение, которое работает(!), значит видимо у участника ручки кривые, если не зашло то, что должно было
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Но у авторов есть тесты, куча времени и возможность проверки на всех тестах.
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              Стоп, независимо от ключа? o_O
              Т.е. пофигу, какое p брать в выражении a0 + a1· p + a2· p2 + a3· p3 + ...?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Например, в ЛКШ.А есть такого рода задача, которая не сдавалась хэшами, если брать по модулю 2^64.
                Серёжа Копеилиович на этих зимних сборах о ней говорил, помнишь?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А разве у таких строк длина должна быть не порядка 263?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Видно не должна, раз все ломалось независимо от ключа. Длина была порядка 2000 символов.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Тут важный момент, что писать детерминированный алгоритм, который работает в худшем случае за квадрат, и получать за это ОК - это лично мне не нравится. Любой может подойти, поизучать ход вызовов программы и всегда построить тест для взлома.
            А с недетеримнированными хуже - всё-таки анализировать рандомные значения как-то сложно.
            Просто я хочу донести мысль, что детерминированный алгоритм за O(n^2) в худшем случае ну ничем не отличается от неоптимального решения.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А у кого-то он может быть детерминированный в том смысле, что RandSeed фиксирован. Тогда те, кто знает, как работает генератор случайных чисел в данной версии компилятора, смогут такой код поломать, а другие - нет (и жюри тоже навряд ли, ибо код изначально не видит). Я вот не знаю.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            По-моему вполне нормальная тактика - добавить антикусорт тест. На мой взгляд гораздо печальнее, когда часть людей на антикусорте хакнут(вбить генератор для антикусорта - дело не хитрое), а у остальных решение пройдет систесты.

            Как написал Xazker - в контесте, где доступны хаки лучше лишний раз добавить рандомайз и обезопаситься от взломов.
            UPD. Ой, оказывается сходная мысль была уже написана kuniavski ниже.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не хочу повторяться, добавлял я эти тесты именно из соображений, что на более серьезном соревновании будет обиднее и.т.д. Хочу задать ровно один вопрос тем , кто считает что не надо валить Qsort за N^2, потому что это не принципиальная част решения и.т.д. Вам не кажется что если два человека в разных комнатах напишут так, и одного взломают а другого нет - будет обиднее, тому у кого упало?
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          По-моему это обидно ровно на столько же, на сколько и в случае пары участников, у одного из которых прошло(с рэндомом), а у другого нет(без), хотя разницы почти нету. 
          Впрочем, на самый мой первы вопрос "Зачем все-таки авторы так сделали?" я ответ получил, спасибо.
13 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится
Заработался, не смог писать раунд, да еще голова болела.
Смотрю задачи. Авторы молодцы, победителю слава!
13 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
Спасибо авторам за хороший контест. И удачи на сборах :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Присоединяюсь, задачи оч понравились =)))
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Мне тоже понравились задачи (не так часто со мной такое случается). Хотя задачи показались мне немного сложными для меня. Это скорее плюс, чем минус. Меня удивило то, что столько много людей умеют вычислять функцию Гранди.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится
        Похоже, у нас вышел удивительно всем понравившийся раунд  :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Спасибо, нам тоже понравилось)
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Не писал, но задачи понравились
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

UPD: Хватает и одного символа, ведь функция Гранди на всех тестах не первосходит 99.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to solve Problem D(Div 1)?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    There soon will be english version of analysis.
    Main idea is that we sort edges and add by groups in the graph, counting for each new edge all the paths that include it using DSU.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      What is dsu? I've seen that tag on a problem before but have never heard of it. (I've even solved a problem with that tag before and have never heard of it xD although I think I managed to find another way around) 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
   <code> 
    long long lcm ;
    int a,b;
    cin >> a >> b;
    lcm = (a/gcd(a,b))*b;
</code>
why does this overflows ?

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In pretest 3 for problem C, there is a voidddd which hasn't been declared, how should these cases be handled?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Great set :) 
So stupid mistakes in my code but I loved the problems.. Thank you
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
One General Question :: Is it good practice to use long long all the way , because that way I will sure that there will be no overflows. But is it good/alright practice ?

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Long long's are slower at about 3 times. So use it only when it's neccesary.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    long long's are much slower. You can get AC doing 5*10^8 operations with ints, but the same with long longs can get TLE. So you can do it if only you are sure, that your solution works fast enough to fit time limit.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А финальный тесты для первых трех задач div1 объединяются с тестами для последних div2?

Только что заметил, что моя D (div2) не проходит тест
1
typeof void*

Зато финалки прошла :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Немного не в тему, но когда будет дата следующего матча?

У меня сейчас 2 варианта: либо он будет очень нескоро, либо нам сообщат о нем очень незадолго до самого матча)

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По опыту могу сказать, что это предсказать почти нельзя. Так что, when it's done.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
great round, unfortunately It wasn't possible to be in the contest for me, because of the time(it is school time).
By the way, the link to the tutorials is wrong.
greetings
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Quick suggestion for blog posts: when posts are translated from Russian to English, http://codeforces.com/ profile links should be converted to http://codeforces.com/ links.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Another comment: Sometimes when you try to hack a solution, you cannot see the entire line because it is cut off on the right. Maybe you should implement wrapping text around.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In Div-2 (Prob - C) ,
When I used scanf("%lld%lld",&a,&b); --- it gave me wrong answer.
But when I used cin>>a>>b; --- the solution was accepted!!

What was the problem? Anyone please reply.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Actually, it is often written as a note to problem description - "Please, do not use %lld ..."
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      But they had not written this as a note this time around!
      That wasted my 25 minutes :sob:
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Codeforces rejects solutions that don't match regular expression (for example, if C++ solution doesn't have "main", you can't submit the solution). Is it possible to reject solutions that contain "%lld"?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится
          it is bad idea because somebody can use
          #ifdef ONLINE_JUDGE
          #define A "%I64d"
          #else
          #define A "%lld"
          #endif

          to test solution on his own local machine without changes
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Hey. I can't see the tutorials via that hyperlinks. I guess there need some modification from http://www.codeforces.com/blog/entry/codeforces.com/blog/entry/2121?locale=en to http://codeforces.com/blog/entry/2121?locale=en . Isn't it? :P
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
оповещение пришло на почту за два с половиной часа до контеста, когда меня уже не было дома. Обидно, что пропустил раунд
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Нельзя не отметить +180 за контест! Авторы просто молодцы, задачи супер!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Немного странно выглядит предложение
"Это будет необычный раунд, так как авторы контеста подготовили более пяти задач. "

в e-mail оповещении, учитывая, что уже несколько раундов таких было за последнее время
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    да уж, и учитывая высказывания  MikeMirzayanov  о том, что все следующие раунды будут проводиться по такой системе
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is it possible to start allowing hacks even in practice, like topcoder?

Concerning problem D,
I wonder if if final tests contained this type of a test:
We have a large tree with this structure -
4
1 2 1
2 3 2
3 4 3
It is a straight line tree with the largest weight edge at the bottom.
I m guessing final tests, skipped such a case. I could notice solutions without the use of DSU pass the system tests but fail this one.

Appreciate a reply.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I hope that in addition to this, we can actually see/download the test cases, instead of just seeing a number of '...'s at the end of large cases. Since sometimes I find my program can produce different results on my computer and on the site, I think this could be even more useful. Or maybe there is a way to do it unknown to me now?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hey can anyone let me know how to register for beta round #74 div 2 as m a newbie???