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

TopCoder SRM 502
Автор Egor, 14 лет назад, По-русски
состоится 8 апреля в 5:00 МСК
  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
У 62го места 0 задач о0. Думал так только на кодфорсесе бывает=)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто нибудь может рассказать как решать 1000?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится
    Петя ;)
    → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    Я решил ее не до конца, но там можно заметить следующее:
    Пусть f(n,k,mod) = кол-во выборок к групп из первых н чисел с суммарным остатком мод.
    Если выписать таблицу f(N,k,mod) то можно заметить, что для фиксированного остатка числа с разными к либо все одинаковы, либо отличаются только в некоторых строках периодически. Кроме того сумма по всей строке равна C(n,k). Ну и наконец, по-моему, ответы отличаются только в строках с номерами кратными наименьшему делителю Н, на счет столбцов не уверен. В общем и целом там ответ равен C(n,k)/k+smth.
    UPD: Нет, таки зависимость сложнее, но по-моему по-прежнему завязана на делителях.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Как можно было так облажаться. Ну очевидно же что надо было сортить не по скорости убывания. Итого 162 место и -74 рейтинга. Лучше б выспался.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Хех. А я понял как надо сортить, но когда писал ДП забыл, что если делать в тупую то нужные данные подпорчу.

    Итого место ещё дальше и ~-110 рейтинга.

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А я вообще сначала не подумал, что их ещё и сортить как-то надо. Спасибо тестам из условия, а то ведь так бы поди и отправил =)
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня то же самое, только место где-то 100е и такой же минус ;)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
распостраненный косяк, а еще один - не юзать динамику, а набирать первые в порядке сортировки, пока время не кончится =) поэтому у всех и попадало
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, пожалуйста, как решать 500.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Отсортировать с компаратором, что, дескать, какую задачу надо решать раньше другой. Это будет корректно, ибо убывание очков линейно. А потом рюкзак.
    → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
    Отсортировать задачи по отношению цены штрафной минуты ко времени решения. Задачи имеет смысл брать только в таком порядке (в этом легко убедиться, выписав потерю очков для двух различных положений соседних задач). После этого простая динамика, берем или не берем очередную задачу. (Параметры: текущее время и текущий номер задачи).
    → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
судя по отзывам - хорошо что я решил забить:D

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

      Два часа искал тупую ошибку в коде. На момент начала раунда так и не нашел. Оценив свое состояние, решил забить на раунд. А то так же буду где нить в 500 тупую багу искать.

      Сейчас багу нашел. Не жалею, что забил))
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
таки новый рекорд на TC ) 
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Давно видимо не писал tc, пришлось два раза ресабмитнуть =) Даже не знаю, хорошо это или плохо
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А никто из тех, кто лихо умеет челленджить, не поделится секретом, как это надо правильно делать? Вот как у вас получается так быстро находить: а) баг; б) тест на этот баг? А если это делается блайндом, то как определить, в какой задаче его можно применять и как его сам составить?
(Хотя, впрочем, тут понятно, что самый честный ответ будет: "Ага, щаааас, вот так мы тебе и рассказали".)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В этот раз всё просто было - нету сортировки в 500 --> надо челенджить, а таких решений было много
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну допустим. Но ведь надо ещё и придумать конкретный тест.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        большой рандомный
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Как-то слишком самонадеянно это. Опасно. Моя бояться...
          → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно самому написать несколько жадностей и стрессом найти большой рандомный тест, на котором все они валятся.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ага. И вот этим, надо полагать, и выгоднее использовать плагины вместо того, чтобы колбасить в "Фаре" и копировать в "Арену"... Но ведь на онсайте вроде как толку от этого нет?
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится
            На онсайт надо еще попасть
            Потренироваться в онсайт энвайроменте можно и после этого
            Бтв, тизер работы моего плагина:
            И никакого unused code ;) (ну хорошо, toString в Rational возможно unused)
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Мда, и что, "стало" типа лучше, чем "было"? Ну замечательно, unused code нет, но это, ИМХО, чистой воды obfuscation. Или здесь уже типа "давайте все так делать, тогда всем будет понятно"?
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                А почему это obfuscation? Если бы вдруг захотелось написать всё это с нуля вручную - то не было бы obfuscation? А скопипастить из prewritten code?
                Тем более, что код абсолютно прозрачный и понятный. Obfuscation - это когда вместо "1" пишут "l", или где-нибудь в незаметном месте вставляют "#define min max".
                → Ответить
                • 14 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                  Я же специально написал ИМХО. Но если хочется объективности, можно, конечно, устроить голосование, кому какой код кажется более прозрачным - без работы плагина или с.
                  P.S. Ну, или, вернее, без всякого голосования, а просто принять к сведению, что жёлтый зачем-то вякнул ИМХОй против красных :)
                  → Ответить
                  • 14 лет назад, # ^ |
                    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                    Еще раз - первый код на сервере, очевидно, не будет работать. Потому, что ни Rational, ни CollectionUtils в Java нету. Плагин это все взял из моей библиотеки
                    → Ответить
                    • 14 лет назад, # ^ |
                      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                      Да вот это как раз не суть. Ну вот мой код, он написан голыми руками до последнего байта и при этом работает на сервере. Объём такой же (в смысле, такой же, как у твоего до обработки плагином). Неужели он для постороннего человека менее ясен, чем стопицот автоматически скопипасченных рутин?
                      → Ответить
                      • 14 лет назад, # ^ |
                        ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
                        Этанадписьсделананаправахрекламы
                        Ну так целью плагина не является упростить жизнь читающим (хотя читать это просто, ИМХО, особенно если поверить, что у меня в библиотеке нету багов в тех гениальных случаях, которые тут применены, и читать только основной код), а упростить его написание для меня. И при этом не нарваться на UCR
                        → Ответить
                        • 14 лет назад, # ^ |
                            Проголосовать: нравится +3 Проголосовать: не нравится
                          -----------------------------------------------
                          Не, ну как бы у многих любителей такого препроцессинга ведь свои библиотеки, там могут быть разные именования, да и хрен его знает, вдруг это действительно маниакально всё руками вот сейчас, на контесте, написано. Приходится читать, прежде чем валить... Понятно, конечно, что формально на обфускацию это не тянет, ибо вполне убедителен аргумент "мне так удобнее". Но, блин, иной раз бесит. Так вот открыл какого-нибудь синего по 250 - увидел два экрана кода - закрыл. При этом подумал: "Да и пошёл ты, всё равно на систесте упадёт" =)
                          → Ответить
                          • 14 лет назад, # ^ |
                            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                            Этанадписьсделананаправахрекламы
                            Вообще разговор куда-то не туда свернул. Я писал в ответ на замечание о пользовании плагинами вместо фара. Что вот, плагины могут еще и так жизнь упростить
                            Сурсы плагина (он хардкожено заточен под мою структуру проекта и некоторые вспомогательные классы) буду открыты 11 числа как только CodeChef закончится
                            → Ответить
                            • 14 лет назад, # ^ |
                                Проголосовать: нравится 0 Проголосовать: не нравится
                              -----------------------------------------
                              Да не, спасибо, не надо. Тут же стоит учитывать разницу в стратегии тренировок. Когда final combat ещё впереди, надо уметь автоматически доставать не плагином из библиотеки, а руками из подсознания.
                              → Ответить
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
138-ое место, некто lindamon, 249.05 за Easy. Судя по размеру решения и времени сдачи, у него скорость набора несколько тысяч символов в минуту)) Мне кажется, если уж читерить, то это надо правдоподобно делать...
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Из-за двух глупых багов опять не сдался медиум. В этот раз он был проще обычного.
→ Ответить