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

Автор Sereja, 12 лет назад, По-английски

Lets discuss problems here.

Теги tc, srm, 567
  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

По-моему, 500 как раз из разряда тех задач, о которых говорили в этом топике. Не знаю, как у остальных, а у меня всегда были проблемы с доказательством подобного рода жадностей. Это уже не первый раз на топкодере, когда я понятия не имею, как решать 500-ку, потом вижу что народ ее сдает очень активно и у топов за нее 460+ и я сдаю самую правдоподобную на мой взгляд жадность, которую можно написать за 5-10 минут.

Кстати, а как там строго доказывать решение?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Во-первых, пусть мы уже переставили буквы. Тогда нам надо назначить первой буквой в перестановке алфавита первую букву слова (если у нас есть уникальная буква, то мы просто можем поставить ее на первое место и выиграть, а иначе нас победят). Тогда надо все копии этой буквы поставить в начало, так как лексикографическое сравнение — линейный порядок, а так мы добьемся минимального из возможных префикса. Теперь есть слова, которые мы точно победили, а есть те, которые еще не победили. Ну и так далее

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А если у нас есть несколько кандидатов на первую букву, то какой выбирать?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        А неважно. Мы можем их взять в любом порядке и выживут только те соперники, которые выживут после каждого

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Да, теперь понял. На контесте завис именно на этом моменте и долго не решался кодить.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Мне моё объяснение нравится чуть больше Егоровского :)

    Пусть мы уже переставили алфавит. Тогда ясно, что каждое слово (и наше, и противников) нужно отсортировать в соответствии с этим порядком, то есть фактически заменить его на последовательность (количество 1-й буквы) (количество 2-й буквы) ..., которые опять же сравниваются лексикографически.

    Ну а дальше ясно, что нужно брать буквы так, что на очередном шаге мы берем ту, которой у нас больше либо равно всех оставшихся (иначе мы сразу проиграем), и выкидывать те, где у нас больше (потому что у них уже выиграли). А тогда ясно, что если букву можно взять, то взять её прямо сейчас ничем не плохо.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Мы долгое время пытались решить эту задачу без ограничения на равную длину строк. Может, есть идеи как её решать в этом случае?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Мне кажется, тут надо один момент уточнить. В общем случае (когда строки не равной длины) может оказаться, что мы выбрали символ, которого в нашей строке не менее чем в каждой другой, но он был для какой-то другой непобежденной строки последним. Тогда она очевидно лексикографически меньше нашей и мы проиграем. Но когда строки равной длины, такой сценарий невозможен, так как тогда в той строке какого-то другого символа было больше и мы её бы уже до этого выкинули.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -41 Проголосовать: не нравится