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

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

Вчера вечером делегация Саратовского университета вернулась из Питера, с полуфинала чемпионата мира по программированию ACM-ICPC NEERC 2010/11. Если кто-то еще не видел результаты: все 4 саратовские команды получили дипломы, а мы (Saratov SU 2) вышли в финал. Команда Saratov SU 1 тоже попала в число выходящих в финал, что довольно круто для их первого раза, но не едет из-за ограничения "одна команда на один университет".

А еще мы подготовили Div. 2 раунд. За оперативную помощь спасибо Эдварду Давтяну, Геральду Агапову и Марии Беловой.

Всем удачи!
Артем Рахов и команда Codeforces


К сожалению, было обнаружено несоответствие авторского решения и условия задачи E. Приносим свои извинения всем участникам соревнования. Все решения, не получившие Accepted ранее, были перетестированы. Спасибо участнику xcr за обнаружение проблемы.
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Всем удачи!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
GL&HF^^
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Что значит отказ тестирования?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
что значит ошибка представления?...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вероятно вы вывели лишние данные или вывели строку, хотя ожидалось число. Возможно, вы вывели недостаточное количество данных.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Касательно задачи С вопрос:

Будут ли билеты, склееные из кусков (например) (123 + 321) и (12 + 3321), считаться разными билетами??

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, номера получившихся билетов могут совпадать.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Сори

(перечитал условие)

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А разве можно взламывать решения участников, которые участвуют вне конкурса ?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Участники вне конкурса помещаются в отдельные комнаты. Это значит, что ни вне конкурса не могут взламывать конкурс, ни наоборот. Но конкурс может взламывать конкурс, а внеконкурс может взлымвать внеконкурс.
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Спасибо авторам за задачу D. Давно я так не веселился:)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Из-за чего веселье? Мне вот совсем не весело - меня по ней взломали.
    Можешь подсказать, в чем угловой случай состоит?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      1 2

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня правильно обрабатывает этот случай. Проверил все маленькие тесты - не нашел баги.
        Я даже забеспокоился, вдруг мой вывод 10000 чисел через System.out.println() медленно работает.

        Вообще, в моем решении было 3 случая.

        if (n % 2 == 1 && m % 2 == 1) {
         строим один телепорт
         идем змейкой до (n, m)
        } else if (n % 2 == 0) {
         идем по вертикали - потом змейкой
        } else {
         идем по горизонтали - потом змейкой

        В чем я неправ?
        }
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нашел ошибку, отменяется вопрос.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Если n=1 и m>2 и m%2=0, то телепорт строить все равно надо, хоть одно из чисел и четное.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            У меня такие случаи обрабатываются отдельно, но мое решение все равно завалили, хотя оно полностью идентично решению caustiQue. Печально.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Меня взломали на таком - 2 1 (ну или 1 2)

      Выдать нужно

      0

      1 1

      2 1

      1 1

      А у меня телепорт строился =) Но я быстро исправился.

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

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

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Действительно, фантастика, я считал, что моё решение неверное с первого взлома и до конца контеста.
    Теперь дошли руки проверить и оказалось, что эти угловые случаи обрабатываются...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо авторам за контест.
Задача D мне ужасно не понравилась. Тупо всех ловили на частных случаях. Не самая достойная задача для D на соревнованиях такого типа. Хотя на ACM такое бы сошло на ура.
Можно пожалуйста претест 4 к задаче Е?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне не понравилось то, что если я решу за час все задачи, я не могу уйти. Я должен всё оставшиеся время сидеть, нажимать "F5" и высматривать новые посылки. На минуту отвлёкся - 300 очков потерял, например.

    На TC такого нет: 30 минут покодил, ушёл, вернулся, почеленжил минут 5, ушёл.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Еще бывает так, что ты уже нашел ошибку и с радостью бы отозвал свой сорс (все равно исправленный уже пишешь), но нет! Кто-то еще может успеть сбить на тебе очков!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      извини, но в первом дивизионе такого скорее всего не будет)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если будет контест на деньги, то вероятней всего так и будет. Я не хочу чтобы мой результат зависит от времени сдачи задач другими участниками.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Контест за деньги, что за чушь?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Пиши чисто, и твой результат не будет зависеть от времени сдачи другими участниками. Что вобщем-то выполняется и в ТС.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если бы я всегда мог решать за час все задачи, я бы был счастлив.
      Ну а вообще что поделать, таков формат, человеку нравится — участвует, не нравится — не участвует. По крайней мере так обычно происходит.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Someone can paste the Pretest #6 for the problem D?
I can't figure what is the problem with my solution...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
задача Е решается инверсиями?
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
/ a.out 
1 2
0
1 1
1 2
1 1

./a.out 
1 4
1
1 4 1 1
1 1
1 2
1 3
1 4
1 1


14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
I wonder if it wouldn't be better to have a possibility to lock the problem and start hacking without passing pretests, even without submiting it.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I think it wouldn't be better, because in your case contestant can use 2 accounts: one for stealing solutions from another, second - for submitting stolen solutions. Now for getting solutions from competitors, even cheater have to write solution which passes pretests
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How do I prove for problem D that when both n and m are odd, we can't find a required path without using teleporting gates?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Well, let's look at board painting. Every turn we change color of cell, in which king stays. So, for odd n and m cell at n*m turn will be black. n*m+1 turn must follow us to (1,1), which is also black. So we're used to place at least one gate.
    • 6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In the above comment, the board painting refers to visualizing the board as a chess board with the cell at (1, 1) being colored black.

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

    Another way to prove this is by noting that the graph is bipartite.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могли бы вы подсказать тест 8 задачи E и тест 11 задачи D?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Тест 8 в E:
    6 896922
    8 295 313 551 122 299 965 189 619 139 566 311 427 47 541 411 231
    5 743 210 82 451 921 124 792 397 742 371
    7 173 247 608 603 615 383 307 10 112 670 991 103 361 199
    2 190 209 961 892
    2 821 870 186 982
    5 563 456 293 568 247 955 134 787 151 877

    Тест 11 задачи D:
    1 100
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Give me 23 test for E, please
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's final test 25 at problem D? Thanks..
  • 14 лет назад, # ^ |
    Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится
    I don't know. But I can assure you that if your code passes the following types of inputs, it should pass all the inputs,
    odd even
    even odd
    even even
    odd odd
    1 2
    2 1
    thanks to HackSon.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      I think "1 even" and "even 1" are not precise enough...
      1 2
      2 1
      1 M
      N 1
      where N, M > 2.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      I have it done more complicately, so it's giving me Time exceeded.. but i think it should handle it for every 1<=n, m<=100
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    99 99
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Сижу ломаю голову над А. Можно 15 тест?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и 30 тест пожалуйста!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      99 голов, из которых 49 забила одна команда.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    33
    OWQWCKLLF
    OWQWCKLLF
    OWQWCKLLF
    PYPAS
    PYPAS
    PYPAS
    OWQWCKLLF
    PYPAS
    OWQWCKLLF
    PYPAS
    PYPAS
    OWQWCKLLF
    OWQWCKLLF
    OWQWCKLLF
    PYPAS
    OWQWCKLLF
    PYPAS
    PYPAS
    PYPAS
    PYPAS
    OWQWCKLLF
    PYPAS
    PYPAS
    OWQWCKLLF
    OWQWCKLLF
    PYPAS
    OWQWCKLLF
    OWQWCKLLF
    PYPAS
    PYPAS
    OWQWCKLLF
    PYPAS
    PYPAS
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно 6 тест в задаче С?

никак не пойму.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    6
    94861402 89285133 30745405 41537407 90189008 83594323

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

я чего-то непойму почему в задаче С во 2 примере ответ 1?

Там ведь можно собрать 123 231 1023 2310. Или я ошибаюсь?

14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Будет ли опубликован разбор задач?
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Hi to codeforces team

why you don't put test case's and problem's(in PDF) after each contest ?

it's usefull for every one ....

thanks for attention
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И всё-таки какой тест №6 в задаче D?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Congrats on making into the finals!! 9 Problems done, that is pretty impresive.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Today I participated "out of competition". I have 2 questions:

-My solution got hacked by another div1 contestant. So....does this mean I'm able to hack any other div1 competitors? Cause I didn't see any one in my "room".

-Am I able to see the case that got me hacked during competition?

Thx in advance
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    To see other "out of competition" contestants in your room you should check box, that doing it (in top right corner).
    Hack protocols availible at "Hacks" tab by link in "Verdict" column.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If you participate 'out of competition', then when you enter the contest you appear in room number 1 instead of the room you were assigned to. (It's a bug.) To move into your room, select it from listbox in top right corner, it's marked with a star.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone explain me problem C, I couldn't program it and ended up getting -2, how about a contest analysis after every contest?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Let C[i] = # of integers in A1...As.t. Ak = i (mod 3)
    Then answer = C[0]/2 + min(C[1], C[2])
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Previous explanation is for problem B. As regards C you just have to pair numbers a, b when:
    a % 3 = b % 3 = 0 or a % 3 = 1 and b % 3 = 2. In such cases (a + b) % 3 = 0.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могли бы вы подсказать тест #9 задачи D???????
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Не все "полные решения" по задаче E проходят следующий тест:

2 5
3 2 1 1 1 2 1
3 1 1 2 1 1 2

Правильный ответ - 0. Некоторые решения выдают 1
Тест корректный?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, корректный.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, мы уже достаточно коллективно с этим согласились.
      Если считать, что на такой тест правильный ответ - 0, то решение получает WA23.
      То же решение с 1-кой по такому тесту у меня получило Accepted
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      В этой теме уже обсудили это недоразумение, но авторы контеста оставляют его без внимания. Надеюсь, что хотя бы отсюда может быть они увидят, что в условии (или в решении жюри) нашли ошибку, которая вполне могла повлиять на исход контеста.
14 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
Ждём раунд 43.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Несколько странно, что проходило решение D за L*N*(b+f), при чем за 50мс..