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

Автор Egor, 14 лет назад, По-русски
В эту субботу, 26 июня, в 20:00 МСК состоится второй отборочный раунд TCO 2010. Желаю всем удачи
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Думаю, в этот раз задачи будут посложнее чем в Round 1. А следовательно, мне вряд ли что светит, в 350 войти нереально. А жаль, так хотелось получить майку...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ну в первом раунде были задачки не очень сложные. 250 и 500 надо было решать.
и вообще, там главное будет решать быстро и без багов, а то решишь столько же, сколько и 350ое место, а не пройдешь... вот это было бы обидно
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не проспать, не проспать! :о)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Фантастика! Я каким-то макаром решил 2 задачи, занял 218 место и прошел! :)

Мааааайкааааа!!!

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Поздравляю :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    задачи неожиданно оказались простыми
    по крайней мере первые 2
    нужно было просто аккуратно закодить

    кстати чтобы получить футболку нужно поучаствовать в следующем раунде, который состоится 10 июля (сбб) в 20 00
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Мне задачи очень не понравились, если честно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Согласен. Первая - баян, вторая - какая-то совершенно безыдейная.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну если задача безыдейная, значит нужно было ее очень быстро решать. Минуты за 2 например :-D
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Безыдейная != двухминутная. Хотя согласен, топы должны были закодить её быстро.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Почему безыдейная? Там амортизация была, которая сильно упрощала жизнь. Жаль только, что я её во время контеста не усмотрел... Хотя её многие не усмотрели, но другим хотя бы хватило ловкости рук закодить альтернативное решение. :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не совсем понял, какая амортизация?)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если вы вообще не знаете, что такое "амортизационный анализ", то можете почитать, например, вот это: http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/amortized-analysis-2004

          А в задаче амортизация проявляется в том, что мы можем перебрать все подходящие для представимого числа пары чисел из упорядоченного массива "супернечетных" чисел за O(n), где n - размер этого массива.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да нет, знаю. Да, я понял, о чём Вы говорите, я так и писал, но там легко заходил и просто перебор всех чисел массива с бинарным поиском пары для него, так как массив-то там очень скромных размеров получается.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Фокус в том, что амортизация там помогает обойтись даже без бинарного поиска, просто тупо перебираем пары используя два индекса, устанавливая их вначале на противоположные концы массива, а затем последовательно приближая друг к другу. Такой подход позволил некоторым сделать самые быстрые сабмиты по этой задаче.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Да, да, я же говорю, что именно так и делал. Впрочем, мне это совершенно не помогло сделать быстрый сабмит)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ух... давно я так не сливал халяву... :D
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Сколько я не напрягал зрение, не видел что снегоуборщик в 250-ке едет только из нулевой вершины и просто проверил что все ребра в одной компоненте связности. Но решение прошло!
http://pastie.org/1020138
Я вижу почему. А вы?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    оригинально, да, 2 баги скомпенсировались. Если 0 - пустая компонента, то там получается, что найдено на 1 больше чем надо
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      При этом при наличии других компонент разность падает сразу на 2, то есть -1 становится :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Ты мой исходник посмотри! Я к ответу прибавлял количество вершин, в которых степень нечетная (не считая при этом входящие ребра), но оно прошло :о)
    Таже история что у тебя - эта ошибка закрылась ошибкой с лишним знаком восклицания :О)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А сколько народу кроме меня 500 решили за линию от длины числа? :о
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня за квадрат. А как за линию решать?
      А вообще прикольно - я там понаписал такой фигни, смотрю - а 500 сдала толпа народу. Я профигел немного, честно говоря
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обидно, что 1000 за 80^5 с маленькой константой проходят, а с немного большей - нет.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    у меня лично время работы не зависит от входных данных.
    то есть, я запустил, сразу увидел, что работает 1,5 сек, и посубмитил.
    прошла
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Какой-то чувак у меня в комнате прикололся:

"Если я пройду в следующий раунд, сборная США выйдет в финал ЧМ" :)

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
вообще, раунд вполне адекватен =)
две задачи надо было решать.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну как сказать адекватные - в первой задаче надо было очень внимательно читать противоестественное условие, ничего не упустив. Посмотрите, у скольких крутых людей она попадала, при том что и идея, и реализация элементарные. Такую задачу можно ещё дать на что-нибудь с правилами ACM, где получив WA сможешь ещё раз перечитать условие и исправить; но с топкодеровскими правилами imho так не стоит делать.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В каком месте условие противоестественное?
      Хорошая турнирная 250. Идея элементарная, но весьма красивая. Хотя это легче заметить новичку, конечно, а то вон выше "баянами" обзываются.
      Не умеешь доказывать и/или тестить  –  получи Failed System Test, хоть ты сто раз крутой.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В каком месте условие противоестественное?
      Хорошая турнирная 250. Идея элементарная, но весьма красивая. Хотя это легче заметить новичку, конечно, а то вон выше "баянами" обзываются.
      Не умеешь доказывать и/или тестить  –  получи Failed System Test, хоть ты сто раз крутой.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вебдваноль такой вебдваноль
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ну, например я как то пропустил, что трактор в вершине 0 сначала стоит и считал, что могу в начале положить его куда мне хочется... в итоге меня зачелленжили.

        конечно, мне надо было спать перед контестом побольше:) но для такого формата малозаметное предложение в большом условии - подлость, имхо))
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, для топкодера подобное "западло" в условии редкость. Хотя конечно же надо было читать условие и было бы мне счастье)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я все-же не соглашусь по первой задаче. Задача простая, а условие довольно понятное. Единственное что, его надо читать построчно, сверху вниз и слева направо. Просто уж слишком много развелось на ТК ковбоев кодеров, которые стреляют от бедра читают условие первой задачи "по диагонали". Все прекрасно осведомлены о том, что тут не ACM и второй попытки не будет, так что если в погоне за быстрым сабмитом кто-то что-то не так понял, то это только его проблема.

      Я думаю такое большое количество не прошедших сильных участников связан со второй задачей. Проблема в том, что у нее куча решений, в том числе и всяких мутных эвристик/разборов случаев. Но опять же, никто не мешал тестировать задачу по-нормальному. Хотя бы до 1000 прогнать и сравнить с брутфорсом. Тот же Томек упал на тесте "10", куда это годится?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Офигеть можно, у многих топовых участников какие-то исключительно запутанные решения медиума. Я просто сгенерировал все "абсолютно нечётные" числа до X  и потом искал ответ за линейное время от их количества.
        Или взгляните на решение NALP'а, о котором он уже писал здесь: дёшево и сердито)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я все-же не соглашусь по первой задаче. Задача простая, а условие довольно понятное. Единственное что, его надо читать построчно, сверху вниз и слева направо. Просто уж слишком много развелось на ТК ковбоев кодеров, которые стреляют от бедра читают условие первой задачи "по диагонали". Все прекрасно осведомлены о том, что тут не ACM и второй попытки не будет, так что если в погоне за быстрым сабмитом кто-то что-то не так понял, то это только его проблема.

      Я думаю такое большое количество не прошедших сильных участников связан со второй задачей. Проблема в том, что у нее куча решений, в том числе и всяких мутных эвристик/разборов случаев. Но опять же, никто не мешал тестировать задачу по-нормальному. Хотя бы до 1000 прогнать и сравнить с брутфорсом. Тот же Томек упал на тесте "10", куда это годится?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ага, по первой задаче я сколько не вчитывался, не увидел этот 0, хотя искал его глазами.
        А в 500-ке у меня заумное решение, но я как раз проверял до 1000 брутфорсом :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    :) не можешь, не можешь :)
    По раунду - 1ая мне кажется отличная - то что надо для 250 - прочитай (внимательно, я вот не внимательный сам, но про 0-старт увидел), догадайся, что надо только сумму выдать и -1 отсечь. 2ая то почему безыдейная? Многие писали дп. Например я написал проверку, что число можно разложить динамикой.
    То есть в отличие от того года, задачи были приятные :) Хотя 1 раунд мне понравился больше)
    PS Поздравляю Владимира Чалышева aka cmds с получением красного рейтинга вчера))))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только я не могу сейчас комментарий оставить?