KhaustovPavel's blog

By KhaustovPavel, 4 years ago, In Russian,

478A - Initial Bet

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

478B - Random Teams

Если переформулировать задачу в терминах теории графов, то ее можно сформулировать следующим образом: Имеется граф, состоящий из n вершин и m компонент связности. Внутри каждой компоненты связности каждая пара вершин этой компоненты связана ребром. Другими словами, каждая компонента связности является полносвязной. Какое наименьшее и какое наибольшее количество ребер может содержать такой граф? Рассмотрим процесс построения графа из n вершин и m компонент связности. Для начала предположим, что каждая из m компонент содержит ровно одну вершину. Остается распределить оставшиеся n - m вершин так, чтобы минимизировать или максимизировать количество ребер. Заметим, что при добавлении новой вершины в компоненту связности размера k, количество ребер увеличивается на k (новая вершина соединяется с каждой из уже существующих одним ребром). Следовательно, для того, чтобы минимизировать количество образованных ребер на каждом шаге, требуется каждый раз добавлять вершину в компоненту связности наименьшего размера. Если действовать согласно такой стратегии, то после распределения вершин по компонентам связности появится компонент размера и компонент размера . Аналогично, для того, чтобы максимизировать количество ребер, на каждом шаге необходимо добавлять очередную вершину в компонентну связности наибольшего размера. Если действовать согласно такой стратегии, то образуется одна компонента связности размера n - m + 1, оставшиеся компоненты связности будут состоять из одной вершины. Зная количество компонент связности и их размеры, можно посчитать общее количество ребер. Для полносвязной компоненты, состоящей из k вершин, количество ребер равняется . Следует помнить про необходимость использовать 64-битный тип данных для хранения количества ребер, которое квадратично зависит от значения n.

478C - Table Decorations

Рассмотрим ситуацию, когда величина max(r, g, b) - min(r, g, b) ≤ 1, в таком случае, очевидно, ответ равен . Мы всегда можем украсить столько столов тремя воздушными шарами разных цветов. Очевидно, что оставшееся количество шаров будет меньше трех и, следовательно, не может быть использовано для украшения стола в любом случае. Все оставшиеся случаи имеет смысл свести к ранее рассмотренному. Если есть один цвет такой, что количество шариков этого цвета больше, чем суммарное количество шариков для оставшихся двух цветов, то всега выгодно украшать стол двумя шарами этого цвета и одним шаром того из оставшихся цветов, которого больше на данный момент. Далее можно разными способами группировать операции и выполнять более одной операции за раз. Другим решением можно назвать тот факт, что ответ будет отличен от , но только тогда, когда max(r, g, b) ≥ 2·(r + g + b - max(r, g, b)), в таком случае ответ r + g + b - max(r, g, b). В этом случае шарики двух наиболее редких цветов закончатся раньше, чем шарики одного наиболее популярного, если украшать каждый стол с использованием двух шариков наиболее популярного цвета.

478D - Red-Green Towers

Для начала можно заметить, что для того, чтобы построить красно-зеленую башню высоты h потребуется кубиков. Следовательно, высота полученной башни для заданных ограничений никогда не превысит 893. Эту высоту можно определить заранее, если предположить, что все кубики одного цвета. Попробуйте доказать это самостоятельно. Далее можно решить задачу с использованием динамического программирования. Пусть F(t, r) — количество способов собрать башню наибольшей высоты, если собрано t верхних этажей и остались незадействованными r красных кубиков. Среди аргументов функции нет количества оставшихся зеленых кубиков g — его можно однозначно определить из значений t и r: , где r0 и g0 — изначальное количество красных и зеленых кубиков, соответственно. Ну а дальше следует рассмотреть лишь два перехода: пострить t + 1-ый уровень из красных или из зеленых кубиков: F(t, r) = F(t + 1, r - t) + F(t + 1, r). Очевидно, кешировать данные в массиве размера 893 × 2·105 — не лучшая затея. В таком случае можно подсчитывать значения функции для всех значений t от 0 до h, храня в памяти только значения для текущего значения t и для предыдущего, от которого оно будет зависеть.

478E - Wavy numbers

Для решения этой задачи необходимо было заметить, что волнистых чисел на интервале от 0 до 107 намного меньше, чем 107. В таком случае можно решить задачу с использованием подхода meet-in-the-middle. То есть отдельно решить эту задачу для первых семи цифр ответа, и для последних семи цифр ответа. Для этого потребуется отдельно сгенерировать все волнистые числа на интервале от 0 до 107, которые начинаются с возрастания двух соседних цифр, и аналогичные волнистые числа, которые начинаются с убывания двух соседних цифр. Дальше для каждой первой половины мы можем посчитать rl — ее остаток от деления на n и, затем, определить количество подходящих вторых половин, которые должны иметь остаток от деления равный .

Для задачи было установлено ограничение времени равное 1.5 сек. На самом деле, если написать решение с подходом meet-in-the-middle достаточно оптимально, то решению потребуется гораздо меньше времени. Приведенная авторская реализация (8271836) умеет решать аналогичную задачу для 1 ≤ n, k ≤ 1016 примерно за 2.5 сек.

 
 
 
 
  • Vote: I like it  
  • +45
  • Vote: I do not like it  

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where find English version

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +20 Vote: I do not like it

    Note: English version of the above editorial.

    478A — Starting bid

    To solve the problem, it is important to note that during the game, the number of coins on the table can not be changed. The total number of coins on the table after a successful bid, remains unchanged. Therefore, by dividing the total number of coins on the table by the number of players, can obtain an initial rate for each. If you divide without remainder impossible, such a result can not play. Should pay attention to the fact that the initial rate of each of the players must be different from zero, hence, zero can never be the answer.

    478B — Random team

    If you restate the problem in terms of graph theory, it can be formulated as follows: There is a graph consisting of n vertices and m connected components. Inside each connected component, each pair of vertices connected by an edge of the component. In other words, each connected component is a full mesh. What is the smallest and the largest number of edges which may contain such a graph? Consider the process of constructing a graph of n vertices and m connected components. To begin, assume that each of the m component contains a single peak. It remains to distribute the remaining n — m vertices so as to minimize or maximize the number of edges. Note that when adding a new vertex in the connected component of size k, the number of edges is increased by k (new vertex is connected to each of the existing one edge). Consequently, in order to minimize the number of ribs formed on each step required each time to enhance top component connected smallest size. If you act according to this strategy, after the distribution of vertices on the connected components appears component size and component size. Similarly, in order to maximize the number of edges in each step must be added to the next vertex in the component connectivity greatest dimension. If you act according to such a strategy, then a single connected component of size n — m + 1, the remaining connected components will consist of a single vertex. Knowing the number of connected components and their sizes, you can count the total number of edges. For a full mesh components consisting of k vertices, the number of edges equals. It should be remembered about the need to use a 64-bit data type to store the number of edges, which depends quadratically on the value of n.

    478C — table decoration

    Consider a situation where the value max (r, g, b) — min (r, g, b) ≤ 1, then obviously the answer is (r+g+b)/3. We can always decorate so many tables three balloons of different colors. Obviously, the remaining amount will be less than three balls, and hence can not be used to decorate the table anyway. All the remaining cases it makes sense to reduce to the previously discussed. If there is one color, such that the number of balls that color is greater than the total number of balls for the other two colors, it is advantageous to decorate a table with two balls of one color and the ball of the remaining colors, which is greater than presently. Further it is possible in many ways to group operations and to carry out more than one operation at a time. Another solution include the fact that the response is different from (r+g+b)/3, but only if max (r, g, b) ≥ 2 · (r + g + b — max (r, g, b)), in which case the response r + g + b — max (r, g, b). In this case, the balls of the two most rare flowers will end earlier than the balls of one the most popular, if you decorate each table with two balls of the most popular colors.

    478D — Red and green towers

    To begin, you will notice that in order to build a red-green tower height h requires h(h+1)/2 cubes. Therefore, the height of the resulting tower predetermined limits never exceeds 893. This height can be determined in advance, if it is assumed that all blocks of the same color. Try to prove it yourself. Further it is possible to solve the problem using dynamic programming. Let F (t, r) — the number of ways to gather the greatest height of the tower, if collected t upper floors remained untapped r red cubes. Among the arguments of the function are no amounts remain green cubes g — can be uniquely determined from the values ​​of t and r: g = g0 — (t(t+1)/2 — (r0-r)), where r0 and g0 — the initial number of red and green cubes, respectively. Well and further consideration should be given only two transitions: Build t + 1-th level of the red or green blocks: F (t, r) = F (t + 1, r — t) + F (t + 1, r). Obviously, the cache data in an array size of 893 × 2 × 105 — not the best idea. In such a case, you can count the value of the function for all values ​​of t from 0 to h, stored in memory, only the values ​​for the current value of t and the previous one, from which it will depend.

    478E — Wavy number

    To solve this problem, it was necessary to note that the numbers on the undulating range of from 0 to 107 is much smaller than 107. In this case, the problem can be solved using an approach meet-in-the-middle. That is separate to solve this problem for the first seven digits of the answer, and for the last seven digits of the answer. This will require the wavy separately generate all numbers in a range from 0 to 107, starting with the increase of two adjacent numbers and similar wavy numbers which begin with the decrease of two adjacent numbers. Then for each of the first half, we can calculate rl — its residue modulo n and then determine the appropriate amount of the second half, which should be equal to the remainder of the division rr = (n-rl)mod n.

    For the problem was a limitation of time equal to 1.5 seconds. In fact, if we write the solution to the approach meet-in-the-middle optimally enough, then the solution will take much less time. The above author's implementation (8271836) can solve a similar problem for 1 ≤ n, k ≤ 1016 for about 2.5 seconds. Courtesy: Google Translate

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding 478C - Table Decorations 'Table decoration': What if r = 200, g = 201, b = 298?

min{r+g, r+g+b/3} = 233.

But I am not seeing how to get 233 tables. I can only decorate 201 tables at max.

Please help.