AlexFetisov's blog

By AlexFetisov, history, 19 months ago, In English,

Problem A (div2):

It is obvious that we need to make sequence of moves like: 1, 2, 1, 2, ...

So the answer is 2 * n / 3. After that we have either 0, 1 or 2 stones left. If we have 0, we are done, otherwise we have 1 or 2 left, so we only can give 1 more stone.

Final formula is: (2 * n) / 3 + (n % 3 != 0 ? 1 : 0);

Problem B (div2):

We can just emulate grasshopper behavior and save all positions it visits. It is obvious that we will have no more than O(n) different positions. If grasshopper appears in the same position twice that means that there is a loop and the answer is INFINITE. Otherwise the answer is FINITE.

Problem A(div1)/C(div2):

Let's have 2 matrices: a, idx. In a we will have NULL for cell if we don't know the value or the value. idx will be initialized with idx[i][j] = {i, j}; Then we need to emulate the process on matrix idx. If we have 3rd query we can set up the value in matrix a, because we know the original position of that cell keeping idx.

Problem B(div1)/D(div2):

The key in this problem is that order of all elements in odd positions and in even positions is the same. Let's say we have 2 arrays: [1, 3, 5, ...] and [2, 4, ...] (odd positions and even positions). Now if we call 2nd commands we just swap these 2 arrays, but order is the same. Obviously 1st command also keeps the order. By order I mean cyclic order (right neighbor is the same in cycle position).

Let's just keep the position of 1st boy and 2nd boy. Now if we apply 1st operation we move it by X or -X. Second type of the query just swaps the positions. In the end we can construct the answer if we know positions of 1st and 2nd boys.

Problem C(div1):

First, let's solve inverse problem: find minimum (maximum) of two distributions. Let's use the following formulas:

P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)

For minimum:

P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))

Now in our original problem minimum and maximum defines system of square equations for each pair P(a <= k), P(b <= k).

Solving these equations we get P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2, where u = P(max(a,b) <= k), v = P(min(a,b) <= k). Now we can notice that if there exists an answer, then there exists an answer when we chose the signs for each pair equally (check out this comment)

Problem D(div1)/E(div2):

There are many ways to solve this problem. One of the ways was SQRT-decomposition. First let's compress all times. Now for each block in the decomposition we will store for each element the balance in that block. So to answer the query we need to calculate sum of balances from first block to the block before the one where our element is located and then just process all requests in the current block.

Another way was to use data structure from std library, described here. For each element we have two trees: remove times and add times. Then by getting order of the time in remove and add tree we can calculate the answer.

Problem E(div1):

Let's build for both 2-SAT formulas implication graph and let's find strong connected components in this graph. If both of the formulas are not satisfiable then the answer is SIMILAR. If only one formula is not satisfiable then we can find an answer for the second one and output it.

Now, let's assume both formulas are satisfiable. Let's have a transitive closure for both of the graphs. Let's call the variable X fixed in the formula F if there is a path -> x or (x -> ). If there is a fixed variable in one formula, but not fixed in the other (or fixed but has other value) we can find the solution for that second formula with opposite value of that fixed variable — that will be an answer. If we could not find these variables, we can remove all of them. There is no fixed variables in the rest of them. Let's find an edge u->v, presented in one graph, but not presented in the other. Let's find the solution for formula without the edge with u = 1 and v = 0 (we always can find it). That is the answer.

Problem F(div1):

Let's define k-clique B the descendant of k-clique A, if B could be produced from A with the sequence of the following steps: add vertex to the clique, connected with all clique vertices in the graph description and remove exactly one other vertex. Let's calculate the DP with states (k-clique, separation its vertices to the components) — number of spanning forests int the graph, induced by the clique and all its descendants so that clique will be divided to different connected components according to the defined vertices separation (all of the rest vertices will be connected with some of these components). To calculate that we need to precalculate all separations from k to k+1 elements and transitions:

1) (separation of k+1 vertices) x (separation k+1 vertices) -> (separation k+1 vertices | null), transform pair of separations — forests to the set of connected components of their union or null if there appears a cycle.

2) (separation of k+1 vertices) x (vertex) -> (separation of k+1 vertices | null), transform forest to the new forest, generated by adding new edge from vertex to vertex k+1 (or null, if there appears a cycle)

3) (separation of k+1 vertices) -> (separation of k vertices | null), projecting the separation on the first k vertices (or null, if k+1-th vertex creates a separate component)

Check out details in the author solution.

Read more »

Tutorial of VK Cup 2016 - Round 2
 
 
 
 
  • Vote: I like it  
  • +37
  • Vote: I do not like it  

By AlexFetisov, history, 19 months ago, translation, In English,

In 6 hours 2nd Round of the VK Cup 2016 programming competition is going to happen! If you haven't registered for the round — don't worry! There is an extra registration!

The teams who has advanced from VK Cup 2016 Round 1 and VK Cup 2016 Wildcard Round 1 can participate in this round. The competition has regular Codeforces rules. Also in the same time with official round there is a regular rated Codeforces round played on the same problem set for participants from both div1/div2 divisions.

This round was prepared by AlexFetisov and winger. That is the first round which we have prepared as authors. We want to thank Gleb Evstropov (GlebsHP) for his help. Gleb is doing great job as Codeforces coordinator and I wanted to tell that one more time! Also we want to thank Kamil Debowski (Errichto), Mateusz Radecki (Stonefeang), Boris Minaev (qwerty787788), Pavel Kunyavskiy (PavelKunyavskiy) for their help in testing the problems and for great suggestions. Huge shout out for Mike Mirzayanov (MikeMirzayanov) for everything he has done for all of us!

To advance to Round 3 team should have a positive score and has score not less than the score of the 100th team in the final scoreboard. Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well.

Good luck and have fun!

Update

Round has been finished. There were some problems during round but we hope that you enjoyed problems. Congratulations to the winners!

Official VK Round 2:

  1. Who`s On First Base!: -XraY-, ershov.stanislav
  2. Beer and lemon tea: sankear, Zlobober
  3. MYCOPOBO3: overtroll, LHiC
  4. Never Lucky: subscriber, tourist
  5. 33% less bad jokes: ifsmirnov, Arterm

Div1 results: Congratulations to anta who is the winner of this round div1 solving the hardest problem of the contest.

  1. anta
  2. TooDifficuIt
  3. Petr
  4. dotorya
  5. ikatanic

Div2 results:

Congratulations to alexrcoleman who is the winner of this round div2 solving all problems less than in an hour!

  1. alexrcoleman
  2. nherceg
  3. santjuan
  4. mkisic
  5. unused

Editorial http://codeforces.com/blog/entry/44538

Read more »

Announcement of VK Cup 2016 - Round 2
 
 
 
 
  • Vote: I like it  
  • +104
  • Vote: I do not like it  

By AlexFetisov, 7 years ago, In Russian,
Добрый день) Решая ГП Европы, придумал задачу В (там где надо сориентировать ребра так, чтобы граф стал Эйлеровым), но написать уже не успевал) Потом прочитал на СФ разбор Ильи Корнакова и тихо порадовался, что знаю как решать такие задачи. Однако на пути из Питера решил написать ее в поезде и получил ВА 5. Искал баг и ничего не нашел, так и не знаю, где косяк. Вот и подумал, может кто подскажет. По шагам то, что я делаю.
1) Ищу минимальный возможный вес ребра и максимально возможный, где минимальный - это максимум из минимумов весов по каждому ребру, а максимальный - максимум всех весов.
2) Бин поиском подбираю вес
3) Строю граф по ребрам у которых вес >= текущему
4) Проверяю граф на достижимость из вершины 0.
5) Для каждой вершины читаю ее полустепень входа и выхода, потом беру минимум из этих двух величин и вычитаю из каждой этот минимум (то есть свожу одну из них в ноль)
6) Добавляю ребра из истока в каждую вершину с положительной полустепенью входа с пропускной способностью, равной этой степени, и в сток добавляю ребра из вершин с положительной полустепенью выхода, с пропускной способностью, равной этой степени.Остальные ребра добавляю в сеть такие как есть с пропускной способностью 1
7) Нахожу макс поток
8) Перебираю ребра в сети, которые не ведут из истока и в сток. Если поток по ребру положительный, то ориентирую это ребро в сторону потока.
9) Строю граф на неориентированных ребрах
10) Проверяю степень каждой вершины этого графа на четность
11) Нахожу для каждой компоненты связности Эйлеров цикл и ориентирую ребра вдоль него.
12) Строю исходный граф с найденной ориентацией ребер и нахожу Эйлеров цикл.
Может где то в логике косяк? В коде не нахожу.

Read more »

 
 
 
 
  • Vote: I like it  
  • -10
  • Vote: I do not like it