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

Автор Egor, 13 лет назад, По-русски
Всем привет!

Сегодня в 20:00 по Москве состоится очередной TopCoder SRM
  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Спасибо что напомнил.
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
А в арене сейчас у всех российских участников часы на час отстают, или там какая-то настройка есть, чтобы часы перевести?
13 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится
А у меня не получится написать :) Буду празновать день студента!
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    Что же, многие сегодня будут праздновать, мои поздравления! Но можно успеть и матч написать, и погулять на славу (т.к. в Украине традиционно празднование=пьянка)

    P.S. Кстати, ты еще первую сессию не сдал - рано тебе день студента отмечать.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

    ой, заглючило

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Видать, и в правду отмечают. Зарегистрированных меньше обычного.
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Как решать 500 ?


  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Рассмотрим граф на суммах чисел на префиксах. Информация на входе эквивалентна куче ребер вида что-то меньше чего-то. Проверить совместимость утверждений = дфс. Ну и бинпоиск по ответу поверх надо накрутить.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А без бинпоиска разве не зайдёт? Там же ответы вроде совсем мелкие - не больше 2k.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        2000 * 2000 * 50 = 2 * 108 Операции довольно дурацкие. На тц компы конечно хорошие, но мне как-то с бинпоиском спокойнее.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Можно и без бинпоиска: храним, какие вершины достижимы из пустого префикса, добавляем новые вершины по одной и если добавленная вершина соединена с какой-то из тех, которые уже были, пускаем из неё дфс.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А. Тут мы нагло попользовались красивостью графа и сказали что если есть цикл, то есть цикл с 0?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Это довольно очевидно - иначе цикл можно подвинуть влево
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Странно, у меня на систестах решение упало по времени на "-1000 999", хотя тест "1000 -999" проходило успешно. А на моем компе оба теста проходят моментально (мой косяк). Какой-то особый фейл?

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

Вот это раунд! Я за все время не придумал, как решать 500, и чувствую себя дибилом.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится
    Фух, я не один такой)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ок, вы меня успокоили.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Особенно смущает время, за которое такие задачи решает Гена.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Меня лично больше смущает время за которое я ее сдал. Оно слишком большое. Задача то тупая как пень. По факту это Четность с тимуса, где ее сдали 2000+ людей.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Тоже сначала вспомнил о Четности. Потом вспомнил, что до сих пор не знаю решения четности. 

        Потом начал вручную выводить какие-то факты, ничего не придумал.

        Теперь, когда прочел решение, стало еще более стыдно за себя)

        Зато буду знать на будущее. Странное, что такую боянистую идею знали (или решили на ходу) так мало кодеров.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Я эту идею так и не придумал :) В итоге у меня там какая-то фантосмагорическая хрень, про которую я долго думал, что она упадет по времени (у меня локально 8с работает), но потом решил таки запустить на сервере - там на этом тесте 0.4 с
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я придумал за 10 минут до конца, но не время не хватило додумать, в итоге искал цикл отрицательного веса в графе где все ребра минус 1 - фордом-беллманом =) Так что получу TL на систестах :(
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Интересно, много ли кодеров сразу после начала челенджей побежали искать тех, у кого в 250 не учтен 1 корнеркейс:) Мне показалось, что очень много:)

И много ли таких, кто зафейлил 250 на чем-то другом)

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

    Думаю, все кто корнеркейс заметили его искать)


    Не очень расторопно получилось, еще б 1 взлом)

    На первом месте был синий, сдавший на 247, когда остальные на 243, но не  успел его снести, пока нажимал ОК, его вынесли(
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В моей комнате и с кейсом не густо (только 1 из 19), и мой мобильный интернет (нормальный только на выходных) не позволил поймать даже его.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Да челлендж фаза была лотереей: кто попал в того кто не учел, тот получил 50. Мне такое не по душе :)

  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    В моей комнате был человек, у которого корнеркейс был учтен, но его кто-то зачеленжил.

    Вот подстава, из-за этого кейса ресабмитнул 250, да и почеленжить никого не успел, всех до меня разобрали. Особенно обидно было, когда мою возможную жертву почеленжил другой за секунду до меня.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Почти для всех этот контест - кто быстрее вбил 250 и при этом заметил n=3. Я вбил быстро, но случай не заметил, упаду в зеленые наверно)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я едва не зафейлил 250 на проверке простоты, но ресабмит спас положение =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится
    Я походу единственный, кто написал решение не через разбор случаев. Для входного числа находим ближайшее непростое - near. К ответу прибавляем n / near . Рекурсивно запускаемся от числа (n - (n/near) * near).
    Это спровоцировало аж 3 челленжа.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Был человек, который написал просто while(просто) ответ++

      Тоже - 2 дефенда
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
В который раз убеждаюсь, что лучшая моя тактика во время челендж фазы: "не челенджить никого и ни при каких условиях".

Вот опять усугубил свое и так плохое состояние :(
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Подскажите пожалуйста, как решалась 1000 div 2?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится
    Я написал длинную арифметику (только сложение). Выходил по счетчику. Но это решение не верно, т. к. не проходил даже претест (на девять девяток - №1), написал "заглушку", но в системном тесте был еще один похожий тест ( 2007; { 1,2,3,4,5,6,8,9,0 }. Ответ: "777...777 (666 digits)"). Все остальные тесты пройдены. =\

    С одной стороны я не прав, с другой стороны все-таки обидно.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      А как ты понял, что все остальные тесты пройдены? Тестирование прекращается, если решение падает хотя бы одном тесте.

      Такое решение шансов зайти не имело, даже с кучей заглушек, так что не расстраивайся)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    BFS
    Состоянием будет пара (остаток, представление числа как строки).
    Изначально в очередь кидаем все разрешенные цифры  ( кроме нуля), запоминаем остатки.
    Теперь, пока очередь не пуста, вынимаем состояние из очереди, пробуем перейти в новое - допистаь в конец какую-то из разрешенных цифр. 
    Пересчитаем остаток : newRemainder = (oldRemainder * 10 + digitmodN. Смотрим, не встречался ли он.Если уже встречался, то мы его уже обработали и еще раз закинуть в очередь нам нету смысла - ибо мы перешли из такого остатка во все состояния на каком-то из предыдущих шагов, при этом длина числа была меньше, в итоге получится что-то типа цикла. 
    Если же мы выняли из очереди и остаток равен 0 - то это наш ответ. Лексикографичность обеспечивается тем, что мы рассматриваем числа с неубывающей длиной и добавляем цифры в лексикографическом порядке. BFS делаем пока очередь не пуста., если в итоге она оказалась пуста - то возвращаем IMPOSSIBLE.
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
а можно где то узнать кто автор контеста, и не из Перу ли он случайно?
а то уж очень смущает меня время сдачи задач(причем правильно) парня, который сейчас первый в Див. 2....
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
А когда систесты?
13 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится
Авось 1000 не завалится...
  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    И надо уже научиться включать голову при посылке 250... А то так и буду всегда как лох с одной 3й задачей.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    FFFFUUUUUUU.....
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
аааа.... 2 - неправильное простое число, из-за него всегда все проблемы
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    2 то неправильное? Вот 3 - неправильное!
    • 13 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      Не правда. проблема с 2-ой. Проблема в том что 3-1 = 2, а не в самой тройке.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну 3 - хотя бы нечетное. Я когда думал над 250, мысль была: "ну двух простых подряд не бывает, поэтому ответ 1 или 2", и как обычно забыл про двойку. 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По-моему более неправильное простоу 3, а 1 наоборот неправильное непростое)
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
А как решается div1-1000? Ничего лучше чем 250 * 50 что-то не придумывается.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выкидыванием минимальных столбиков-строчек.

    Берём минимальное число, для него считаем кол-во способов покрасить решёточку (кубической динамикой). Умножаем ответ на это число способов.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А если минимальных много?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Их немного - не более 100 :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Под много я имел ввиду больше 1. 100 утром было больше 1.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится
            Там простенькая динамика. Как только закончатся систесты - я закоммичу в архив и приведу ссылку
          • 13 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится
            А вечером?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Пусть есть n1 строчек и n2 столбцов с общим минимумом. Обозначим количество способов их заставить как a[n1][n2]. Заметим, что при выкидывании верхней строчки может выкинуться (перестать иметь правильный максимум) i столбцов следующим количеством способов:
            a[n1][n2-i]*(кол-во способов закрасить верхнюю строчку) * (кол-во способов выбрать выкинутые столбцы) * (кол-во способов расположить по ним остальные числа)

            Каждый из множителей легко считается.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

              • 13 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                Предыдущие строчки не могли выкинуться, т.к. тогда бы столбец не выкинулся - мы же рассматриваем наборы столбцов/строчек с одинаковым требуемым максимумом.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Хм. видимо я не понимаю динамику. Мы перебираем где поставить максимумы в строке и говорим что дальше в остальной строке и в столбцах может быть все что угодно?
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +5 Проголосовать: не нравится
                    Динамика призвана решить следующую задачу: дан набор строк и столбцов в таблице. Надо их покрыть числами не больше X, так чтобы в каждой строке и в каждом столбце X встречался хотя бы по одному разу.

                    Для каждой строки мы перебираем кол-во столбцов, в которых X пока не встречался, и в которые мы просто обязаны этот X поставить.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    На контесте немного не успел отдебагать, но в дорешивании сдал за O(n3*log(P)), где P - максимальный элемент в матрице. 
    Общая идея такова: сначала как и в написанных выше решениях рассматривается максимальный элемент, тогда задача сводится к подсчету числа способов расставить числа от 0 до P в фигуре типа уголка, так чтобы максимум в каждой строке и столбце был P.
    Найдем это число при помощи формулы включений и исключений.

    Пусть уголок имеет размерности как на рисунке.


    Тогда посчитаем число способов расставить числа от 0 до P, так чтобы какие-то i строк были плохими (т.е. максимум в строке < P), и какие-то j столбцов были плохие.
    Таких способов понятно F(i,j)=Pc1*(P+1)c2, где c1=i*a+j*b-i*j, c2=x*a+y*b-x*y-c1 (в этих i cтроках и j столбцах должны стоять числа меньше P, а в остальных клетках могут стоять числа от 0 до P, с1, с2 - количества клеток этих двух видов). Но тогда ответ это просто сумма этих выражений по всем возможным выборкам i строк и j столбцов, при этом F(i,j) входит со знаком "+", если сумма i и j четна и с "-" в противном случае. Но понятно, что выборок i строк и j столбцов ровно C(x,i)*C(y,j), где С(n,k)-биномиальный коэффициент.
    Все, таким образом для уголка можно посчитать ответ за O(n2*log(P)) просто пройдя двумя циклами по i и по j и добавив или отняв F(i,j)*C(x,i)*C(y,j). Также понятно, что общая сложность O(n3*log(P)) так как различных элементов в строках и столбцах O(n).

    Исходный код: http://pastebin.com/rFnZ5tPh

13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Поздравляю с победой!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    Спасибо
    20 минут думать, что у тебя упадет медиум, а потом оказывается, что нет - это прикольно
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Кто может подсказать, каков размер стека для Java на серверах топкодера?
13 лет назад, # |
Rev. 3   Проголосовать: нравится +104 Проголосовать: не нравится

С учетом последних результатов Egor'а (CF93,CF94,TC524), похоже, что в его плагине появилась кнопка "Solve" =)

  • 13 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится
    Она работает только если в контесте участвует Гена (как я убедился на примере 523го SRM)
13 лет назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

А есть ещё кто-то, кому именно на этот раунд не пришло по e-mail напоминание (хотя всегда приходило)?..


UPD (написан после первых трёх ответов).

Ну так, видимо, причину меньшего кол-ва участников надо искать в первую очередь в этом.