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

Автор AndrewLazarev, 14 лет назад, перевод, По-русски

Задача A. Победитель


Для решения данной задачи нужно лишь аккуратно промоделировать действия из условия, а именно:

  1.  Прежде всего нам необходимо найти максимальное количество очков m на момент окончания игры. Это можно сделать эмулированием игры. Когда сыгран последний кон, мы можем перебрать всех игроков и найти максимальное количество очков.
  2. Далее, мы должны определить множество игроков, которые имеют максимальный балл в конце игры. Это делается в точности таким же способом, как и определение максимального количества баллов. Перебираем всех игроков в конце игры и сохраняем тех, у кого количество очков равно m.
  3. И наконец, нам нужно найти победителя. Для этого мы эмулируем игру еще раз и как только у игрока из списка победителей стало не менее m очков - мы нашли победителя!

Эта задача показывает, что иногда проще последовательно закодировать все написанное в условии, чем думать и оптимизировать.

Задача B. Наименее круглый путь


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

Итак, мы можем считать, что в матрице нет ни одного нуля. Давайте поймем, из чего получаются концевые нули в результирующем произведении. Если мы пойдем вдоль пути и будем считать количество множителей 2 и 5 в числах по пути, то количество концевых нулей будет min(количество 2, количество 5). Это позволяет нам решать задачу для 2 и 5 независимо. Итоговый ответ будет равен минимуму из независимых решений.

Теперь остался последний штрих - решить задачу для 2 и для 5. Новая интерпретация задачи выглядит следующим образом. Есть квадратная матрица с числами. Нам необходимо найти путь с минимальной суммой по ходу пути. Это классическая задача динамического программирования. Пусть A[r,c] - число в ячейке (r,c), а D[r.c] - ответ для данной ячейки. Тогда
 
D[r,c] = min(D[r-1,c],D[r,c-1]) + A[r][c]

Задача C. Задача комментатора


Возьмем два стадиона и найдем множество точек, из которых стадионы видны под одинаковым углом. Не слишком сложные математические вычисления показывают, что это множество - прямая линия в случае, если стадионы имеют одинаковый радиус и это множество - окружность, если радиусы у стадионов различны. Пусть S(i,j) - множество точек, из которых стадионы i и j видны под одним углом. Т.к. по условию центры стадионов не находятся на одной прямой, то пересечение S(1,2) и S(1,3) сдержит не более, чем две точки. Если мы знаем эти две точки, то можем проверить, что они удовлетворяют условию и выбрать из них с максимальным углом обзора.
Разбор задач Codeforces Beta Round 2
  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему решение задачи B на Питоне не проходило (походу из-за памяти), а на Java без особых исправлений прошло? Питон очень много памяти выделяет для массивов?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а можно вообще построчно сканировать, памяти будет O(N) а не O(N·M)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    правда с восстановлением пути будет проблема,  ведь для этого надо около N·M булевых переменных, но как-нибудь ужмём :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А- Победитель. Мы  учитываем, что у этого первого из числа победителей, на следующий кон выпадет отрицательный баланс, а потом он когда то доберет очки до маскимального, но при этом пока у него будет меньше очков его кто-то обойдёт - он остаёться победителем?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Неплохо бы написать как находить эти окружности/прямые линии в задаче C.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    +1.
    если напишет, то тогда мне бесполезно будет переводить мой разбор.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А подскажите алгоритм вычисления точек пересечения окружностей. Мне удалось сочинить такой метод: записываем два уравнения окружностей в систему, далее из одного вычитаем другое и получаем ур-е прямой, проходящей через искомые точки пересечения. Представляем прямую в каноническом виде {x=x0+dx*t; y=y0+dy*t}, подставляем это в уравнение любой из окружностей, образуется квадратное ур-е относительно t. Решаем его.

Есть ли более простой или точный способ?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have alternative solution for C. I did it with hill climbing.
I made the observation that if I have the radii of the three circles r1, r2, and r3 and the distances from the commentator's point of view d1, d2, d3 then di / dj = ri / rj. Then I did hill climbing trying to minimize the maximum of the three such ratios.
One last note - I found out that if my initial step was too huge then I got thrown into the infinity so I chose a relatively small step - 10.0 but allowed for multiple using of this step in the same direction without having it reduced.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can somebody help me?
I have WA 2 in problem C
Please, give me some test :) thanks
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Consider this testcase for problem A: 6 a 3 b 3 c 3 c -1 b -1 a -1 What is the result? "a" or "c"? Thanks

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

Anyone solve 2B in python? I always got "Time limit exceeded " in test 17 or 18。 11495193

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

can anyone please tell me why im getting TLE in testcase 31 Problem B.i am stuggling from so long.it would be so helpful.i cant figure it out. 27893278

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

    Because one of the number may be 0 in that test case so take care of that while finding the number of 2's and 5's as factors for that number

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

For PROBLEM 2B

The path that would give min for 2s wont necessarily give min for 5s, right ? Then why should we solve the problem for 2s and 5s independently ? Wont they be interlinked based on the min no of ending zero till the point we are calculating for ?

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

    I have the same doubt, did you find an explanation for it?

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

      You don't want to find a path that minimizes both 2s and 5s, but you are looking for a path that minimizes the number of 10s. This path could be either the one with minimum 2s or minimum 5s (whichever is smaller).

      Proof: Suppose the path that minimizes the number of 10s does not minimize either the 2s or the 5s. Then there exists a path with fewer 2s or 5s. But this path would also have fewer 10s (since 10=5*2). Which is a contradiction.

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

About question C, in fact the intersection of $$$S(1,2)$$$ and $$$S(1,3)$$$ will all satisfy the criteria, we only need to check for the maximum :

The set of points that observe 2 stadiums equal angle is an Apollonius circle (a line is treat as a circle with radius $$$\infty$$$). Let's call $$$I_1, I_2, I_3$$$ and $$$X_1, X_2, X_3$$$ the internal and external similitude centers of 3 pair of circles, then the circle with diameter $$$I_iX_i$$$ is the said Apollonius circle

By direct apllication of Menelaus theorem $$$X_1, X_2, X_3$$$ are collinear

According to Gauss-Bodenmiller theorem, these 3 circles are coaxial, which mean if any 2 of these circles have some common points, they all pass through such points

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I didnt participate in contest. Personal reasons. I have seen only question D and G this morning. D Pretty straightforward. Just simulate the process smartly with level gap and value gap. G was more implementation type I think. I will solve that one maybe.

    Btw how was questions ? was C good ? I will go check C.