Russian Code Cup 2016 — Third Qualification Round Editorial
By RussianCodeCup, history, 8 years ago, translation, In English
A. Rectangle and Squares

To solve this problem, notice that the sides of the Elijah's rectangle don't matter, only the area is considered. So he can use any number of squares to create a rectangle of size C × nC for any positive integer n.

The optimal n is the result of the division AB / C2 rounded either up or down. So we just check two variants and choose the better one. Additionally, it is important to remember that n > 0, so sometimes it is impossible to round down.

B. Zeroes and Ones

First notice, that we can make inversions only in one string. Also notice that the order of inversions doesn't matter.

So the solution is greedy: consider characters of the first string from left to right. If the corresponding character s1[i] ≠ s2[i], we inverse characters i, i + 1 of the first string. In the end check that s1[n] = s2[n], if it's not, there is no solution, in the other case we have found the only, and therefore optimal, solution.

C. New Track

The solution is using special construction.

First, let us show how to create the track with maximal possible k. Starting with the horizontal segment, each vertical segment would cross all previous horizontal segments except the adjacent one. The example with 14 segments is shown in the picture.

To get exactly k segments first draw 2l segments such that l(l - 1) / 2 ≥ k > (l - 1)(l - 2) / 2, make a small track with k intersections. To do so, start creating the maximal example, but terminate the last segment after required number of intersections. The remaining n - 2l segments can be added in the beginning of the track to form the spiral around the smaller track. See picture below for example, where n = 17 and k = 9.

The constraint on k is really the maximal bound on the number of intersections of n segments. We omit the proof, but the hint is: look at the number of intersections of the pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or only the segment 1, if n is even).

D. Tree

Let us add weights to tree edges, and set edge weight equal to 1 initially for all edges. Now instead of removing the vertex we would change the weight of the edge from it to its parent to 0. The distance between any pair of vertices would be equal to the distance that would be should we had actually removed the vertex.

We can solve the new problem as follows. For each vertex in the initial vertex find the distance from the root to the vertex, and put the distances to the array in DFS order. After changing some edge weight, we must change the distances in the continuous segment of the array. This can be implemented using, for example, range tree.

Now the distance between vertices can be found, using : dab = da + db - 2·dlca, where lca — is the least common ancestor of a and b, dv — is the distance from the root to v.

E. Barbarians

Notice that the angriness of all people in one connected component is equal to their initial angriness multiplied by some value, the same for all islands in this component.

Let us process edge removal in time proportional to the size of the smaller components that appears after its removal. In this case the time complexity of the algorithm would be . To prove the complexity notice that for each vertex when it is in the smaller component, the size of the component at least halves. So it can only happen times.

If removing the edge we could know which component is smaller, we could traverse it and move its vertices to a new component, leaving the vertices from the larger one in the old one. But we don't know which component is smaller. So let us run two BFS-s simultaneously in both components, and when one of them terminates, terminate the other one as well. This way the time for such BFS would be proportional to the size of the smaller component.

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

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I kinda don't agree with "This way the time for such BFS would be proportional to the size of the smaller component.". It is not explained how we run them in parallel in details, but since sizes of components are mentioned I suspect authors meant alternately doing "take vertex v from on of queues and process its neighbors". This approach is O(n2), because that vertex can have O(n) neighbours and indeed on a star graph it runs in such complexity. I processed edges one by one which ensures it works fast enough, but is a bit tricker to implement. Very standard problem.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +35 Vote: I do not like it

    Another nice way for that,

    https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting/editorial

    bool bdfs(int v, int from, int &rem) {
  --rem;
  if (rem < 0)
    return false;

  for (int to : g[v]) {
    if (to != from)
      bdfs(to, v, rem);
    if (rem < 0)
      return false;
  }

  return true;
}

int getSmallest(int u, int v) { // u and v in diff components
  int k = 1;
  while (true) {
    int temp;
    int ua = bdfs(u, 0, temp = k);
    int va = bdfs(v, 0, temp = k);
    if (ua)
      return u;
    if (va)
      return v;
    k *= 2;
  }
}

    I don't know it's popular but I learnt it recently and I think it's more simpler than parallel bfs.

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

      Nice trick :). However it take some guts to initialize reference with "temp = k" :D

      → Reply