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

Автор ikar, 11 лет назад, По-русски

A: 379A - Новогодние свечки

Пусть cura количество целых свеч, curb — количество прогоревших. Изначально cura = a, curb = 0, тогда после того как прогорят все cura свечек, к ответу прибавится cura , а curb +  = cura, переделаем прогоревшие свечки в целые cura = curb / b , будем повторять это пока мы можем сделать хотя бы одну целую свечу. #### B: 379B - Новогодний подарок Если в кошелек необходимо положить более одной монетки, то между операциями "положить монетку" можно передвинуться к соседнему кошельку, затем обратно. Так как почти на каждую операцию "положить монетку" мы будем тратить не более 2 дополнительных операции, легко проверить, что количество инструкций на максимальный тест не будет превышать 300 * 300 * 3 = 270000, что меньше 106.

C: 379C - Новогоднее изменение рейтинга

Можно отсортировать рейтинги в порядке неубывания, затем итерируясь по ним можно поддерживать текущий минимальный рейтинг cur, который не был ни кому отдан. Тогда если ai > cur, i-му пользователю достанется ai рейтинга и cur = ai + 1, если ai ≤ cur то i-му пользователю достанется cur рейтинга и cur увеличится на единицу.

D: 379D - Новогоднее письмо

При честном моделировании, получения итоговой строки, мы столкнемся с проблемой того, что она достаточно велика. Заметим что для каждой итерации нам достаточно хранить количество подстрок AC в текущей строке, а также первую и последнюю буквы. Таким образом мы научимся быстро моделировать алгоритм для произвольных начальных строк. Единственное что нам осталось перебрать начальные строки, для этого воспользуемся алфавитом из трех букв A, C и любой другой на ваш вкус. Переберем первую и последнюю буквы строки, а также количество подстрок AC, которые у нас могу получится с такими начальной и последней буквой. Перебрав таким образом s1 и s2 мы сможем посчитать количество подстрок AC в sk.

E: 379E - Новогодние елочные украшения

Будем поддерживать объединение всех кусков до i-го, обозначим за S(i) площадь объединения первых i кусков. Тогда для того что бы узнать видимую площадь i-го куска нужно вычислить S(i) - S(i - 1), (S(0) = 0). Для простоты рассмотрим все отрезки с началом в x = 0 и концом в x = 1. Объединение будет представлять из себя выпуклую вниз ломанную, её можно представить как последовательность точек, каждая из которых соединена с соседней. Текущее объединение будет обновляться трапециями(часть куска). Понятно, что нам нужен будет только верхний отрезок, если он войдет в новое объединение тогда он должен будет пересечь два отрезка из объединения. Это пересечение мы можем найти за количество вершин в объединении, также каждый новый отрезок может добавить в объединение не более одной вершины. Если отрезок войдет в новое объединение то точки из объеденения, находящиеся под этим отрезком должны быть удалены. Таким образом количество вершин в объединении будет сравнимо с количеством кусков. Посчитав такие объединения для каждого сегмента, мы сможем получить ответ на задачу.

F: 379F - Новогоднее дерево

Скоро будет.

G: 379G - Новогодний кактус

На дереве эту задачу можно решать при помощи динамического программирования d[v][c][a], где v — номер вершины, c — тип этой вершины(чья игрушка висит или там не висит игрушек вовсе), a — количество игрушек в поддереве вершины v которые повесил Джек, само значение d[v][c][a] будет равно максимальному количеству игрушек, которые может повесить Джилл, при заданных условиях. Такую динамику можно считать перебирая сыновей вершины v и их тип и количество игрушек повешенных Джеком. Но у нас не дерево, а кактус, для того, что бы научиться решать эту задачу достаточно сжать циклы в кактусе в вершины тем самым получив обычное дерево, представив каждую вершину как последовательность вершин в цикле кактуса, из которых есть "продолжение" кактуса, и промежуточных вершин. Единственное что осталось, реализовать динамическое программирование на дереве, аккуратно обрабатывая каждую вершину.

Разбор задач Good Bye 2013
  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

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

problem A act optimally how to prove the algorithm acting optimmally ?

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

    not really related to your question but actually a "brute-force" implementation can also AC 5571273 :)

    edit : it's clearly optimal since make new candle when ever we can, it have the same idea with the tutorial but this may be easier to understand :p

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

      maybe it's not a good question seems trivial I think maybe the candle which is run out and then make a new one have different choice of run out candle and run out ones may have different levels and maybe not using them all in the same time or in different order maybe different. your answer is implement not brute force or exhaustion.I may have consider all the situation .I`d like an elegant simple approach to the proof.

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

This Tutorial is too simple that I can't understand how to solve D after I read it : (

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

    Look for example you need to calc s5 for strings s1 = CACACC and s2 = CACAA, represent s1 like 2 AC substring and first and last letter — CC,
    s2 = (1, CA)
    s3 = (3, CA) (AC + CC has no AC at the junction and we just take first and last letter)
    s4 = (4 + 1, CA) (+1 because of at the junction substring AC appears)
    s5 = (8 + 1, CA) (again).

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

This tutorial' english gave me cancer XD

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

Any better explanation for problem E ?

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

Any better explanation for problem E ?

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

    You can separate the problem into K parts, because each part is independent of the others. To solve for just one part, you can keep the segments (points) that builds it, at first there is only one segment, from (xk,0) to (xk+1,0) and the area is currently 0. For each new segment (each new decoration) we must build the parts again. To add a new segment Bk, you need to check for every segment Ak that builds the part with the new segment Bk:

    • Segment A and B intersect: add the segments (A.x1, max(A.y1, B.y1)) to (intersect_x, intersect_y) and from (intersect_x, intersect_y) to (A.x2, max(A.y2, B.y2))
    • Segment A and B don't intersect: add the segment (A.x1, max(A.y1, B.y1)) to (A.x2, max(A.y2, B.y2))

    (The y coordinate for the B segment means the y for the current x). After building the parts again you have the old ones and the new ones. The amount of area that they add to the answer of this decoration is the new area minus the old area. The overall idea is not hard, it is just can be tricky to implement, specially for those who don't have much geometry skills :) (like me). You can check my code here: 5594115

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

i thought that struct is faster than pair,but it seems not, i changed it to pair and got ac the C problem

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

    What slowed you down wasn't struct, but the comparison function. See 5602813. I modified your comparison function and got AC, passing the arguments by reference and adding a "return false" at the end. Not sure why the latter is required but without it I got a WA in test #10.

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

      hi! thank you soo much for your explanation! its very clear and now i know where my code is wrong! it seems that it cant handle the sort when the 2 values is same, and adding "return false" seems to fix it all! thank you very much once again!

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

    pair<int,int> is basically the same as struct {int first, int second}; with some predefined comparison operators and constructors.

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

Problem G how to write O(N^2) dynamic solution for tree. O(N^3) is simple, but O(N^2) is not so obvious. Answer in Russian is also acceptable.

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

Как автору в голову пришла идея задачи F?

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

Все задачи понравились. Особенно задача D. Автор молодец!

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

Can somebody, please, post at least a sketch of the actual solution on F? Thanks, Happy new year!

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

How to solve F?

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

How can I solve the problem F? Who can give me some idea? Thanks!

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

    This is a problem about LCA?

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

      Indeed, this is a problem about LCA. Let end_first and end_second be the endpoints of the diameter of the tree. When inserting an new node u we first have to compute the 2^j-th ancestor of u, for all j in range 0..log2(N). After that, notice that a possibly new diameter may start from j and end at end_first, or start at j and end end_second. So, you just compare the distances to get the new diameter, and you update properly end_first and end_second. I also have some code I wrote after the contest: http://codeforces.me/contest/379/submission/5603366. I hope this helps :)

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

coming soon after X years?

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

How to solve the problem F with Centroid Decomposition

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

Задачу A можно ещё решить с помощью формулы:

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

Задачу A можно ещё решить с помощью формулы:

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

How to solve question B?

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

How to solve question F?