gen's blog

By gen, 10 years ago, In English

405A - Gravity Flip

Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.

Solution complexity: O(n), since we can sort by counting.

405B - Domino Effect

If the first pushed domino from the left was pushed to the left at position l, all dominoes at prefix [1;l] fall down, otherwise let l be 0. Similarly, if the first pushed domino from the right was pushed to the right at position r, all dominoes at suffix [r;n] also fall down, otherwise let r be n + 1. Now, in the segment (l;r) there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides.

When does a domino at position p in segment (l, r) remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the pushed dominoes closest to p (from both sides). It is pushed by dominoes, only if the closest from the left was pushed to the right, and the closest from the right was pushed to the left. Suppose these dominoes are at positions x and y, x < p < y. Then, the only way that the domino is still standing is if it is positioned at the center of the block [x;y], which could be checked by .

Solution complexity: O(n) / O(n2), depends on implementation.

406A - Unusual Product

Written as a formula, the problem asks to find the value of

Suppose that i ≠ j. Then the sum contains summands AijAji and AjiAij. Since the sum is taken modulo 2, these summands together give 0 to the sum. It follows that the expression is always equal to the sum of the diagonal bits:

Now, each query of type 1 and 2 flips the value of exactly one bit on the diagonal. Thus we can calculate the unusual product of the original matrix, and flip its value after each query of type 1 and 2.

Solution complexity: O(n + q), if we don't take the reading of the input into account... :)

406B - Toy Sum

Let's define the symmetric number of k to be s + 1 - k. Since in this case s is an even number, k ≠ s - k.

Note that (k - 1) + (s + 1 - k) = s, i.e., the sum of a number and its symmetric is always s. Let's process the given members x of X. There can be two cases:

  1. If the symmetric of x does not belong to X, we add it to Y. Both give equal values to the respective sums: x - 1 = s - (s + 1 - x).
  2. The symmetric of x belongs to X. Then we pick any y that neither y and symmetric of y belong to X, and add them to Y. Both pairs give equal values to the respective sums, namely s.

How to prove that in the second step we can always find such y? Let the number of symmetric pairs that were processed in the step 1 be a, then there remain other pairs. Among them, for pairs both members belong to X, and for other pairs none of the members belong to X. To be able to pick the same number of pairs for Y, as there are in X, we should have

which is equivalent to , as given in the statement.

Solution complexity: O(s) / O(n).

406C - Graph Cutting

It can be proved that only graphs with an odd number of edges cannot be partitioned into path of length 2. We will construct a recursive function that solves the problem and also serves as a proof for this statement.

The function partition(v) will operate on non-blocked edges. It will partition the component of vertex v connected by the non-blocked edges into paths of length 2. If this component has an odd number of edges, the function will partition all the edges of the component, except one edge (u, v); the function then will return vertex u, expecting that the parent function call will assign it to some path.

The function works as follows: find all vertices that are adjacent to v by the non-blocked edges, call this set adjacent. Then block all the edges from this set vertices to v. For each u in adjacent, call partition(u). Suppose partition(u) returned a vertex w. That means we can pair it into the path (v, u, w). Otherwise, if partition(u) does not return anything, we add u to unpaired, since the edge (v, u) is not yet in any path. We can pair any two vertices of this set u, w into a single path (u, v, w). We pair as much of them as possible in any order. If from this set a single vertex, u, is left unpaired, the function will return u. Otherwise the function will not return anything.

The function could be implemented as a single DFS:

partition(v) :
    adjacent = { u | not blocked[(u,v)] }
    for(u : adjacent)
        blocked[(u,v)] = true

    unpaired = {}
    for(u : adjacent)
        int w = partition(u)
        if(w = 0)
            add(unpaired, u)
        else
            print(v,u,w)

    while(size(unpaired) >= 2)
        int u = pop(unpaired)
        int w = pop(unpaired)
        print(u,v,w)

    if(not empty(unpaired))
        return pop(unpaired)
    else
        return 0

Solution complexity: O(n + m).

406D - Hill Climbing

Note that the path of each hill climber is strictly convex in any case. Let's draw the paths from all hills to the rightmost hill. Then these paths form a tree with the "root" at the top of the rightmost hill. We can apply the Graham scan from the right to the left to find the edges of this tree. Each pop and insert in the stack corresponds to a single edge in the tree.

Now it is easy to see that for each team of climbers, we should calculate the number of the lowest common ancestor for the corresponding two vertices in the tree. The size if the tree is n, so each query works in .

Solution complexity: .

406E - Hamming Triples

Let's look at the Hamming graph of all possible distinct 2n strings, where each two strings are connected by an edge with length equal to the Hamming distance between these strings. We can observe that this graph has a nice property: if we arrange the vertices cyclically as a regular 2n-gon with a side length of 1, then the Hamming distance between two strings is the length of the shortest route between these vertices on the perimeter of the polygon.

For example, the figure shows the graph for n = 3. The gray edges have length 1, the orange edges have length 2 and the blue edges have length 3. That is the corresponding Hamming distance.

Now, we can convert each string coded by a pair (s, f) to an integer (f + 1)·n - s. The new numbers will be 0, 1, ..., 2n - 1 and correspond to the same cyclical order on the perimeter of the polygon. The given strings are mapped to some subset of the vertices. Now we have to find the number of triangles (possibly degenerate) with maximal perimeter in this subgraph. It will be useful to keep the new converted numbers sorted.

First, we can figure out what this perimeter could be. If there exists a diameter in the full graph, so that all of the points are on one side of the diameter, the perimeter is 2d, where d is the length of the longest edge:

Then any triangle with two vertices at the longest edge points and the third one being any point has the maximal perimeter. Since the numbers are sorted, the longest edge in this case will be produced by two cyclically adjacent elements, which is not hard to find.

If for any diameter this does not hold, then the maximal perimeter is 2n. This can be proved by taking two different points a, b and drawing two diameters with them as endpoints; since it is not the previous case, there shoud be a third point c in area where the perimeter of triangle a, b, c is 2n.

The tricky part is to count the triples in this case. We do this by working with the diameter (0, n). There can be several cases:

  1. A maximum triangle has vertices 0 and n. This a simple case: with any other vertex as the third the triangle has perimeter 2n.
  2. A maximum triangle has vertex 0, but not n. Then the second vertex should be in interval [0, n), and the third in interval (n + 1, 2n - 1], and the clockwise distance between the second and the third should not exceed n (since then the perimeter of the triangle would be less than 2n). We count the number of such triples iterating two pointers (one in each of these intervals). For each pointer in the first interval, all points from n + 1 till the second pointer will make a maximal perimeter triangle. We similarly solve the case where the maximal triangle has vertex n, but not 0.
  3. The maximal triangle does not have 0 or n as its vertices. Then one vertex of the triangle should be on one side of diameter (0, n), and two should be on the opposite side. To count them, we iterate a vertex pointer on the first side, say, (0, n); let the diametrally opposite vertex on the opposite side be x. Then the second vertex can be any in [n + 1, s], and the third can be any of the [s, 2n - 1]. It is easy to calculate these numbers using partial sums on the circle. Note that s can be both the second and the third vertex (since strings can repeat). So we iterate this pointer over all one side vertices and update the answer. Similarly we solve the case where a single vertex is on the other side, and two on this side.

One only needs to be careful with the formulas in each case.

Solution complexity: , because of the sorting.

Post Scriptum

What were your solutions? Feel free to share any solutions or thoughts! For example, was there a solution to DivI E simpler than in this tutorial?

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Yes, there was a simpler solution to Div1 E :D. I'm pretty sure the idea's the same, but I find its phrasing really simple to understand.

Imagine you picked 3 strings and want to express their . Each of N bits contributes to the Hamming sum with 2 if one of the chosen strings has a different bit at that position than the other two and 0 otherwise. That means the Hamming distance is 2N - K, where K is the number of positions where the 3 strings have the same bit (all 0 or all 1).

We'll call si the type of a string. Let's fix a type t now.

Let's first look at the case when a, b are of type t and c is of type 1 - t. W.l.o.g. fa ≤ fb. If fa ≤ fc ≤ fb, the maximum value of the Hamming sum is 2N — and it can't be maximized any further. The number of triples for given t and c is the number of pairs {a, b} such that sa ≤ sc ≤ sb and their sum over all c (for given t) can be found using 2 pointers on a sorted array.

What if there's no triple {a, b, c} for which fa ≤ fc ≤ fb? It means that values fc of all c are either all (strictly) below the smallest fa or all above the largest fb. W.l.o.g. assume the first case. In order to minimize the number of positions with identical bits (the ones between the fc + 1-st and fa-th), we need to pick the largest fc and the smallest fa; fb can be then picked however we want.

There is a third case where all 3 strings are of the same type t. W.l.o.g. assume fa ≤ fb ≤ fc. It's obvious that there are fc - fa positions with non-identical bits, and so we want to maximize fc - fa. This is the most easily done by picking the largest fa and the smallest fc; once again, fb falls into the abyss of oblivion :D

Notice that each case leads to one value of cyclic Hamming distance for all triples counted in it. Also, all cases are disjoint — we can't count a triple in 2 cases.

The rest is just about treating all cases (we try both t in the same way), writing the formulas for and for computing the number of triples — watch out for equal fi — and picking just the sum of cases with the maximum Hamming distance. More on that in the code: 6127737. Time complexity: also .

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

Hi gen, regarding your solution for Graph Cutting Problem, I tried to understand the logic of partition function which I could not understand clearly, I got the idea in somewhat high level fashion, But I could not implement it. I implement your function as it as you have provided, your partition function always returns 0.

So please post your code for this problem so that I can learn from it.

Here is my code http://ideone.com/Ny9PjL

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

    Sorry for the trouble, I corrected the mistake. Here is my code, but there are some redundant structures, as I now realize.

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

      sorry to trouble you again, but with this modification too, I am getting TLE on a large test case http://codeforces.com/contest/406/submission/6127948. I feel like my code is going into cycles :(

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

        This test contains a full graph with 444 vertices, you can try it locally. Our Java solution also works slower than average on this test, since it makes a new ArrayList in each DFS call. Maybe you have a similar problem, since you make two vectors in each call.

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

I feel that something wrong with the 406C — Graph Cutting solution: print(u,v,w) where u and w are adjacent to adjacent vertex to current v that is why they are not adjacent with v directly, aren't they? That is why my direct realization of algorithm, which is written here achives wa1

I think that there should be smth like

    for(u : adjacent)
        int w = partition(u)
        if(w not 0)
            add(unpaired, **u**)
        **else**
**            print(v,u,w)**

rather than

    for(u : adjacent)
        int w = partition(u)
        if(w not 0)
            add(unpaired, w)

Could you explain me, please, am I wrong?

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

    Thanks, my wrong. It should be

    if(w = 0)
        add(unpaired, u)
    else
        print(v,u,w)
    

    If the component was partitioned completely, the edge (v, u) is left unpaired. Otherwise we make a path (v, u, w), as you suggested.

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

Is it just me here think that Div2 D is easier than C ? :))

»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Thanks for the round! I thought Div1 C in particular was a nice problem. Here's my solution:

It is clear that the total number of edges must be even. Our goal is essentially to direct each edge in a way that gives each vertex an even indegree. Then we can form the paths by taking pairs of edges that point to the same vertex.

To do this, find any spanning tree in the graph. Then, direct all edges not in the tree arbitrarily. We will use the spanning tree to "fix" the parities of the indegrees of each node.

However, this is easy to accomplish with tree DFS. For each node, we run the DFS on all of its children and then direct the node-parent edge so that the node's total indegree is even. The root node will automatically have even indegree if the total number of edges is even.

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

What is meant by Non-blocked edges in Div1 C?

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

    this mean the edges we have not alredy blocked. It is quite clear written in pseudocode: we are blocking all adjacent and still unblocked to current vertex edges, before before doing dfs with their ends.

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Div 1 A is a very nice problem !!!

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

Can someone explain how LCA is used in the solution for problem D?

Take, for example, nodes 5 and 7 from the picture in the solution. LCA(5,7) = 6, but the answer is actually 7...

Can someony clarify this?

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

    The edges are not oriented to the higher peak, because the climbers don't go to the higher peak. They're oriented to the right, because the climbers always go to the right. LCA(5,7)=7.

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

      Ahhhh, I get it. I hadn't read the part that says "with the root at the top of the rightmost hill".

      Thanks!

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

Can someone provide the demonstration for problem C Div 1

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

I solve Div.1 E problem by list all the possible conditions. And I also find out many people pass this problem by similar idea. Xellos has explained the idea at length. By the way,there are many details in equal strings. Nice problem any away!