Блог пользователя ivan.popelyshev

Автор ivan.popelyshev, 14 лет назад, По-русски
Отнимаю хлеб у Егора :)
СРМ номер 498 состоится 26 февраля 20:00 GMT.
Удачи!
  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А я уж боялся, что эта тема не появится.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а что бояться? почему бы самому не написать в свой блог?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Интересно за сколько часов до TopCoder SRM 500 будет создана тема о предстоящем соревновании. Это все-таки очень крупный юбилей для TopCoder =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я надеюсь, они каких-нибудь goddie's раздадут. Причем не за жеребьевку, а за результаты
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, обидно.. почему то арена слетела... пока грузил.. короче опоздал зарегаться на 40-50 секунд :(
14 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
история маленького фэйла :)
благодаря плагину moj я все делаю в MSVS
дак вот, я первый раз пишу нормально с этим плагином, поэтому зашел в арену только чтобы отсамбитить 250
нажал submit и не потрудился посмотреть на сообщения которые вылезли
воткнул в лажу только через 15 минут, увидев результаты комнаты - перед сабмитом я не нажал compile!!
обидно за свои ~40 баллов )
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    все равно тупейший баг О_о
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Обычно принято тестировать девайсы перед использованием.
      Когда изобретешь свой самолет, смотри не взорвись при взлете.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        да, теперь понял это )
        видимо когда тестил (мало конечно), не отложилось в голове
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну и как нормально решать 1000? У меня была идея и неотлаженный код.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну включения-исключения по количеству плохих шагов. Если все шаги (включая 0,0) - хорошие, то трив. Дальше включения/исключения, надо быть аккуратным с коэффициентами и ещё аккуратным чтобы не словить TL. Надеюсь, у меня прокатит...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, именно это писл. Но багов былооооо :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А вот как посчитать для произвольного числа шагов? Я только для одного придумал, с квадродеревом, хотя наверняка можно и без него.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я правильно понимаю, что в sh first == second для любого элемента, и, соответственно, d[i][j] == 0 для i != j?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, я как обычно стал писать код, не вчитываясь в условие :) d[i][j] == 0 при i != j заодно обеспечивает нормальное время работы.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я просто не могу понять какого гладиолуса у меня точно такой же код не проходит семпл :)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Нет, ну то есть он, очевидно, не точно такой же. Ошибку у себя я ищу, короче
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Посеял один из множителей
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Перемудрил я 500 :(
Все нормальные люди пихали в мап строку из расстояний или вообще сам вектор расстояний, а я какого-то лешего хеш считать попёрся, ааргх.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    строка из расстояний у меня ловила TL на макстесте, поэтому я тоже хэш писал ;)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у меня 0.2 секунды
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Тем не менее меня с моими несколькими хешами it4.kp таки зачеллил :) Подозреваю, что по TL, я не спрашивал.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        В моей комнате челленджи были в основном из-за того, что люди факториалы предподсчитывали в слишком маленьких массивах.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет не ТЛ.
        Константа 500 маловата. Причем я специально этот баг и ждал :)
        Тест был заранее подобран где величина 792 участвует.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Странно. Я тоже хранил расстояния строками (но правда 1 расстояние -> 1 символ строки). На макс тесте было 0.4 сек.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Йа хеш написал. Посчитал, что со строками будет ТЛ
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Аналогично. Идея с мапом векторов/строк пришла сразу, но была отброшена, как неоптимальная, уступив место замудренной индексации массива.
    Несколько сбивает с толку стоимость задачи. Если бы она весила 300, я бы уверенно писал вектор.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
      Мне кажется, идея с отсортированным массивом векторов пооптимальнее, чем с мапом. Я без малейших сомнений написала и прошло.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А я так прикинул, что элементов в мапе будет не более 200*200, а добавление/поиск и все такое за не более log(200*200)*50. Перемножим, домножим еще на 10, т.к. stl, получаем 3*10^8 простых операций. А топкодер до 10^9 операций жует.

      Ну, потом я все же макстест загнал. Было меньше 0.5 с.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я тоже понял, что это решение пройдет, но уже на стадии челленджей. На контесте по невнимательности отбросил.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Тоже занимался псевдо-оптимизациями. Потом хотел прикрутить хэширование... В итоге просто забил и написал тупой сорт векторов.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я делал на всякий случай по 2 хешам и нормально прошло
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, похоже у TopCoder будет новый рекорд по числу участников. Сегодня зарегистрировано 2050 человек минус те, кто не решал скорее всего превзойдет предыдущее значение 1891. Может это из-за того, что на Codeforces тоже рекорды пошли? =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    насколько я понял по недовольным репликам за несколько минут до окончания регистрации, 2050 участников - это топкодеровский предел; желающих было немного больше

    кстати, Геннадий снова одержал! поздравления!
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Особо "порадовала" 950 в диве 2 :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Совершенно нормальная задача, просто многие пропихнули
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать 450? Я решал как-то, у меня TL на одном из систестов. Сейчас чуть переделал - теперь на другом :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Расклассифицируем все камни по их состоянию - вектору расстояний до отмеченных точек.
    Тогда камни с одинаковыми состояниями можно менять между собой как угодно, а с разными - нельзя в принципе.
    Тогда подсчитаем все существующие на доске состояния, и для каждого - количество камней с таковым состоянием.
    Ответ - произведение факториалов количеств по всем состояниям.

    Большинство хранило состояние как string или vector<int> в качестве ключа в мапе. Другие считали хеш этого вектора расстояний и записывали его как ключ. И то и то проходит.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блин, реально проще, а я к прямоугольникам переходил(
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    *FACEPALM*
    *WALL*
    *SAD*
    *OTHER_BAD_ACTIONS*
    :(
    Всё, понял. В лоб при помощи map. Гррр. Перемудрил. Очень. Сильно.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ну чтоже... у меня примерно +45 к рейтингу...

с моей скоростью печати и багами - даже вполне неплохо) хотя место нужно было лучше занимать...
вообще, этот раунд удивил задачами, они были необычайно простыми)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    И, обрати внимание, почти совсем без легенды. Прямо контест твоей мечты :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      шутку оценил)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Контесты без легенд - контесты моей мечты. Сегодня я даже без гуглтранслейта обошёлся
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А у меня аргх из-за разницы в компиляторах. В 250 один чувак в комнате обращался к seq[1], не потрудившись посмотреть, что такового может и не быть. В "Студии" это однозначно сегфолт, а вот в g++, оказывается, нет... И причём я далеко не один такой, кто на этом -25 получил.
P.S. Итого +28, ну, тоже ничего.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я два таких бага видел в комнате, но заметил что в одном из случаев runtime должен выдаваться на любой "YES"-тест и не стал челенжить.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Я ещё подумал, что TopCoder хуже того места, где мы сейчас находимся, из-за отсутствия кнопки "Запуск" и возможности менять код после кодинг-фазы.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и в релизе упадет под мсвс?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      В релизе не упадёт.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ну так что никакой разницы..
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        У меня вот такой код падает. В релизе. Точнее, по сборке из командной строки с ключами /EHsc /O2 /D_CRT_SECURE_NO_DEPRECATE (хрен его знает, этот MS, вдруг и это влияет). 2008.
        #include <vector>
        using namespace std;
        int main() {
            vector<int> v;
            v.push_back(1);
            int a=v[1];
            return 0;
        }
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is your topcoder handle?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
мой первый TopCoder :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати как и когда там можно поучаствовать в High School?