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

TopCoder Open Round 3
Автор Egor, 14 лет назад, По-русски
10 июля в 20:00 MSD состоится третий отборочный раунд TopCoder Open. Всем удачи
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Восьмерочка в первой задаче была отличным тестом :о)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ога, дайте 2
    Хоть штука прошла и то хорошо
    Помню у меня с начала выступлений на топкодере был какой-то дикий по длине стрик из прошедших 250к. Вот такая бы точно его убила
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вообще буквально недавно была задача про игру типа там кучки и брать можно степени четверки из них. И там тоже восьмерочкой всех ложили.
      Отсюда урок - сдаешь задачу на топкодере, проверь на восмерке :о)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Мне вот вообще показалось, что в этом раунде самая простая задача - 1000 о_О
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, по крайней мере мне кажется проще 500.
          → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, хороший тест. Мои blind челленжи принесли +7*50-6*25. Хотя, наверное, не стоило ACRush-а челленжить :)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Веселый получился раунд. Самое удивительное, с 0 очками я получил + в рейтинг.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
бррр, как по мне - один из самых нервных раундов. Я нервничал, что не знаю, как решать 250, что моя 250 неверная, что не знаю как решать 500, что не придумал быстрого решения 250 с произведением 2 простых ( и славно что не придумал ) и прошел бы, если б кодил быстрее, я нервничал, что сделал неудачный челлендж, без которого наверняка прошел бы, и когда я все-таки каким-то чуком прошел, это вызвало только нервный смех))
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Объясните решение 500-й. Никак не могу понять :(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Во-первых, если никто не телепортируется, то ответ - максимум из всех расстояний.
    Если кто-то телепортируется, то всегда будет один кто сделает это первым (по условию нельзя
    в один момент времени телепортироваться более чем одному человеку).

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

      Не понимаю :(

      А если у нас будет 2 цикла? Разве всегда все люди могут пойти куда им хочется?

      Ну вот такой тест:

      первый чел в (0,0), хочет в (0,1)

      второй в (0,1), хочет в (2,0)

      третий в (2,0), хочет в (0,0)

      четвертый в (5,0), хочет в (5,3)

      пятый в (5,3), хочет в (8,0)

      шестой в (8,0), хочет в (5,0)


      Если рассуждать, что все, кроме одного выбранного человека могут телепортироваться куда хотят, то второй цикл даст 0 к ответу (каждый телепортируется куда хочет, и всё), а в первом цикле оптимально пустить первого человека пешком, а остальных телепортировать. Итого получится ответ 1, хотя казалось бы, ответ должен быть 3 из-за второго цикла...


      Или я жёстко туплю :)

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Место выбранного человека не потребуется в дальнейшем. Можно его сначала телепортировать в цикл, "разомкнуть" цикл и затем выбранного человека телепортировать туда, куда ему надо.
        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Слегка другая идея. 
    1. Телепортироваться имеет смысл только в начале. Действительно, если принц телепортируется в более поздний момент времени в позицию другого принца, то ничем не хуже  переместиться к этому же самому принцу в начале и дальше перемещаться вместе с ним.
    2. Для каждого принца найдем среди начальных точек наиболее близкую к его конечной точке. Получим функциональный граф. Проблему создают циклы длины > 1. Если есть вершина со степенью входа 0, то можно использовать ее для "размыкания" циклов.
    3. Если есть циклы длины >1 и нет вершины со степенью входа 0, то нужно попытаться заменить одну из дуг графа на вторую по оптимальности для данного принца. Заметим, что при такой замене обязательно появится вершина со степенью входа 0. Поэтому всегда достаточно одной такой замены.
    → Ответить