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

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

Всем привет!

Сегодня состоится очередной codeforces-round. Он пройдет в обоих дивизионах, в каждом из которых будет предложено пять задач разной сложности.

В его подготовке, принимало участие несколько человек: KAN, fdoer, Skird, tunyash. Огромное спасибо Gerald, за координацию подготовки задач, множество клевых идей и понятизацию условий. Так же благодарю MikeMirzayanov за отличную систему подготовки задач, Delinur за перевод условий.

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

Удачи!

UPD: разбалловка стандартная (500-1000-1500-2000-2500) в обоих дивизионах.

UPD: появился очень кратенький разбор

UPD:

Поздравляю победителей! div1:

  1. tourist
  2. rng_58
  3. Mimino
  4. Dmitry_Egorov, Egor

div2:

  1. debug22
  2. ryz
  3. dvdreddy
  4. vinodreddy
  5. rdivyanshu

UPD: есть полный разбор на русском.

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

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

Надеемся увидеть хороший контест с интересными задачами)

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

На прошлом контесте была обычная, значит, сейчас динамическая.

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

Будут суровые челябинские задачи? = )

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

    Вроде, в прошлый мой контест кто-то так уже шутил :) Но он был не из Челябинска.

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

    Похоже что так и есть :)

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

Score distribution?

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

я смотрю, tunyash понравилось раунды делать

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

Давно хотел спросить, а почему информация о разбалловке в анонсе часто публикуется лишь за несколько (15-20) минут до начала раунда? Это делается с какой-то определенной целью? Или же создатели этих раундов настолько долго решают вопрос о стоимости задач?

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

    Скорее второе. Никто особенно не задумывается о разбалловке, пока участники не спросят :)

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

    А что Вам даст знание разбалловки за, скажем, 5 часов до начала контеста? Это поможет Вам лучше подготовиться?)

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

Надеюсь задачи будут интересными и из них можно будет узнать много нового.И хотелось бы пожелать всем удачи и высокого рейтинга.

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

usually every time they say : Score distribution will be announced a few minutes before the start of the contest.

it will be dynamic :|

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

Зарегистрировался в втором дивизионе, затем проверяю списки участников(зарегистрированных с одного дивизиона), а там меня нет. Как так?

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

Мне кажется, или автор переборщил со сложностью?

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

    Хотя мы в разных дивизионах, думаю, что не кажется.

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

    Мне тоже так кажется (после контеста скажу пару доводов, по которым я не стал решать задачи).

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

    И со сложностью проблемы, и с балансировкой тоже.

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

    Еще с серваком не все ок. Очереди на тестирование по 10 минут. Вкупе со сложностью просто сносит башню :)

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

    Первый мой контест в первом дивизионе — и ни одной решенной задачи :( Надо больше практиковаться.

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

      Согласен.Без практики никуда.Но и теорию надо знать)

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

    Согласен, грубо говоря 10/2000 = 0.5% участников решили D. Про Е я молчу. Довольно сложный контест по сравнению с предыдущим :)

    P.S.: Речь идёт о Div.2

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

    Крутые же задачи.

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

      Сами задачи мне очень понравились, но вот сложность довольно завышена

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

      Задачи хороши, но не для этого контеста :)

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

Any ideas on what is so special about Div 1 Task B Pretest 3?

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

    The same question about Div 1 Task C :)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      5 1000
      1 10000000000000000
      1 9999999999999999
      2 9999999999999999
      3 9999999999999999
      4 9999999999999999
      

      ответ:

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

        Спасибо. Все оказалось банально: int вместо long long...

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

клевый контест, жаль только, что задачи выше В перегробили

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

Как решалась D(div 2). Я вывел какую-то формулу, если k<=n, то c(n*n,k)*(m-n+1)-c(n,k)*(m-n). Верна ли она?

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

Мне кажется, или в A div 1 можно было не писать, что не требуется минимизация числа вершин? Решение от этого вроде бы не поменяется ведь.

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

    Ну мое бы перестало работать например. Оно ровно 100 использует на худшем тесте. 97560. Рекомендую проверить. Он забавный.

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

    Не думаю. У меня некоторая конструктивка, относительно которой я не умею доказывать, что с меньшим числом вершин сделать нельзя. Если бы это условие было, многие потратили бы куда больше времени на доказательство.

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

      Строго я и свое не умею доказывать :) Но кажется, что оно дает минимальное число вершин.

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

    У меня на худшем тесте было 101 вершина: я делал добавлением групп почти полных компонент и у меня возникала проблема в больших тестах (их много, но например 99994), где в конце мне нужно было добавить 3 треугольника, а на это уходило по моему алгоритму 7 вершин, пришлось написать ручками, чтобы было 6 вершин и тогда полный чек не выявил косяков.

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

      Ну да, посмотрел решения других участников и увидел, что не все писали минимизацию. Я думал, что простая жадность после постройки максимального полного графа + добавление нескольких треугольников выйдет за лимит вершин.

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

задачи хорошие, но сложнее по сравнению с прошлым контестом.

как думаете: задача С Div2 -- комбинаторика

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

Ideas for Div2 D ?? I was finding out a pattern that if I fill some N sized array by some arrangment , The same thing I could do with next N + N arrangement . This was going for matrix exponentiation. Altough I could not completely formalize it.

Was I going in the right direction ?? Or there is some other way ??

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

    Lets define F(C) as the number of colored cells in column number C. IMHO, the key observation is that F(X) = F(X + N) = F(X + 2N) and so on.. DP solution can be found, but I failed on pretest 3 as mentioned above.

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

      You mean to say that we could find F(X) by using DP and rest we have to do is exponentiation of F(X) by ceil(N/M)

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

    We can use dynamic programming here .

    state would be [cur_pos(0...n-1)][rema(0....n^2)]

    base case : dp[n][x] = 1 if x= 0 dp[n][x] = 0 if x!= 0

    recurrence : dp[i][j]= sum over x=0 to min(j,n) pow(nCr(n,x) ,ceil( m/n ) ) * dp[i+1][j-x]

    P.S : need to make sure that we don't use pow function every time and need to memorize it as base can have at most 100 distinct values

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

Мне одному Джон Доу кого то напоминает?

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

For div2-A, when n = 3, "2 3 1" seems like a perfect permutation, is there any mistake I made?

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

D — суфмас + дерево отрезков + структура, которая говорит, сколько на отрезке чисел, меньших данной? Хорошая задача, но, на мой взгляд, условие про непересечение явно лишнее. Оно не делает задачу более идейной, но прибавляет 10-15 минут тупого кодинга дерева, которого в этой задаче и без того предостаточно.

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

    суфмас + фенвик + спарс. Мое решение не меняется от отсутствия условия непересечения.

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

    отослал за минуту до конца, получил ТЛ6

    но в целом не обидно, потому что времени не было нормально писать, наверняка и так где-то набажил..

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

Опровергните идею по Е.

Будем решать в оффлайне. Зафиксируем некоторый столбец и будем рассматривать все запросы, которые начинаются в нем. По очереди рассмотрим столбец (больший или равный данного), в котором запросы будут заканчиваться. При этом считаем динамикой для каждой ячейки второго столбца минимальную и максимальную клетку первого, из которых можем добраться. Плюс ко всему считаем массив "можем ли мы добраться хотя бы до какой-нибудь клетки второго столбца из клетки i первого". И будем обрабатывать запросы следующим образом (на момент, когда первый столбец совпадает с началом, а второй — с концом): если из клетки-начала вообще не можем дойти до второго столбца — No, иначе рассмотрим минимальную и максимальную ячейку в первом столбце, из которых достижима нужная (во втором столбце), если текущая клетка лежит между этими двумя — Yes, иначе No.

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

    Я неудачник! Если в посылке, которая была на контесте, поменять компилятор на GNU C++, то решение получает AC :(

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

      Упс. А почему это работает? то есть, если клетка лежит между двумя достихжимыми, почему она тоже достижима?

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

        Там еще есть условие, что из клетки можно добраться до какой-нибудь клетки второго столбца. Тогда рассмотрим этот путь. Если он не идет в необходимую клетку, то он в любом случае пересекает либо путь от "минимальной" клетки, либо от "максимальной", а соответственно, по объединенному пути можно добраться до необходимой клетки.

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

          а, понял, классно. получается qn? у нас было более сложное решение.

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

кто-нибудь, кроме меня тестил свое решение на всех тестах?

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

    Я думаю, так делал автор контеста.

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

    По А? Я тестил. После сабмита, разумеется. С чекером за куб заняло минут двадцать, как раз хватило на написание B.

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

как решать Б лучше, чем n4?

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

    Мой n4 в запуске работает 1.6. Ключевой оптимайз — избавиться от быстрого возведения в степень, преподсчитав все {Cni}m / n.

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

      ну это само сабой, хочется еще быстрее (видимо не дп)

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

        Я не умею. Я долго думал, но не придумал. Попробуйте, вероятно, я чего-то не увидел.

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

    n4 заходит. Самая медленная операция  –  это (m % n), но её можно сделать один раз.

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

    Я, вроде, умею. В моем коде третий цикл легко заменяется частичными суммами. Разве так не у всех?

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

      Оп, как? Там же на разные степени цешек разные состояния динамики умножать.

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

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

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

System Test still pending :/ ... I am too anxious!

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

Спасибо за интересный контест! Побольше бы таких.

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

how long does it take generally for system testing to complete?

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

    I have seen very few system testing before. In my experience they all took around one hour. But today's system test seems really fast. I guess it will be done in half an hour. It's a new experience :D

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

Testing is so fast today

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

Я все понимаю, люблю интересные задачи, понимаю нелегкий труд проблем-райтера, но это реально чересчур сложные задачи.

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

Was difficult

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

2343173

Random? Или в этом есть какой-то смысл?

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

Зарегились 603, хоть что-то посылали 371. Только 60% писали раунд.

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

Very difficult div. 1 problems! Even for tourist, rng_58 and Egor!

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

    Score distribution should be 500 — 1000 — 2500 — 2500 — 2500 =)

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

      500 was not usually 500... It was difficult and not trivial. So, I think that score distribution should be 1000 — 1000 — 2500 — 2500 — 3000;(

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

Контест получился хорошим.Я узнал много нового.

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

Ох уж этот 12 тест к С...

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

Всех, кроме tourist, в Div 2! Даже оттуда не все задачи могут решить!

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

Solved only AB and second place...

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

По моему пора на сборах вводить контесты от участников....

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

ребята не зря съездили в А0, однако

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

past contest is much easier than this for div. 2

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

Тупорылый контест

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

    мало решил?

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

    "Ужасный контест. На самом деле, очень плохой контест. Я думал намного лучше будет, намного лучше будет все и очень плохой контест, просто очень плохой контест. Я думал намного лучше все будет. Сколько раз решать ходил! Было намного лучше. Ну на этот раз как-то не удалось. Во-первых решил мало, да и контест не очень."

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

По-моему что-то случилось с сервером, т.к. уже ооооочень долго тестируются последние 2 посылки...

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

Screencast. Начиная с 24й минуты тот еще треш

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

    Открывать вкладки в новом окне быстрее щелчком средней кнопкой мыши :)

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

      Спасибо, кэп. На тачпад не завезли

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

        Ещё можно удерживая Ctrl нажимать по ссылке левой кнопкой.

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

          Тогда тачпад иногда интерпретирует перемещения мыши как движения колесика, и начинается фантасмагория с размером шрифтов

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

        Во-первых, то шутка была, во-вторых, раз уж это так тебя задело, есть Ctrl+Click.

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

          Peace. Меня это не задело, мне просто такой комментарий показался странным

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

            А чего тут странного? Просто первая мысль, возникающая при просмотре этого скринкаста :)

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

        На самом деле кое-куда завезли, срабатывает при нажатии двух кнопок одновременно.

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

Is there someone who can tell me the direction to solve Div1.C ?

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

    Vertex |D(n-1)| + 1 is cutpoint. Because of this, if min(a,b) <= |D(n-1)| + 1 and max(a,b) >= |D(n-1)| + 1, path will contain |D(n-1)| + 1. We should solve same problem for pair (a, |D(n-1)|) (a, 1) (b, |D(n-1)|+1) and graphs with orders k-1, k-1 and k-2 respectively.

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

Hi, Div2 judge is stuck. please fix it. thanks

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

А по C предполагалось решение быстрее чем за O(t*n)?

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

    да, .

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

      Все я понял я тупой надо было просто брать min(n, 80) :-(

      Upd: прошла((( я реально тупой Upd2: кстати спасибо за раунд. задачи клевые

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

НЕ могу понять почему в задаче С ответ на тест где n=6 и a=1 и b=13 ответ 2.

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

Hi, I have a doubt in C div 2. For k = 3 why I can not draw a graph with 4 nodes and these relationships, (1 — 2 — 3), (1 — 2 — 4) and (2 — 3 — 4). Maybe I did not understand very well when statement says "A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". Thanks in advance.

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

    Then there will be cycle (1-3-4) and in total there will be 4 cycle but not 3.

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

    Try to draw this graph. To have cycles 123, 124, 234 you need edges 13, 34, 41. Which creates a new cycle 134.

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

    "A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". 1 is connected to 3 (from 123), 3 is connected to 4 (from 234) and 1 is connected to 4 (from 124), so your graph actually have 4 cycles of length 3 (123,124,234,134). CMIIW!

    Edit: sorry for reanswering a question, when I write this hza's and BOBAS' comments aren't there yet!

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

Did anyone else had a problem when challenging? I challenged someone and the verdict was something like "Judgement protocol not found or unavailable." This lead me to try to challenge the same code again, but then the previous challenge turned out to be unsuccessful... There goes 50 points :(

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

Или мне кажется, или в первом дивизионе переборщили со сложностью задач.

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

is this contest unrated ?

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

2 problems with no one solved them during the contest for both divisions!!! seems strange !!

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

Можете объяснить, почему моё решение 2348402 по D (Div 2) не заходит в тайм-лимит?

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

In div2 problem B , Can it be solved using binary search (for finding the value of x) ?

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

    I think no , because binary search property isn't applied here as there is no value of x the equation is true above and false below

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

    I don't think so.....

    x^2 + s(x)*x

    x = 8, 8^2 + 8*8 = 128 ; x = 9, 9^2 + 9*9 = 162 ; x = 10, 10^2 + 1*10 = 110 <- It drops here ; x = 11, 11^2 + 2*11 = 143 ;

    If the increase in value was uniform, then we could have used binary search. But now we can't be sure on which half the correct value lies.

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

    I believe you can't, since it's perfectly possible to have x * x + x * s(x) > y * y + y * s(y), even though x < y. For example x = 9, y = 10 : 9 * 9 + 9 * 9 > 10 * 10 + 10 * 1

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

    yes, if you use some delta to check the rightness of answer. my solution here

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

      the binary search in your solution isn't responsible for the result .. the loop after the binary search do all the work i think !

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

        binary search lowers the answer interval to [x-delta; x+delta], it is simpler than some solutions where is the answer within [sqrt(n)-delta; sqrt(n)+delta]

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

Слишком трудный контест для див2

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

I'm happy ... +149 points!!!

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

    Me too. I was progressing during four last contests, I gained 317 points in total and finally I'm in the first division :).

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

не смотря на то, что я не люблю графы, контест очень даже понравился

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

В задаче С div2/ A div1 не слишком слабые тесты?

Конечно, трудно угадать все решения участников, но делать набор тестов с N= 1..12, 99000..99025, 99999,100000 и еще 4-5 случайных тестов — маловато.

Например, моя эвристика падает в TL на тесте N=112.

upd. Минусуйте меня, я не то решение гонял на тестах... Финальное проходит и N=112, и все, что я в него догадался пихнуть, проблема снята.

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

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Интересно, а против моего рандомного решения есть контртесты??
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Максимум времени на тест — 1сек, всего возможных тестов 5*10^4. Немного терпения — и за 14 часов вы узнаете точный ответ на свой вопрос. )

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

          Чего 5*10^4, разве не 10^5?

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

            Запамятовал условие. Ну значит 28ч, суть не меняется.

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

    Просто основное что нужно проверить, это правильность построенного графа и не использовано ли более 100 вершин. Первое проверяется случайными тестами и максимальными, второе проверяется максимальными (ну то есть например 99994). А то что у вас падает на N=112 это просто что-то очень специфическое, что в данном случае просто очень сложно обнаруживается.

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

      Я не говорил о том, что надо в набор тестов включить все 10^5 вариантов. Но, чтобы повалить часть "специфических" решений, можно вместо 46 тестов сделать 100 и в появившихся накидать разного хлама (если не осталось осмысленных вариантов). На скорость финального тестирования это повлияет не сильно, а проверка будет полнее (имхо).

      P.S. Это очень странно, что моя задача работает больше 1с на тесте N=112, но мне лень прогонять её на всем диапазоне. Хотя и есть шанс, что на "средних" тестах оно будет валиться часто.

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

Looking forward to the editorial.

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

That moment when No one could solve C&E(Div. 1) :

Problem Designers: Problem??

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

will the Editorial be published?

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

всем удачи во всех ваших делах )