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

TopCoder SRM 486
Автор Egor, 14 лет назад, По-русски
26 октября в 19:00 MSD состоится очередной TopCoder SRM. Всем удачи!
P. S. Я приболел, потому не постил анонсы контестов. Теперь снова буду
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Хорошо что выздоровел, а то тут полно желающих ВыКЛАДывать анонсы :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Минута до начала. Блин, давно ТопКодер не писал. Нервничаю аж
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А я уже испугался, что Вы забили на анонсы. Как-то уже привык. Сразу после контеста ищу тут тему, чтобы пообсуждать его. :)

P.S. Хорошо, что выздоровели. Больше не болейте. :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, я решил понтануться, писал 45 минут, не успел вторую сдать :(
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
Эх, по-моему задача 1000 сегодня была классная.
Можно было 100500 неправильных эвристик придумать. Я, например, перебирал 2 точки, проводил прямую через них. Все точки выше брал в первую часть, все ниже во вторую. И еще перебила куда отнести точки, лежащие строго на прямой.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Ну так это правильное решение. И ничего классного в этой задаче я не вижу
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А, ну вот перебирать не надо на самом деле
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я лично такую задачу вижу впервые... =( Можешь объяснить как её толком решать, и  почему это правильно? 
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я ещё двигал концы разделяющей прямой на eps по нормали к прямой. Тогда перебирать нужно только n^2 прямых.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Их и без передвижений на eps надо перебирать O(n^2)
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    1000 не очень классная. 1) Даёт преимущество тем, у кого prewritten code, 2) Безидейная, 3) Тяжело придумывать челленджи, даже если видишь, в чём у человека бага.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Обычная такая 1000 в духе 200ых-300ых SRMов.
      1. Да, это не дело, конечно.
      2. Нормальная идея, но на 1000 не тянет. В районе SRM 200 может и потянула бы.
      3. Отличный челлендж из 1 точки всё-таки не может не радовать.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, с возможностью для челленджей было сегодня всё в порядке.

    В 450 можно было написать динамику по отрезкам исходного массива, а не по отрезкам значений, и на сэмплах был тот же ответ. Для меня это оказалось ~-175 за ресабмит, +100 за челленджи... не так уж плохо. Привычка уже: если работает на сэмплах, сначала послать, а потом понять "блииин, в условии же просят совсем не то!"...

    В 300 lex-порядок многие проверяли неправильно.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А в чём в 300 был неверна проверка порядка?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну если его проверять или проверять неправильно (с конца, например, добавлять + раньше *), то на [1024, 65536] может получиться "/+****" вместо "++++++". Если не проверять длину, на [512, 65536] получится "+++++++" вместо "/+****".
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ах вон оно что. Я даже не подумал, что здесь можно набажать, т.к. сравнивал сначала длины строк, а потом сами строки через compareTo. :)
          → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Лекс. порядок в 300 на шарпе это вообще жесть...

      Вот код на C#:

      System.Console.WriteLine( "*".CompareTo("+") );
      System.Console.WriteLine( "+".CompareTo("-") );
      System.Console.WriteLine( "-".CompareTo("/") );

      Теперь вопрос: что выведет эта программа, если известно, что лексикографический порядок символов такой: *, +, -, /
      → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
А я писал 450 без динамики (через сумму вероятностей что пара чисел зачтется) в несколько строк но забыл взять обратную перестановку поэтому она упала:(
Странно что все писали динамику.

А 1000 правда оч плохая и безыдейная.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну все таки почему безыдейная? просто такая идея была много раз уже, когда надо точки на 2 множества разбить таких.. Кто не видел, тому сложнее, кто видел - проще. с другой стороны казалось бы - простая, а сдало то не много) так что не очень плохая, наверное. Но все таки наверное на 1К не тянет, вот на 900 бы в самый раз
    → Ответить
14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Проясните кто-нибудь, как в 300 на тест (5, 40000) получается ответ +*+ ?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    в правильном решении никак, а в не правильном как угодно
    → Ответить
  • 14 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится
    Правильный ответ:
    +*+*
    5 + 5 = 10
    10 * 10 = 100
    100 + 100 = 200
    200 * 200 = 40000
    Посмотрел на сайте, и вот она один в один вставка оттуда:
    5, 40000"+*+*"Passed
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Синим стал... Видимо я по жизни синий:)
→ Ответить