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

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

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

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

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

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

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

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

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

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

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

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

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

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