MikeMirzayanov's blog

By MikeMirzayanov, history, 5 months ago, translation, In English,

Hello everybody!

The contest is over, and I've found that there is no post about the contest. I'm waiting for unfreeze of http://opentrains.snarknews.info/~ejudge/res/res10355 Who knows the expected time?

Let's discuss problems here.

Also it is interesting how good was the onsite in Novosibirsk. What impressions?

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

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve 11?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    For each suffix compute the value (as a decimal number) mod P. Let ai be the value corresponding to the suffix starting at i.

    Then, for a fixed j, the value of the substring [i..j) only depends on ai. Now it's easy to get an O(nlogn) solution for each query.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In fact you can get O(NT) solution (without logarithm) by using hash table.

      Just make sure you do O(N) insertions total instead of O(NT), otherwise you'll get TL unless you write a hand-optimized hash table.

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve 5-th problem?

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

    I think 5th is MCMF problem. You can fix number of people who votes for no one, and maximum votes that other candidates get. Then build network with this variables and run MCMF. But not sure about whether it fits in time limit or not. I didn't have time to code it at contest because of 11th problem time limit in DIV2 :) I hope someone who solved it will write more detailed solution.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it with MCMF.

    Let a be the exact number of votes that we want our winning candidate to receive. Construct a flow graph with source/sink, a node for each person that is voting (N nodes), and a node for each voting option (K + 1 nodes). We need the following edges:

    • Source to the node corresponding to our candidate with capacity a and a very large negative cost.
    • Source to the other candidate that can be voted for with capacity a - 1 and zero cost.
    • Source to "not voting" with infinite capacity and zero cost.
    • Each voter to sink with capacity 1 and zero cost.
    • Each voter to the voting option with capacity 1 and cost equal to the cost of having that voter choice that voting option.

    It is clear that the minimum-cost flow here corresponds to the minimum cost required to have our candidate win with exactly a votes (the large negative cost from the source to our candidate forces any minimum-cost max flow to vote for our candidate a times). We can increment the cost of this flow by a·(negativecost) to get the exact cost, and look at the residual graph to reconstruct the solution. Finally, we can iterate a from 1 to N to get the optimal assignment.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      One thing worth noting is that the function "cost to win with exactly a votes" (depending on a) is convex. This can be proved by taking optimal flows for a = x and for a = z, then observing that their convex combination with appropriate coefficients would be a valid flow in the graph for a = y (where x < y < z).

      So you could optimize your solution by doing something like a ternary search over a.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 10? It seems brute force is not too slow and only slight improvement is enough.

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it +18 Vote: I do not like it

    1) Brute first K moves.

    2) After that you have state (X, Y, DestructedWalls). For optimizations purpose DestructedWalls can be 64 bit mask.

    3) Clean up bits in DestructedWalls mask, if you can't visit some walls anymore with (n - K) moves (to reduce different masks count).

    4) After that there are not so many different states. For each just brute remain (n - K) moves.

    K ~= 23 - 24 works for us in upsolving.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      In fact, there is no need to do any portion of brute force here.

      You can run DP with states: (turns passed, robot position, 64-bit mask of destroyed walls), always storing the states only for a single current value of "turns passed". In each state store also its multiplicity (i.e. how many ways are there to get it). After modelling each turn, merge all equal states.

      Now you have to add the "finish optimization". For each number of passed turns and robot position, precompute the set of cells you can theoretically move into regardless of whether any brick wall is destroyed or not. Then in the main DP you do bitwise AND between the mask of destroyed walls and mask of potentially visitable cells in future (i.e. you are forgetting about destroyed walls you can never bump into).

      With such a solution, there is no need to tweak a special parameter K, and no need to write recursive search.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve C and D?

Also, I was wondering if there is any clever solution for F. I solved it using Hopcroft's DFA minimization algorithm.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    For F: take any remainder x modulo M. Now consider the chain of segments: [x, x], [b*x, b*(x+1)-1], [b*b*x, b*b*(x+1)-1], ... Find the first segment in this chain that contains 0 modulo M. The pair (k, (x*b**k) mod M) now uniquely defines state x, where k is the number of the segment (in other words, the size of the segment and its left boundary).

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

    C: we will only use "is intersection empty" questions. First, find bounding box using binary searches by X and Y. At least one of its corners is a vertex of the triangle, we can check by truncating a small 0.5*0.5 triangle from the corner. Now we've found a vertex and a 90 degree angle containing everything. Now use two binary searches by angle to find rays containing two sides from that vertex. Finally, use binary searches with half-planes parallel to one side to find the vertex on the other side.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    D: I find it really hard to explain, but the solution itself is really easy. First, the problem easily boils down to: you have N left ends, then N right ends of segments, connected somehow in pairs. Let's call two segments connected if they intersect, but not one lies inside another. Now we need to find connected components, check if each component is bipartite, and color with two colors if it is, all faster than N**2.

    It turns out that because all left ends come before all right ends, the structure is really simple. Let's look at the left end corresponding to the first right end. All left ends after it intersect it, and thus must have the opposite color. Thus, their right ends must go in reverse order (to avoid intersections between them). Now let's consider the rightmost right end of those. All remaining uncolored right ends to the left of it, again, must have the first color, and so on.

    Code for the coloring part:

            vector<double> sum_inside(2);
            vector<double> sum_outside(2);
            int bl = 0;
            int el = 0;
            int br = 0;
            int er = 1;
            double res = 0;
            while (true) {
                bool upd = false;
                int prev = -1;
                for (int ir = br; ir < er; ++ir) {
                    int cur = invr[ir];
                    if (color[cur] < 0) {
                        upd = true;
                        color[cur] = 0;
                        sum_inside[0] += inside[cur];
                        sum_outside[0] += outside[cur];
                        if (l[cur] < prev) {
                            out << -1 << endl;
                            return;
                        }
                        prev = l[cur];
                    }
                }
                br = er;
                el = max(el, prev + 1);
                prev = -1;
                for (int il = bl; il < el; ++il) {
                    int cur = invl[il];
                    if (color[cur] < 0) {
                        upd = true;
                        color[cur] = 1;
                        sum_inside[1] += inside[cur];
                        sum_outside[1] += outside[cur];
                        if (r[cur] < prev) {
                            out << -1 << endl;
                            return;
                        }
                        prev = r[cur];
                    }
                }
                bl = el;
                er = max(er, prev + 1);
                if (!upd) {
                    assert(bl == el);
                    assert(br == er);
                    assert(el == er);
                    res += min(sum_inside[0] + sum_outside[1], sum_inside[1] + sum_outside[0]);
                    if (er == n) {
                        break;
                    }
                    sum_inside[0] = sum_inside[1] = sum_outside[0] = sum_outside[1] = 0;
                    bl = el;
                    br = er;
                    ++er;
                }
            }
    
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      In fact, we did not find this a simple solution. We used a more technical approach.

      Renumber wires on the left to be [1..N] (and wires on the right accordingly). Then the indices of wires on the right form a permutation. It is easy to notice that we have to break this permutation into two increasing subsequences (one for inner wires, one for outer wires). For each element, we know the cost of including it into each subsequence.

      This problem can be trivially solved by DP with O(N2) states. In fact, you can use only O(N) states looking like (size of prefix processed, which subsequence contains last processed element). To achieve this, you have to add whole increasing blocks to alternating subsequences, one block on each step of DP.

      This DP takes O(N) memory, but O(N2) time. It can be optimized with RMQ structure to O(NlogN) time in a way similar to how classical "maximal increasing subsequence" is optimized with RMQ. In fact, it is also possible to optimize it to pure O(N) without any data structure by simply saving some minimums during long increasing runs. Of course, the details are rather nasty =)

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

        Right, the two increasing subsequences paradigm also allows to explain my solution a bit easier: let's look at 1. All numbers to the left of it must go to the other subsequence, and thus be in increasing order. Let the last of them (right before 1) be X. Now all remaining numbers less than X must go to the same sequence as 1, and be in increasing order, and so on.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How one can solve 8?

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

    Yes, I would like to know about solving this problem too. I got TL 16 because of usual tree structure (bad idea when tree looks like a line — so queries would be executed O(N)), but what is right solution?

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

    What we need a data structure that allows to update numbers in a tree and to find the sum of numbers in a subtree. If we do a preorder traversal of the tree, then any subtree will correspond to a segment in that ordering. And a data structure that allows updating numbers and finding segment sums is a Fenwick tree.

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

      Thank you for your answer, I thought about segment tree, but could not understand how to enumerate vertices (build segment tree)... It is not difficult for me when we build segment tree according to the array 1..N, but when we have tree with randomly enumeration in that problem — I don't know about representing.