Блог пользователя goo.gl_SsAhv

Автор goo.gl_SsAhv, 14 лет назад, По-русски

Это мое первое участие в соревнованиях Codeforces, и вроде даже удачное. Задачки довольно простые, но на то он и второй дивизион.

В соревновании участвовало 404 человека, и сервер довольно долго проверял решения. Этот момент внёс некоторые особенности в тактику. Так, в условии задачи C, как я ни искал, я не нашёл того, что после "подсказки" никнейм с номером попадает в базу. Тем не менее я чудом угадал что имели в виду авторы. Т.к. я не был уверен в первом решении, я сразу поправил его и отправил снова, с другим пониманием условия. C задачей D я поступил так же, после первого сабмита рекурсивного решения, я написал второй вариант уже без рекурсии, из-за опасения тайм лимита и/или багов.

В итоге я послал 6 решений на 4 задачи и все они прошли все тесты. Это произошло главным образом из-за того, что очень много сабмитов, и система не успевает быстро их все проверять. Забавно, но это только увеличило число сабмитов, думаю не я один такой, кто посылал ещё решение, не дождавшись вердикта.

Надеюсь выбранная мною тактика не станет особенностью соревнований. В связи с этим предлагаю:

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

2) Рассмотреть возможность распараллеливания проверки.


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

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

    распараллеливаются разные участники, или проверка одного решения распараллеливается на несколько серверов?

    второе думаю может тормозить.

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

    но видимо ошибка где то в реализации, схема решения по моему рабочая?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Но ведь при сортировке подряд будут идти равные элементы. А если отсортированный параметр одинаков, а подстрока — возрастающая, то всё же два таких конверта не войдут друг в друга.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Пусть открытка это конверт с номером 0, остальные занумеруем от 1 до n. Теперь нам нужно нулевой конверт вложить в максимальное число других, ясно что отношение "вкладывается" не содержит циклов, т.к. размер того конверта, в который мы складываем должен быть строго больше по обоим измерениям.

    ДП: определим D(x) как максимальное число конвертов, в которые можно вложить конверт x, пересчитывается очень просто - просто перебираем конверт y в который непосредство вложим конверт x и D(x) = Max(D(y) + 1) по всем y в которые вкладывается x

    код:

    http://www.everfall.com/paste/id.php?hyznn3vt1bqm

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

      а я задачу не правильно понял значит)
      написал неправильное решение которое как то прошло три теста.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо. Всё понятно. Я сначала решал графами, но не проходило по времени на 25 тесте.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
о, Поздравляю с победой!)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, в задаче C была еще одна ошибка в условии: "Каждый запрос представляет собой непустую строку длиной не более 32 символов, состоящую только из прописных букв латинского алфавита."
В сэмплах же буквы строчные :)