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

Автор goryinyich, 13 лет назад, перевод, По-русски
Всем привет!

Привожу разбор задач для раунда #78.

Еще раз приношу свои извинения за ситуацию с задачей B (div. 1) / D (div. 2). Также, приношу свои извинения за недооценку сложности задач. По крайней мере, надеюсь, что задачи показались участникам интересными.

Задача A (div. 2) - Помогите Тридевятому царству
В этой задаче необходимо округлить число по обычным математическим правилам, за исключением случая, когда последняя цифра целой части числа равна 9: в этом случае необходимо было вывести "GOTO Vasilisa.". Можно заметить, что для проверки того, что дробная часть числа не меньше 0.5, достаточно рассмотреть только первую цифру сразу после десятичной точки. Если эта цифра равна 5 или больше - мы добавляем 1 к последней цифре целой части числа, и задача решения. Возможно, самым удобным способом обработки входных данных (которые, как было указано в условии, могли быть очень длинными), было использование строковых переменных.

Задача B (div. 2) - Помогите Повару Герасиму
В задаче нужно было аккуратно проверить что требовалось по условию. Прежде всего, проверим, что все объемы компота во входных данных равны - в этом случае выведем "Exemplary pages.". В противном случае найдем два кубка с наибольшим и наименьшим объемами. Предположим, что их номера a и b, и объемы компота в них соответственно v[a] и v[b]. Теперь предположим, что до предполагаемого переливания их объемы были равны V. Тогда они содержали 2V миллилитров компота до (и после) переливания. Поэтому, необходимо проверить, что (v[a] + v[b]) делится на 2. Если это не так - выводим "Unrecoverable confihuration.". В противном случае присвоим кубкам предполагаемый объем компота до переливания: v[a] = v[b] = (v[a] + v[b])/2. Теперь, если только одно переливание было совершено, объемы компота во всех кубках должны стать равны, и мы выводим соответствующее сообщение "... ml. from ... to ...". Если объемы не равны, выводим "Unrecoverable configuration".

Задача A (div. 1) / C (div. 2) - Помогите Василисе Премудрой
В этой задаче необходимо найти количество различных раскрасок граней куба шестью заданными цветами. Вероятно, самое простое решение данной задачи - как то упорядочить грани (скажем, 0 - передняя, 1 - задняя, 2 - верхняя, 3 - нижняя, 4 - левая, 5 - правая), затем рассмотреть 720 = 6! размещений цветов по граням. Каждое размещение есть некоторая перестановка заданных на входе символов. Для каждого размещения мы находим все 24 возможных вращения куба с заданной раскраской - получаем 24 строки символов Лексикографически минимальная строка будет представителем этой раскраски. Ответ к задаче - количество различных представителей.

Задача B (div. 1) / D (div. 2) - Помогите Царю
К сожалению, первоначальное авторское решение данной задачи оказалось неверным. Однако, оптимальность нижеприведенного алгоритма была показана Knuth и Yao в 1976. Ограничение на n в задаче теперь изменено до 10000.
Процесс бросания монетки и принятия решений относительно того, какую из заданных n альтернатив выбрать может быть естественным образом описан бинарным деревом (возможно, бесконечным). Каждый бросок добавляет две новые ветки из каждой свободной вершины дерева (изначально, дерево состоит из одной свободной вершины). Каждый раз, когда количество свободных вершин становится не меньше n, мы превращаем ровно n свободных вершин в листья (по одному листу на каждую из n альтернатив), и продолжаем процесс с оставшимися свободными вершинами. Например, для n == 3 мы получаем следующее бесконечное бинарное дерево:
            o
         /      \
      o          o
   /     \      /     \
1        2  3        o
                     /      \
                   ...      ...
Теперь наша задача свелась к тому, чтобы посчитать ожидаемую длину случайного пути из корня в какой-нибудь лист в этом дереве. Можно заметить, что дерево рекурсивно: поскольку количество свободных вершин на каждом уровне дерева строго меньше n, ситуация (последовательность "срезаний" - то есть превращения свободных вершин в листья) будет повторяться с периодом не больше n. После того, как мы это заметили, вывести соответствующие формулы не слишком сложно. Поскольку числа в ответе могут быть порядка 2^n, необходимо реализовывать длинную арифметику, или использовать Java.BigInteger.

Задача C (div. 1) / E (div. 2) - Помогите Гному Грише
В этой задаче предполагалось численное решение. Но сначала нужно рассмотреть несколько случаев. Ниже без потери общности мы считаем a <= b.
1. l <= a <= b. В этом случае ответ ограничен длиной гроба, поэтому ответ есть l, и понятно, что гроб размерами l x l может быть пронесен через коридор (a, b) - будем обозначать размеры коридора таким образом.
2. a < l <= b. В этом случае ответ есть a, и понятно, что никакое большее число не может быть ответом. В самом деле, в противном случае гроб размерами (w > a) x (l > a) невозможно пронести через коридор (a, b).
3. a <= b < l. Этот случай наиболее общий, здесь мы должны повернуть гроб в месте изгиба коридора. Для максимизации ширины гроба, мы хотим перемещать его таким образом, что один угол гроба касается одной из внешних стен коридора (предположим, самая нижняя стена на рисунке к задаче), а другой угол, прилегающий к той же длинной стороне гроба, касается другой внешней стены коридора (самая левая стена на рисунке к задаче). Введем систему координат таким образом, что нижняя стена будет осью OX, а левая стена - осью OY. Предположим, что в процессе "вращения" один угол гроба находится в точке (x,0) (0 <= x <= l), тогда другой угол гроба должен быть в точке (0,sqrt(l*l-x*x)). И ответ, который мы ищем, есть min {расстояние от отрезка (x,0) - (0,sqrt(l*l-x*x)) до точки (a,b) }, где min{} берется по всем 0 <= x <= l. Обозначим расстояние в точке x за f(x). Поскольку f(x*) минимальна в некоторой точке x* и возрастает слева и справа от x*, можно использовать тернарный поиск для нахождения ее минимума.
В этой задаче возможно также и точное решение: задача сводится к минимизации косого произведения векторов (a-x,b) and (-x,sqrt(l*l-x*x)) по x. Однако эта задача сводится к нахождению корней многочлена четвертой степени, что, вероятно, не есть самое удачное решение в условиях 2-х часового контеста.

Задача D (div. 1) - Помогите монахам
Эта задача по мотивам известной головоломки "Ханойские башни", в которой диаметры некоторых дисков могут быть равны. Как же ее решить? Хорошая (и в то же время несложная) вещь, которую можно сделать - написать решение BFS-ом для проверки оптимальности ваших идей для небольших входных данных (кстати, BSF работает достаточно быстро практически для всех башен, имеющих до 10 дисков) и затем попытаться придумать оптимальный алгоритм решения головоломки.
Пусть C (x1, x2, ..., xn) будет решением задачи (под "решением" здесь мы подразумеваем оптимальное количество ходов - сами ходы могут быть легко получены с использованием рекурсивной процедуры; также "решение" есть количество ходов переместить группу дисков с одного стержня на любой другой стержень (а не какой-либо конкретный) ) головоломки, когда мы имеем x1 одинаковых самых больших дисков, x2 одинаковых дисков, вторых по величине, и так далее. И пусть U (x1, x2, ..., xn) будет решением головоломки когда разрешено не сохранять порядок дисков (необходимо соблюдать условие первоначальной головоломки не класть большие диски на меньшие, но в конце диски равного диаметра могут лежать как угодно).
Тогда одно из оптимальных решений задачи следующее:
C (x1, x2, ..., xn) = U (x1, x2, ..., xn) если x1 = 1 (*)
C (x1, x2, ..., xn) = 2*x1 - 1 если n = 1 (**)
C (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) + x1 + C (x2, ..., xn). (***)
U (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) (****)
Почему так? Можно заметить, что U() - "почти" решение нашей задачи: оно "переворачивает" группу самых нижних одинаковых дисков, порядок остальных дисков остается тем же! (попробуйте понять почему)
Поэтому верно (*).
(**) довольно очевидно.
(***) означает следующее: переместить (x2, ..., xn) со стержня 1 на стержень 2 без сохранения порядка. Затем переместить x1 одинаковых дисков со стержня 1 на стержень 3, затем переместить (x2, ..., xn) со стержня 2 на стержень 1 без сохранения порядка (но оказывается, что после того, как мы применим U() к той же самой группе дисков дважды, порядок сохраняется!), затем переместить x1 равных дисков со стержня 3 на стержень 2, и затем использовать C() для перемещения (x2, ..., xn) со стержня 1 на стержень 2 (здесь мы используем C() для сохранения первоначального порядка дисков). Так что (***) тоже верно.
А (****) довольно очевидное выражение для U(): переместим все диски кроме группы самых больших дисков тем же алгоритмом, затем переместим самые большие диски (вот почему если x1 > 1, порядок дисков в самой большой группе "переворачивается"), и затем переместим все остальные диски к группе x1 тем же самым алгоритмом.

Problem E (div. 1) - Помогите Крокодилу Гене
Эта задача была на оптимальную игру в эту "простую-на-первый-взгляд" игру. Ключевая вещь, которую нужно было понять - это то, что называть только карты, которых у вас нет на руках, не всегда оптимально. Иногда оптимально попытаться обмануть соперника, назвав карту, которая имеется у вас на рука. В этом случае... да, он может подумать, что карта, которую вы назвали - это карта на столе, и проиграть своим следующим ходом. Теперь задача - понять, когда выгодно использовать стратегию уменьшения количества карт соперника, когда - блефовать как описано выше и когда пытаться угадать карту на столе. Но вместо "когда" верный вопрос - "как часто", поскольку перед нами не что иное, как обычная матричная игра с постоянной суммой, и оптимальной стратегией является смесь этих трех стратегий (то есть, на каждом ходу - выбор одной из трех с некоторыми вероятностями). Но сначала сконструируем матрицу. Игрок 1 имеет три чистые стратегии: "игра" (когда он играет в игру и на самом деле пытается определить карты соперника и карту на стоде), "угадывание" (когда он пытается угадать карту на столе) и "блеф" (когда он пытается обмануть соперника, чтобы тот проиграл, назвав в качестве карты на столе карту, которая на самом деле в руке первого игрока). В свою очередь, если первый игрок использовал стратегию "блефа", или в результате использования стратегии "игра" случайно назвал карту на столе, его соперник имеет две альтернативы: "проверка" (то есть, поверить первому игроку, что он не назвал карту в своей руке и попытаться угадать карту на столе, назвав эту карту) и "далее" (то есть, решить, что это была стратегия "блеф" и игра просто должна быть продолжена, но с исключением карты, названной первым игроком, из списка возможных карт на столе). Обозначим P(m,n) вероятность выиграть игру, когда первый игрок имеет на руках m карт, а второй игрок - n карт. Тогда P(m,n) есть цена матричной игры со следующей матрицей (строки - стратегии первого игрока, столбцы - стратегии второго игрока):

                                  "проверка"                                    "далее"
"игра"              n/(n+1)*(1-P(n-1,m))        1/(n+1) + n/(n+1)*(1-P(n-1,m))
"угадывание"            1/(n+1)                                     1/(n+1)
"блеф"                            1                                       1-P(n,m-1)

Как получить числа в матрице? Рассмотрим первую строку: стратегия "игра" первого игрока, "проверка" второго игрока. Первый игрок просто называет наугад одну из n+1 карт. С вероятностью 1/(n+1) от называет карту на столе, второй проверяет ее и выигрывает (так что вероятность выиграть для первого игрока 0), с вероятностью n/(n+1) первый игрок называет одну из карт на руках второго игрока, и игра продолжается, второй игрок выигрывает с вероятностью P(n-1,m) в этом случае. Тогда общая вероятность выигрыша первого игрока с таким сочетанием чистых стратегий есть n/(n+1)*(1-P(n-1,m)). Так же точно заполняются остальные элементы матрицы. Затем мы решаем игру (это можно сделать либо напрямую, или одной формулой, если заметить, что стратегия "угадывание" неоптимальна в случае когда m>=1 и n>=1 и в матрице нет седловых точек) и получаем ответ для исходной задачи - P(m,n).
И последнее, что нужно заметить: когда m==0 понятно, что своим ходом второй игрок выигрывает, поэтому первый должен "угадывать", и P(0,n) = 1/(n+1). Когда n==0 P(m,0)==1 - первый просто совершает одно верное угадывание.
Разбор задач Codeforces Beta Round 78 (Div. 2 Only)
Разбор задач Codeforces Beta Round 78 (Div. 1 Only)
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Почему в задаче А (div2) такой код даёт WA127?
s = map(int, raw_input().split('.'))
if s[0] % 10 == 9: print('GOTO Vasilisa.')
else: print(s[0] + (str(s[1])[0] >= '5'))


(почему-то в первой правке видно лучше, хотя когда я разместил комментарий, было по-другому)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    "Длина записи числа не превосходит 1000 символов (включая точку)."

    А вы, по привычке, приводите к int. Можно было long использовать, но, вообще, приведение к числу тут не нужно. Навскидку:
    =========================================
    s = raw_input().split('.')
    if s[0][-1] == '9':
        print('GOTO Vasilisa.')
    elif s[1][0] >= '5':
        print s[0][:-1] + str(int(s[0][-1]) + 1)
    else:
        print s[0]

    P.S. Советую ознакомиться с этой штукой  http://www.python.org/dev/peps/pep-0008/
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо за ответ! Впрочем, я не очень понял: здесь написано, что int - это как int в C, а long уже имеет неограниченное число знаков. Тогда почему моя программа проходит тесты, в которых ~30 цифр в числе? К тому же, исправив int на long я всё равно получаю WA127.
      Приведение к числу действительно не нужно, но это же удобнее: одна ветка условия становится ненужной.
      Со рекомендуемым стилем ещё раз ознакомился, пока что есть привычка писать однокомандые действия в той же строке, эх.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone explain why the answer for the problem E (div.1) input (1, 2) is (0.5, 0.5)?
My assumptions:
1) (guessing) the answer is (0.333, 0.666);
2) (bluffing) If gena bluffs and it's the optimal strategy for him, Cheburashka knows that (he knows that this is the optimal strategy for Gena). That's why the second player easily evaluates the hidden card and the answer is (0.0, 1.0);
3) (playing) If Gena tries to guess one of the Cheburashka cards the answer is (0.333, 0.666).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    About point 2. Cheburashka doesn't definitely know whether Gena bluffed, or he used "playing" strategy and called card on the table. This gives some non-zero probability to win for Gena.
    About point 3. If Gena tried to guess. With probability 2/3 Cheburashka has card called by Gena, and Gena's probability to win is (1-0.5) = 1/2. But with prob. 1/3 Cheburashka doesn't have the card Gena called, and may decide that Gena bluffs, and then Gena wins. So, the overall probability for Gena to win is higher than 1/3.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      So actually there is some optimal probability for Gena to bluff or not to bluff (continue playing). Cheburashka may also calculate this value and use it to make his decision. In this case don't you think that each state will depend on one more extra parameter?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Yes, Cheburashka may also calclate this value. And he does so. But when you solve a matrix game you account for this possibility.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ok, so we still need to calculate that value (optimal probability of bluffing). Maybe I missed something, but I haven't found how to do that in the editorial.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            To solve the problem, you don't need to do that. Since you only need the value of the game - you calculate the value of the game and nothing else (how to do that - may be found in any book on game theory).
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              In this case I don't understand how to compute the value of the game using the strategy matrix you provided. All the strategies are chosen with different probability. So how to compute this "how often" values for different strategies?
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
About problem E.
(Am I correct, that with such a strategies infinitely long games are possible, but with the probability 0?)
Maybe I'm missing something, but I still don't understand. Why our position is determined by numbers n and m? We know the history of the moves of our opponent, so we can probably extract some information about his cards from his moves. I can't understand why we can consider a step-by-step game as a game on such a small matrix (as far as I understand, it is a game on matrix of size 3n + m + 1 × 3n + m + 1, rows and columns correspond to strategies). Can you write the proof more clearly? I.e., we need to prove at least that with our strategy like this any other strategy of our opponent would be worse for him (note that his strategy is not necessarily a function , as you assumed, but can be a function (he can use history)).
Another (and more challenging) option is to publish your code and I'll try to write a code for an opponent so that it would play against your strategy better than your strategy itself :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Sorry, I had no access to the Internet since Saturday, so I answer only now.
    1. No, with the strategies described the game ends in at most m+n+1 steps (see the formulas in the matrix - sum of indices decreases in each step). Only if we add some "dumb" strategies like "call a card which is already dropped out", you (theoretically) may get infinite games like "two guys sit and call the same once dropped cards", but such strategies will be dominated, so no player will use them.
    2. Your second question is answered by von Neumann minimax theorem. Since our (pure) strategies describe the whole set of actions players may do, any "history-base" decision methods will be just mixtures of pure strategies (your very sophisticated algo just chooses from this set what action to perform). And minimax theorem states that for constant-sum games like this one there exists value of the game V such that the first player can assure himself at least V, and second player can assure not more than V no matter what the other player does.
    If you are still not sure - you can write some this-game-playing environment and I will put strategy described for one of the players therein.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      The point is that we have a matrix game for each P(N, M). In your solution these matrix games are not connected with each other, because each matrix game corresponds only to one move. Can you prove that there is no strategy which uses the history of our game, i.e. the previous moves for different values of N and M?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Your opponent's previous move is known after your move. So, this is something like a full information game of matrix games.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          At each move you are trying to maximize the probability of winning with the current values of N and M. Why can't you make a move which leads to lower probability of winning with those values of N and M, but gives you some information about opponent's cards which you'll be able to use later to obtain higher probability of winning for some other values of N and M?
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Кстати, это русская ветка, что я мучаюсь?

            Смотри, у тебя в любой момент матричная игра, но состояние тебе известно, будто это игра с полной информацией. Таким образом, ты проводишь расчет, будто это игра с полной информацией, по дереву, т.е. в оптимизации данного момента ты учитываешь ВСЁ будущее, в том числе ВСЕ последствия любого твоего хода.

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

              Приведу небольшой пример.

              Мы играем в шахматы, только после каждого хода играем в матричную игру, матрица которой зависит от наличия пешки на a2. Возможным исходом этой игры является убирание с доски пешки a2, продолжение партии, или ничья с последующим распиванием пива.  Будем считать, что распивание пива будет при любом исходе, и самоцелью ни одного из участников не является. Ведь понятно, что никакую историю нам помнить не надо, кроме того, что стоит на доске?

              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                В данном случае история не нужна только потому, что не несет никакой дополнительной информации.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  А какую дополнительную информацию несет история в случае обсуждаемой игры?
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                    Если рассуждать чисто теоретически. Что если после того как Чебурашка 5 раз подряд назовет свою карту, мы поймем что он блефует, так как иначе он бы назвал карту на столе? Это даст нам информацию о имеющихся у него картах и нам уже не будет смысла называть их, поэтому вероятность угадать карту со стола будет уже не 1/(M+1), а 1/(количество неизвестных карт у Чебурашки + 1).
                    • 13 лет назад, # ^ |
                      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                      ===============================
                      Можно считать, что мы поняли, блефует Чебурашка или нет, сразу, как только мы сказали, верим ему или нет. Или Чебурашка упускает мгновенный выигрыш.


                      ---правка---

                      Значит, можно считать, что участник просто выкинул карту, если он блефовал. Она уже никогда не повлияет на нас.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        ===============================
                        Как это мгновенно? Вот Чебурашка назвал карту, а Гена сказал, что у него ее нет. Как отсюда можно сделать вывод, блефует ли Чебурашка, если следующий ход делает Гена и пока что он не располагает такой информацией?

                        Да и сказать, верим ли мы ему или нет мы-то можем, но вот Чебурашка может не поверить этому. В итоге они сделают так несколько итераций взаимного недоверия, а потом кто-то оценит шансы и предположит что противник 3 хода назад таки сказал правду, иначе это не была бы его оптимальная стратегия в предположении существования такой.

                        И я не говорю что решение из разбора однозначно неправильное или что-то вроде этого. Просто хотелось бы понять, почему мы не должны помнить историю и почему она не может влиять на наши последующие ходы.
                        • 13 лет назад, # ^ |
                            Проголосовать: нравится +5 Проголосовать: не нравится
                          =======================

                          Представим, что после каждого ответа "нет" мы играем в "верю - не верю".

                          Если мы верим противнику, мы мгновенно проверяем карту на столе. Этот случай не ведет к продолжению игры.

                          Если мы не верим противнику, и мы не угадали, то следующим ходом противник вскроет карту.

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

                        • 13 лет назад, # ^ |
                            Проголосовать: нравится +8 Проголосовать: не нравится
                          Возможно, разбор не очень подробно написан (писался ночью) - я попытаюсь это исправить. Но суть в том, что как только карта названа - она фактически выбывает из игры. Положим, что карта названа, и она есть у второго игрока - она выбыла. Если она названа, и ее нет - то второй принимает решение - верить или нет. Если он верит - игра заканчивается в любом случае. Если он не верит - то либо игра заканчивается следующим ходом все равно (если это была правда, и она в середина), либо, значит, соперник врал, и эта карта у него на руках, поэтому второй тоже мысленно "вычеркивает" ее. Таким образом, про карту не может быть "полузнания" - она либо в игре, и вы про нее ничего не знаете (про нее еще вообще не спрашивали), либо уже нет.
                          • 13 лет назад, # ^ |
                              Проголосовать: нравится 0 Проголосовать: не нравится
                            ===================================
                            А что если не существует оптимальной стратегии соперника, в которой он блефует 5 раз подряд? Тогда после четырех раз мы уже знаем что 5-й раз соперник сказал правду и смысла угадывать его карты дальше уже нет, поэтому мы назовем карту на столе и с каким-то шансом выиграем.
                            • 13 лет назад, # ^ |
                                Проголосовать: нравится 0 Проголосовать: не нравится
                              Поскольку стратегия вероятностная, не очень понятно, что значит "не существует стратегии, в которой он блефует 5 раз подряд". В некоторых играх такой ситуации не произойдет, в других - может произойти (при использовании одной и той же стратегии).. В этом и есть изюминка. Если же вы используете некие правила, которые ограничивают ваши стратегии - вы, скорее всего, как раз играете неоптимально, и увеличиваее шансы на победу для вашего соперника. 
                              • 13 лет назад, # ^ |
                                  Проголосовать: нравится 0 Проголосовать: не нравится
                                =====================
                                Задача ставится как? Есть игра, нужно посчитать с какой вероятностью выиграет первый игрок при оптимальной стратегии. Как ему ходить - это его дело. Например, возможна такая стратегия:

                                1. Если последние 4 раза противник блефовал, то пытаемся угадать карту на столе.
                                2. Если условие первого пункта не выполняется, то с вероятностью A верим, с вероятностью 1-A не верим.

                                Почему стратегия подобного вида не может быть оптимальной?
                                • 13 лет назад, # ^ |
                                    Проголосовать: нравится 0 Проголосовать: не нравится
                                  Потому что вы используете не смесь чистых стратегий, а одну из чистых стратегий, что в общем случае субоптимально. Тем самым, вы уменьшаете вероятность вашей победы по сравнению с достижимой с использованием оптимальной стратегии.
                                  • 13 лет назад, # ^ |
                                      Проголосовать: нравится 0 Проголосовать: не нравится
                                    =========================
                                    А кто сказал что задача эквивалентна вот такому пошаговому вычислению матричных игор 2х3? 

                                    В обычной матричной игре вообще нет понятия "история", поэтому для нее ваше утверждение верно. 

                                    Здесь же мы можем накапливать знания о предыдущих ходах соперника и, возможно, использовать их потом. Под использованием я не подразумеваю вычисление его карт, просто это может повлиять на нашу стратегию на каком-то ходу.

                                    Для того чтобы завершить доказательство правильности алгоритма из разбора, нужно доказать что состояние игры полностью задается числами N и M. Для этого нужно показать, что как бы ни играл соперник до этого, всегда существует такая стратегия, при которой мы будем действовать одинаково начиная с данного момента.
                                    • 13 лет назад, # ^ |
                                        Проголосовать: нравится 0 Проголосовать: не нравится
                                      Так мы выше вместе с anonymous'ом и пытались написать, почему так - если карта названа, она "выкидывается" из игры, знания о других картах никак не меняются.
                                      • 13 лет назад, # ^ |
                                          Проголосовать: нравится 0 Проголосовать: не нравится
                                        ===========================
                                        Так история игры - это не только знание о других картах. Почему, например, знание того что соперник блефовал 5 раз подряд нельзя считать дополнительным?

                                        Я же и пытаюсь сказать, что зная это мы можем изменить свою тактику. А говорить о чистых стратегиях здесь нельзя, так как изначальаня игра не является матричной, к ней ее еще нужно свести.

                                        Если взять сведение из условия, тогда в матрице не будет присутствовать информации о правдивости ходов соперника, а поэтому нельзя говорить что стратегия использующая эти данные является субоптимальной, так как игра перестает быть матричной в обычном ее понимании и теоремы, относящиеся к матричным играм к ней неприменимы. 

                                        Другое дело, если доказать что эту информацию можно и не использовать для достижения оптимальной стратегии. Вот тогда уже можно будет использовать теоремы о матричных играх.
                                      • 13 лет назад, # ^ |
                                          Проголосовать: нравится 0 Проголосовать: не нравится
                                        ====================================
                                        Основная проблема в том, что когда говорят об оптимальных стратегиях, подразумевают что игрок знает стратегию своего соперника. А в таком случае, он может предсказать что при любой стратегии соперника после четырех блефов будет идти только правда.
                                        • 13 лет назад, # ^ |
                                            Проголосовать: нравится 0 Проголосовать: не нравится
                                          Выше я уже пытался сказать, что любая игра с более сложными стратегиями может быть "механически" представлена как игра на этой матрице, но с использованием игроками (например, первым) других (более сложных) правил принятия решений. Но такие стратегии разбиваются просто оптимальной игрой на этой матрице.
                                          • 13 лет назад, # ^ |
                                              Проголосовать: нравится 0 Проголосовать: не нравится
                                            ====================================
                                            Выше - это в разборе? Если да, то как раз это я и пытаюсь оспорить/уточнить. 

                                            Цитата из разбора: "But instead of "when" the right question is "how frequently" since we have nothing else but usual constant-sum matrix game, and optimal strategy is the mixture of these three.". 
                                            Почему это правда? Ведь дальше все опирается именно на это утверждение.

                                            Почему на каждом шагу у нас новая матричная игра, которая никак не учитывает способ достижения предыдущих состояний?
                                            • 13 лет назад, # ^ |
                                              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                                              Вы согласны с тем, что когда первый игрок как-то (неважно как) делаете ход - это будет какой-то ход по правилам этой матричной игры?
                                              • 13 лет назад, # ^ |
                                                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                                                =========================================
                                                Нет, конечно. Когда мы говорим об "этой" матричной игре, мы подразумеваем что у нас есть только 3 стратегии. В матрице в таком случае записан наш "выигрыш" при условии, что мы выберем какую-то стратегию и соперник выберет какую-то стратегию.

                                                Но у нас то не 3 стратегии, потому что в зависимости от того, знаем мы что это блеф или нет, наш "выигрыш" изменится.

                                                Например, если мы знаем точно, что соперник не блефовал и назвал карту со стола, и мы ему сказали что у нас ее нет. Тогда мы знаем что соперник последний раз сказал правду и он уже знает карту, лежащую на столе. В таком случае, если мы сейчас сделаем "playing" или "bluffing", то соперник тут же выиграет, хотя в матрице это никак не отражено.
                                                • 13 лет назад, # ^ |
                                                    Проголосовать: нравится 0 Проголосовать: не нравится
                                                  Честно - мне уже надоел этот спор. Вы не читаете, что я пишу, и не пытаетесь меня понять. Я задал простой вопрос: согласны ли вы с тем, что когда первый игрок как-то делает ход - это будет какой-то ход по правилам этой матричной игры? Вы пишете длинное сочинение с ответом "нет". Ход в игре - выбрать одну из трех стратегий (неважно как, в смешанной стратегии  случайно, вы можете использовать любые шаманства вроде "истории") и сходить. Почему нет? Он что, выбирает какую-то четвертую альтернативуиву, которой в матрице нет?
                                                  • 13 лет назад, # ^ |
                                                      Проголосовать: нравится 0 Проголосовать: не нравится
                                                    ===========================
                                                    Что вообще из себя представляет матричная игра?

                                                    Есть 2 игрока, у первого n стратегий, у второго m. Если первый игрок выбирает стратегию с номером i, а второй - с номером j, то первый получает (соответственно, второй теряет) Aij денег/жизней/чего угодно.

                                                    Теперь ситуация из предыдущего сообщения, т.е. мы знаем что соперник знает карту, лежащую на столе. Если мы выберем стратегию playing, то что бы не выбрал соперник, наш выигрыш будет выражаться какой-то формулой, причем она не равна тождественно нулю. Но он, очевидно, равен 0, так как соперник тут же выиграет.

                                                    Вывод: если мы знаем что соперник знает карту со стола, наши шансы изменятся и матрица не будет соответствовать текущей ситуации. А значит, мы не делаем ход по правилам этой матричной игры, так как следуя им в качестве выигрыша мы бы получили число из матрицы.

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

                                                      По поводу того, что вы написали: ситуации, когда мы точно знаем, что соперник знает карту со стола, вообще быть не может, если наш соперник не дурак! (только после проигрыша). 
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                На шахматной игре никак не отразится, каким был первый ход в этой партии. На игру из задачи же это вполне может повлиять.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  ======================================

                  Просто любой параметр, который влияет, есть часть состояния игры. Если матричная игра будет зависеть от первого хода партии, надо будет его помнить.

                  В данном случае утверждается, что состояние этой игры - количество неизвестных карт.

      • 13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Ok, how do we use "history" of the game? To choose moves, or probabilities to make any possible move. Any decision you make based on history is some mixture of these pure strategies (but, probably, with different probabilities). And according to the v-N minimax theorem our opponent can assure himself with our "history-based" strategies at least value of the game - i.e., our super-puper-duper-history-based-strategy is not better than optimal strategy that we use now.
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          Existance of "history" changes game matrices (and therefore games themselves), so your argumentation doesn't work here.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            In which way? Can you give an example?
            • 13 лет назад, # ^ |
              Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

              A simple example:
              Suppose "history" allows you (I don't really know if it's possible in this particular game) to determine the other player's hand, then you can name the hidden card. And it's obvious that this game differs from the game without additional information.


              UPD: To proof that your approach is correct you need to show that there is no additional information can be derived from the previous turns.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится
                But how "history" allows you to determine the other player's hand? You can do this only asking him about cards.
                By this logic, the right answer to the problem is always "1 0" - if the first player knew the second's hand from the beginning...
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Ok, I've reread your original editorial, and now it seems to me that there is no additional information can be derived from "history", so your argumentation is correct :)
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For problem B (div2) you can simplify things by sorting

then the condition: "volume[1] == volume[N]" means: "volume[1]==volume[2]==volume[3]== ... volume[N]"

If that's true then all volumes are equal.
If it isn't true, try to normalize volume[1] with volume[N] and check volume[2] == volume[N-1]

Just pay attention at tests with small N
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
I think my solution for Div-2 B problem is slightly simplier and more understandable than author's one. I just calculated mean of all volumes and check if exactly two cups contain different volume. Here's my code: http://pastebin.com/YNxpK7DV.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
in problem C <div 2>,
after 6! factorial arrangement how i can figure out the 24 rotations for each lexicographical arrangement.

I am very weak at visualizing cubes symmetry.

can anyone help?
thanks in advance.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Suppose the faces on the cube are fixed.

    For each rotation, we can choose which face to be the "top" face. (6 choices)
    Once you choose the top face, the "bottom" face is fixed.
    Then, for the "side" faces, there are 4 possible arrangements - namely, rotating the cube along the axis passing through the center of the top face and that of the bottom face, by 0, 90, 180, or 270 degrees. (4 choices)

    So, these are the
        6 x 4 = 24
    rotations.

    (Each possible rotation is determined by identifying the top face, and how you perform the 2nd rotation.)
    • 13 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится
      (Each possible rotation is determined by identifying the top face, and how you perform the 2nd rotation.)

      what do you mean by that?
      can you please explain?

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Imagine a standard dice with faces numbered from 1 to 6, then take the dice  and rotate it in such a way until you have brought the number "1" to the top...


        You want to put "1" where (in the link above) there is a "6", ok?
        Well, now you have 4 rotations of the dice having "1" on the top, right?
        Each of these 4 rotations is a candidate.

        Now the algorithm: try to put 1,2,3,4,5,6 on the top, and for each choice make a copy of the dice and rotate this copy in the 4 ways described above.

        You have made 6*4 = 24 rotations
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      when I choose one face how can I determine the bottom face?

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Well, I think you're a bit confused about what are fixed and what are not fixed.

        The statement actually writes: two dices, A and B, are defined to be equivalent, if you can (3D-) rotate A in some way, such that A and B looks the same from any viewing angle. And it turns out that, there are 24 ways to rotate A. (see my previous comment)

        (*) Imagine now you have a particular dice, A, and now that its six faces are already printed with some fixed colors. You wish to know this dice A is equivalent to which of the remaining 6! - 1 dices. Actually, what you need to do is to rotate dice A using the aforementioned 24 ways, and check against the remaining 6! - 1 dices, to see if A and B matches.

        And you do this checking (*) for each of the 6! dice A.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что то не так с задачей B. При отправке по ней решения возникает отказ тестирования.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А у меня другой вопрос по задаче Е.
Как доказать, что ходить всегда выгодно? Возможность пропуска хода возникает после блефа у противоположного участника.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Доказать - не знаю как. Но численно эта стратегия всегда доминируется.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Т.е. тупая прогонка всех возможных случаев говорит, что так?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да. По крайней мере, в domain'е тестов (то есть при m<=1000, n<=1000)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          И то ладно.
          Еще не очень хорошо выглядит вопрос, что, когда второй игрок делает выбор в матричной игре, ему известна информация, изменяющая априорные вероятности случаев. Но здесь я пока сам не очень понял, проблема ли это, пытаюсь сам разобраться :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Нет. Ведь первый знал, что второму в случае чего станет известна эта информация - и он уже выбрал вероятность "блефовать", скорректированную на это знание =)
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Да, уже осознал, что либо мы подменяем априорные вероятности ("с места" игрока 2), либо корректируем матрицу игры ("с места" игрока 1). И то, и то суть одно и то же и не влияет на ответ.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
BigInteger в B div 1? 2^(10^18) ? никакой памяти не хватит
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Я только что сдал на BigInteger.

    UPD-PS И познал gcd кунг-фу.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Интересно.

      Это значит, что тестов с очень длинными числами нет в тестсете, или что их вообще нет? Если вообще нет, то почему?

      Upd: я всё понял, теперь просто ограничения до 10 000.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
вот с изменившегося ограничения и следовало начинать разбор, а также ответ Connector'а
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Про изменившиеся ограничения уже вставил.
    Что имеется в виду под ответом Connector'a? gcd кунг-фу? Мое решение gcd использует не особо (только в конце), но время работы - 340 мс, поэтому я не очень понимаю, где возникли сложности с "влезанием" в таймлимит.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      gcd кунг-фу заключается в том, что его надо использовать только в самом конце (а не где попало %) ) т.к. числа растут не быстро.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Hi!
i know why the algorithm for D(div1) which you are explain in editorial is correct , but i don't know why it's minimum?
please give me some idea to prove it!
thanks for your nice contest!
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Вопрос по задаче: B (div. 1) / D (div. 2) : абсолютно не понятно в каком направлении копать, даже при наличии разбора задачи.
Может кто-нибудь объяснить откуда берётся 8/3 в приведённом примере?
Есть ли какая-то литература, статьи, которые близки к этой теме?
Спасибо.
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The answer for the DIV2 C question is the same as number of stereoisomers , of different types

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

deleted