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

TopCoder Open Round #2
Автор Egor, 13 лет назад, По-русски

Добрый день.

Сегодня в 20:00 по Москве состоится второй отборочный раунд TopCoder Open. В третий раунд пройдет 350 участников. Всем удачи!
  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Что за Sponsor Track Round 2? Для тех кто не прошел в сам раунд?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Для работников спонсоров
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Кстати очень жаль, что нельзя пописать вне конкурса тем, кто уже вылетел. Никто не знает, почему TopCoder не предоставляет такой возможности(в отличии от Codeforces)?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Also top 350 will get t-shirts.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    I believe you need to participate in Round 3 to get t-shirt
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I believe that participating in round 3 will not be that hard. :)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Oh no, maybe it will be hard for me (if I qualified), because round 3 will be just 1 day before my wedding. :)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      participate = open at least one problem.

      If rating is not the main thing for you, then it's easy)

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        And what about such a curious but possible case: let's suppose somebody opens only some other's code during Challenge Phase - is it counted as a participation?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Behavior is counted as participation if round became rated for you
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Thank you Cap :) It is not an answer to the question. BTW, nice performing, I'm watching you :)
            → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

          Yes, intersting)))

          I know only this: "If you did not open any problem during the coding phase, you will not have your rating adjusted."

          But I can not find anything about this curious case...

          Anybody knows?

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

      That's how I missed a t-shirt last year :) I qualified for the round 3 and couldn't participate. I didn't ask someone to open some task for me because I didn't beleive the rules are so weird that just registering and opening a task (not solving tasks or something) is required to get a t-shirt.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        But if you ask somebody else to do something using your account, doesn't it violate the rules? (I amn't sure.)
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          I think it does. But hush, don't tell anyone I thought of violating the Rules :)
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Забавно выглядит разделение в списке зарегистрированных на первый и второй дивизион. Напоминает об обычных матчах, с разными проблемсетами:)
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Был 378-й и посчитал, что последняя надежда на футболку заключается в челенжах. Разумеется, получил -50. Интересно, напрасно...? :-)

UPD: так бы был 372-ым. Все равно напрасно...
Эх, надо быстрее крутить педали :-(
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    С одной стороны тут изи непадающая, поэтому надо было челленджить. С другой стороны изи непадающая, поэтому челленджить нету ничего
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      То-то и оно... Пытался две 500-ки на рандомных макстестах, но надежд особых не питал. Зато совесть чиста.. )
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Интересны решения 500 и 1к.

И можно ли 500ку делать в стиле (пришло за минут 10 до конца контеста в голову, так и не понял до конца нормально это или нет):

Взяли сгенерили первую строку и столбец, потом взяли все полученные строки, отсортировали лексикографически и сжали в 1 символ. И т.д. пока не дойдем до конца, а потом уже легко посимвольно посчитать, где какой символ.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1000 надо аккуратно посмотреть на все компоненты связности и все
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если бы на каждом этапе строки бы были одной длины всё было бы круто.... а так вроде это палево какое-то потому-что сравнивать сумму сжатых как-то не правильно...
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

      Любые 2 строки в таблице отличаются набором букв, потому не может быть 1 префиксом другой
      Фигня, не фигню можно увидеть тут
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    самая фишка - научиться сравнивать элементы (x1, y1), (x2, y2) из таблицы. я делал с хешами:

    бинпоиском подбираем общий равный префикс, а потом смотрим на следующую букву. у меня 2 функции самые главные: 
    1. char getChar(int x, int y, int64 pos)
    2. int64 getHash(int x, int y, int len)
    я думаю, что дальше все понятно
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Видимо, ты не использовал ограничение из условия про различные буквы в строках. Если использовать, то верен факт, что при попытки сравнения не окажется, что одна строка это префикс другой. Почему это так, мне не понятно, но это работает и заметно упрощает решение.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        да, этот факт я не смог прикрутить в свое решение =)
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        это так потому, что мы всегда либо сравниваем строки с одной диагонали или строку и буквы, причем буква не лежит в строке
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Почти так. Только я каждый раз обрабатывал новую диагональ, то есть (row + col) = fixed, просто склеивая строки (когда пробовал сжимать на каждом шаге, это не заработало). Затем сжимаем их, перенумеровывая их числами, например, и переходим к следующей диагонале. Ну и еще храним длину оригинальной строки, чтобы восстановить ответ.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
Этот набор задач был бы хорош для следующего раунда...А то всего 115 тех, кто больше одной решил.
Можно было бы 500 полегче дать =)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Да не нормальная 500я просто мы все затупили
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Нравятся мне такие раунды)))

Когда 250 плоская теория чисел, которую я быстро написал, но долго тестил (в результате 243.23), а 500 скучная, долгая и непонятная, поэтому ее мало кто решает, и на нормальный для низкорейтингового результат достаточно одной лишь 250.

Рад, что получил футболку надо бы разобраться с этой 500, а после окончания сессии будет время - и закодить надо бы)

Серию поднятий рейтинга мне обломает если не следующий матч, который на следующий день после экзамена (хотя и не страшно, сегодня был через 7 часов после экзамена), так следующий раунд точно. Так же я рад, что прошел в следующий раунд)

З.Ы. Да и ладно, есть +107, новый 1986, радуемся тому, что есть. Пока есть.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Забавно, я делал по 500-ке хеш по 4-ём разным базам, 4-ая выбиралась рандомно, от seed посчитаного из инпута. Winger не парясь сделал базу 37, я подумал что его челить бессмысленно, т.к. больше времени потратишь на подбор такого теста )
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что за четырехмерный массив все использовали в 500?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Какая строка больше - та, которая в ячейке i, j или та, которая в ячейке k, l
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ага, я тоже так делал. Преподсчитать первую буквую каждой строки - это, конечно, не для нас.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Как челенжить решение, в котором максимальная степень считается так log(n)/log(prime)?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Прогнать у себя на компе стресс, не?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это не будет компиляторозависимо? Или подобные функции одинаково везде реализованы?
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    В перерыве как раз можно)

    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    n=8
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    У меня кстати в комнате у одного, познавшего эпсилон кун-фу, такое решение даже прошло
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

Бывают же неудачники. Позорно долго сидел над 250ой, а потом не хватило считанных минут, чтобы дописать исправление в 500ой (не прошло всего 2 сэмпла). На челенжах на этом раунде делать было особого нечего. У всех одинаковое решение на 250 и туча кода на 500 или 1000. Слепыми челенжами сразу побежали те, кому уже нечего терять. И вот он я такой сижу 399ый и дрын мне, а не футболка. 

P.S. Решение на 500 зашло в практисе с первой попытки после того, как дописал то, что планировал.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    для тебя главная ценность - футболка? :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      думаю в этом соревновании у многих главная ценность-футболка, так как эти многие наврядли могут рассчитывать в прохождение в следующий раунд
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно рассчитывать пройти как можно дальше
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      К сожалению, да. Еще есть три аспекта:
      1) Рейтинг: получил -11;
      2) ЧСВ: опустилось еще ниже;
      3) Тренировка: решил две задачи сам, без всяких наводок, тут все еще более менее неплохо.
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Аналогичная ситуация. Долго не понимал, чего 500-ка не проходит 2 семпла. Оказалось, что я думал что строка s по-горизонтали, а t - по-вертикали. После контеста поменял и заработало.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Ого, я даже поднялся в рейтинге%)
Опять раунд на то, чтобы бешено написать 250 в первые 5 минут и уйти спать. Не люблю такие срм...
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Своеобразный стимул учиться решать более крутые задачи, чтобы после этих 5 минут было реально еще 500 осилить, а не идти спать.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это, конечно, да...
      Но когда поднялся/опустился в рейтинге (а в данном случае прошел/не прошел дальше) определяется буквально минутным затупом на 250 - как то не дело это.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится -16 Проголосовать: не нравится

        Согласен. Но когда получается аналогичная схема по сумме 2 задач - просто меньше в глаза бросается. Ну и тогда разница между 240 и 200 за первую компенсируется разницей между 350 и 400 за вторую, и все менее "случайно".

        Минутный затуп по 250 - это написать ее где-то на 235, ну пускай даже 225. 

        Дальше уже начинается "долго решал" и "ловил тупой баг".

        Сегодня надо было сдать 250 за 16 минут. Допустим, минута на прочтение условия, еще минуту подумать, минуты вполне хватает на написание Эратосфена (еще остается даже время почесать затылок и посмотреть на птичку за окном), дальше пускай еще 3 минуты на один цикл для степеней простых и прикручивание модуля. Еще, пускай, минута, на примеры з условия. И даже еще 2 минуты - собственные примеры (ну не знаю, что сюда вткнуть... макстест есть ведь в примерах... остается только минтест... да и все, пожалуй). Минута на размышления "сабмитить или еще потестить... сабмитить или еще потестить" и т.д.

        Получается 10 минут на спокойное, неспешное, адекватное решение задачи. Задачи, которая, как по мне, для АСМщика не представляется трудной. Разве что человек привык писать сложные структуры, реализации на сотню-вторую строк, а от математики весьма далек.

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится
          Под минутным затупом я подразумевал попадание на 20-30 мест выше и прохождение в следующий раунд.

          В остальном, вы, наверно, хотите потроллить меня в медленном написании кода)) В моем случае затуп был в том, что я не с той стороны начал решать задачу. Если вам в голову верное решение пришло сразу - что ж, сегодня вам повезло больше, чем мне))
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Вот именно, это все не без везения. Так что без обид:) А троллить... Да не настолько хорошо я пока пишу, чтобы можно было еще и троллить других) С рейтом ТС ниже стабильного высокого красного - нечего голову поднимать, это все ерунда, а не достижения. По поводу кодинга - вещь важная, но даже ТС не скотился до конкурса секретарок, что уж говорить об "более серьезных" соревнованиях.

            Просто мне показалось, что сегодня, с одной стороны, пройти дальше было очень просто; но, с другой стороны, проблемы с 250 (мало там что... ресабмит, допустим) очень портили жизнь, так как 500 была слишком трудной для большинства.

            Мне вот другое интересно, как организаторы матч этот планировали. Так и рассчитывали, на такой результат по 250? А то ведь не угадаешь. То народ слишком хорошо что-то сдает, то слишком плохо) Иногда задача тупая до невозможного, а сдают весьма слабо (250 с прошлого матча тому пример - лобовой перебор, по коду даже меньше наверное, чем сегодня...), а иногда - наоборот, что-то, что и писать долго, и совсем неочевидно, и условие запутанное... А сдают не хуже, если даже не лучше. 

            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              500 просто я думаю казалась авторам легче, чем она оказалась. В принципе опять же, если верно придумать - написать ее очень легко, тоже самое и в 250.
              → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              ==============================
              > Просто мне показалось, что сегодня, с одной стороны, пройти дальше было очень просто; но, с другой стороны, проблемы с 250 (мало там что... ресабмит, допустим) очень портили жизнь, так как 500 была слишком трудной для большинства.

              Собственно, именно это я и имел ввиду в своем первом посте. Поэтому мое отношение к таким срм, опять же повторюсь - не люблю.
              → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Мин тест вообще то тоже был в семплах ;)
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Видимо, я так спешил, что не заметил этого... И проверял минтест еще и вручную)

            В таком случае вообще ничего не надо было тестить, кроме примеров. Идеальная задача:)

            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              В решении, которое все писали, можно было написать решето до < n вместо <= n. Но комнаты с такими решениями редки.

              Ещё можно было что-нибудь рассмотреть отдельно и сделать это неправильно.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                По моему в претестах был тест где n - простое число, так что и этот случай тоже покрыт. =)
                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +15 Проголосовать: не нравится
                  простое было прямо первым тестом, а квадрата простого не было (можно же перебирать до корня).
                  → Ответить
13 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится
Я покраснел!
→ Ответить