rng_58's blog

By rng_58, history, 7 years ago, In English

Let's discuss problems.

By the way, finally reached #1!

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

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

How to solve problem 900

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

    Ok, I have some ideas, and my solution passes system tests in practice room, but not sure if it's correct.

    The idea of my solution is that if we look at each rook as an edge between (row i) and (col j), then the graph should not have a cycle. Additionally, when we pair the rooks up, there should be at most one pair on each row and each columns.

    Also, we should not introduce any new pairs of rooks. Then for each existing rook, we decide if it will be contained in a row pair, or a column pair (2^20 possibilities), and check if there is a way to make a matching without violating the above conditions.

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

      I had the same idea as you and I wrote a straightforward mask dp and got TLE(actually RE because there were too many statuses)

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

        Actually, I didn't really bother checking if there was a valid matching at all.

        I only checked a condition on whether the number of rooks you need is strictly less than the total number of rows and columns (otherwise, there must be a cycle)

        However you have to not let rows / columns which contain no rooks at the end count towards your total.

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

      The only thing I was short of you was that I didn't notice "we should not introduce any pairs of rooks."

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

    Let's construct a graph with n red vertices and m blue vertices. For each '#' add an edge between corresponding vertices. Then we get a bipartitely colored forest. Now we want to add some edges between vertices of different colors, and satisfy the following:

    1. Keep it a forest.
    2. Each tree (connected component) contains odd number of vertices.
    3. Root the trees in an arbitrary way. We call a node "odd" if it has odd number of descendants (including itself). There must not be a node that has three or more odd children.

    The final state will look like the following. Black edges are newly added edges. Other colors represent original components.

    When the final state satisfies the conditions above, black edges can be uniquely assigned to one of colored components. For example, in the previous example, edges 1, 2, 3 should be assigned to green, purple, and orange, respectively. Look at the following picture:

    We want to connect node a with some blue node, node b with some red node, and node c with some red node. It doesn't really matter which red/blue nodes to choose. We just need to make sure that we don't form any cycles.

    Thus, we try all subsets of vertices that have "tails" (in the example above we chose three nodes a, b, c). Check the conditions 2 and 3. For these conditions, the choice of nodes with question marks doesn't matter.

    Can we satisfy the condition 1? For this, it is important to distinguish two types of components: a component with at least two nodes (it always have both red and black) and an isolated vertex. Let rneed, bneed be the number of red/blue question marks, rsingle, bsingle be the number of red/blue isolated vertices, and let comp be the number of non-isolated components. Then, it's not hard to prove that a valid assignment is possible if and only if max(rneed - rsingle, 0) + max(bneed - bsingle, 0) ≤ comp - 1.

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

Big congratulations on advancing and on #1!

My sad story: challenge phase, open a big solution, think "it's so big, surely it has a bug", challenge blindly, get -25, get 7th place instead of 5th :(

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

    My sad story: Medium failed on 1 test out of 280 cause it runs 2.1s (TL=2s). Get 12th place instead of 4th.

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

      Btw, I am not sure how arena works in such cases. Are you sure that your code gave correct answer after 2.1s or did arena just kill your solution after that?

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

        I had execution time approximately 5s when I tested inefficient solution. And it passed after some minor optimisations. But I can't be sure of anything in arena :)

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

    ;)

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

    Heyy! No screencast since long :(
    Everything alright??

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

How to solve 500 properly without things like "if we add this pruning heuristic to our backtrack then it seems that it fits in TL on systests, but no idea why"?

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

    I'm sorry, looks like I accidentally send the comment, good version of the comment is below.

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

      Can you describe that MITM approach? I had no idea how to make use of that technique. I think I figured out bruteforce that should handle k>=9 but didn't know what to do with smaller k values.

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

        I will describe it for k = 8 (for simplicity).

        I want to check all the variants of choosing 8 items. I'll divide them into two halves such that all the items from the first half is to the left to all the items from the second. Now let's fix the fifth item (the leftmost in the second half). Now I want to generate all the variants to take 4 items to the left to the fixed position (it will be the first half), then generate all the variants to take remaining 3 items to the right and for each variant of the second half count the number of good variants of the first half. For example, we can generate all possible sums in the first half, then sort them and use binary search. But it will be slow. Instead of sorting and binary search, we can use Fenwick tree (values are up to 4·107, so we have enough memory) and notice that we can move our fixed fifth item one position to the right easily: we only need to add new variants of the first half with forth item in the rightmost possible position. Now this soltuion works in time I mention earlier.

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

          Nice idea, I hoped that n^k/2 should be doable but was silly enough to think only about dividing all values into two halves which was obviously not working. All in all, that was pretty hard problem, but as for med of TCO3 it was just right.

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

    For k ≤ 8 we can do meet-in-the-middle, I've used Fenwick tree here, number of operations is about . For k > 8 real value of d is no more than 5·107 and much smaller if k > 9, so for now I will say that k = 9 is the worst case. We will sort all the values from big to small and then do a bruteforce the following way:

    void brute(int k, int pos, int sum) {
        if (D <= 0) return;
        if (k == 0) {
            D -= (int)(sum <= 0);
            return;
        };
        if (n - pos < k || getSum(pos, pos + k) < sum) return;
        brute(k - 1, pos + 1, sum - a[pos]);
        brute(k, pos + 1, sum);
    }
    

    I didn't prove it properly, but I'm pretty sure that every O(k) steps I will reduce D by 1, so the number of operations is about 5·108.