AlexFetisov's blog

By AlexFetisov, history, 2 years 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.

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

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

In first problem the formula is (2 * n) / 3 + (n % 3 != 0 ? 1 : 0)

»
2 years ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

Also in problem E we can create map <int, SegmentTree>, where segment tree is sparse (indexes as time and values as{-1, 0, 1}). If we have query "add/delete value x in time t", we just update tree x in position t by value 1/-1. And "count query x in time t" will be sum of tree x in segment [1,t]. Code.

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

Auto comment: topic has been updated by AlexFetisov (previous revision, new revision, compare).

»
2 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Problem E can easily be done with a Fenwick Tree with a map stored in each node, after compressing the values of time.

Code

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    It's not necessary to compress values of time. Check this solution.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      But that solution's complexity is O(nlog2n), instead O(nlogn) for the solution with compression.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        i think that the code provided by zscoder is O(n log^2(n)) how it can be reduced to O(n log(n))?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can compress the time values to a more feasible rank (let's say [0..n]), and do the same for the rank of numbers added or removed from each time value. Then you can create the Fenwick Trees as arrays, doing queries in log(n) like an usual Fenwick Tree query.

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

Very sad that we needed to consider discriminant to be less than epsilon(1e-9).It is first time that I met such trick with precision double problem. When I change double to long double it gives unexpected behavior.

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

"Now we can notice that if there exists an answer, then there exists an answer when we chose the signs for each pair equally" Can you explain this in detail? The comment in the link is in Russian...

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

    I think the reason is the following:

    You have computed two values for each k:

    big[k]=(u + v + sqrt((u + v)^2 — 4u))) / 2

    small[k]=(u + v — sqrt((u + v)^2 — 4u))) / 2

    It is clear that big[k]>=small[k].

    For each k you know for sure that either P(a<=k)=big[k] and P(b<=k)=small[k], or P(a<=k)=small[k] and P(b<=k)=big[k]. In fact, it follows that big[k]=max(P(a<=k),P(b<=k)) and small[k]=min(P(a<=k),P(b<=k)). You have to make the election for all k so that P(a<=k-1)<=P(a<=k) and P(b<=k-1)<=P(b<=k). Some correct election for all k exists because the statement says that there exists a correct probability. It follows that big[k-1]<=big[k] and small[k-1]<=small[k]. Thus, by choosing P(a<=k)=big[k] and P(b<=k)=small[k] for all k we are done.

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Are you going to post the editorial for the last problem?

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

what that swapping means in div2 D? and how it relates,,, posof_1^=1 and posof_2^=2?

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

Problem B (div2): can't a position repeat without having a loop? if the grasshopper jumps in a pattern in which starting position and ending position isn't same it will eventually jump out of bound!

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

Why 2*n/3?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let's first get the explanation of "why n/3" our distribution sequence is definitely going to be 1,2,1,2... so on. Before we check for n%3, on the last birthday he must have given 2 stones. So considering a consecutive pair of 1&2 as a single unit i.e we are giving 3 stones at a time(in your mind you can assume it to be as 1+2) we find n/3. Example lets say he has 5 stones so 5/3 = 1. This 1 is interpreted as (1,2) meaning 2 times(**therefore 2n/3**) remainder = 2 so he can give 1 more stone as gift and not 2 as on her last birthday he has given 2 stones.