chrome's blog

Topcoder Single Round Match 691
By chrome, 9 years ago, In English

Hi there!

Today at 18:00 MSK will be held Topcoder SRM 691.

Let's discuss problems after contest!

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

Comments Comments (39)
| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve 250? Also, why is the logic of sorting in increasing order of B/A ratio incorrect for 500? All solutions in my room got hacked because of this.

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

    About 500:

    Try this test

    {3, 1}

    {2, 1}

    1000

    It's better here to do {1, 1} first, and {3, 2} second.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    250: I pictured it as if it was a directed graph with edges i -> a[i]. I've found all vertices reachable from 0 and 1 by following those edges, let's call those A and B respectively, and their common part C.

    If C is empty then 0 and 1 are in different components at the beginning, and we need to choose at least one vertex from A and at least one from B, and all such choices are good. If they have some common vertices, then a choice is bad only if we choose some vertices from C, but they will all be in A \ B, or all in B \ A.

    So in both cases it's a simple formula depending only on size(A), size(B), size(C).

    500: Both halves must be sorted according to this criteria, but not the entire array. If there are just two elements then it's optimal to sort them according to something like B/(A+X).

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

      Can you explain what does A\B signifies?

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

        B/A means that we sort the positions on the basis of the ratio B[i]/A[i], for each i.

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

          I think you misunderstood my question. I'm asking about 300 points problem. krismaz's line states "If they have some common vertices, then a choice is bad only if we choose some vertices from C, but they will all be in A \ B, or all in B \ A.". I couldn't understand latter part. (A\B and B\A)

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

            It is a set difference (see link). It is a set, which contains all elements from A, which are not in B.

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

        A\B means set difference. The A\B set contains elements that are present in A but not in B.

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Passed B with 60 million state DP :D

I am interested to hear the actual solution though, I saw jqdai0815 use a 3-dimensional DP but I couldn't understand it.

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

    I don't know if this counts, but here is an idea.

    I had a 4-dimensional DP (total numbers passed; number of people in the first half; sum of B in the first half; sum of B yet to be taken in the second half) with (N / 2 * maxB)2 * N * N / 2 = 78m states.

    The starting points are (0, 0, 0, S) for all possible S. Therefore you can track through S in the outer loop and have a 3-dimensional DP with the same complexity.

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

      If I'm in a state, how do I know which projects can be taken and which have already been completed?

      Is there a greedy solution that works if there were no training camp? (Edit: tunyash says yes and I will try to figure out why)

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

        Yes. You sort all the states by a[i] b[i]. The proof is based on the fact that if you compare gains you get by processing a[i], b[i];a[j], b[j], as opposed to the opposite order, as two last elements, they are exactly equal to C + a[i] * b[j] and C + b[i] * a[j] in the other, irregardless of what experience you had before that.

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

          That makes sense, thanks to you and tunyash for your explanations.

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

        Sorry, saw your comment only later. But how then did you then solve the problem without fixing the order of numbers?

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

          10-dimensional DP on:

          • Number of people with b[i]=1
          • Number of people with b[i]=2
          • etc.

          The worst case is 5 people with each value of b[i], which gives 610 ≈ 6·107 states.

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

    First of all if X = 0 we should sort projects by a[i] / b[i] and in each half that order is the best possible.

    Let's fix B sum of b[i] in the second half. Then dp[i][j][k] — the best possible amount of money with j projects in the second half, b[s1] + b[s2] + ... + b[st] = k where s1, s2, ...sk is the set of projects in the second half. Then if we put i-th project to the first half we should increase answer by a[i]·(B + b[0] + ... + b[i]) and something similar if we put i-th project to the second half. Then the answer with fixed value of B is dp[n][n / 2][B].

    → Reply
»
9 years ago, # |
  Vote: I like it +48 Vote: I do not like it

That fastest solution to div1 500 by totsamyzed made my day :)

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

    I wonder if it can be challenged within the given constraints. I constructed a test where you would need on average N2 / 4 swaps to get to the optimal state from the random one, but this attempt at failing it failed:)

    → Reply
»
9 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Couldn't understand what's wrong with my answers in 900 during the last two minutes, and now I got it; I thought there should be an intersection of rectangles but statement asks to make a union of them. I'm crying.(

Despite the fact 500 fell, I'm still going up! :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Cool bug in 500: you should change i to i1 in one place. :) That's what happens when you forget about sort in the first place.

    → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve 500? Did anyone succeeded with something like simulated annealing?

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

    Yes, see the aforementioned solution by totsamyzed. Although, I believe, it is simple hill climbing.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Yes, I also did it. I use something like gradient descent and pass system test.

    Repeat following procedure for about 10 times:

    1. First, sort all elements by b_i/a_i

    2. Repeatly about 10^5 times: randomly swap one from first half and one from second half. Then, sort first half and second half by b_i/a_i again. If the resulting list is better then take it to replace the original one.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From the last 3 contests there has been one problem each, that can pass system tests using random_shuffle :)

→ Reply
»
9 years ago, # |
  Vote: I like it +69 Vote: I do not like it

Wow so popular :)

→ Reply
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

How to solve div2 1000?

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

    In my room I saw a guy who just hardcoded sums for each of i * 1e7 up to 1e9 (100 numbers), then summed up values from (n / 1e7 + 1) to (n) and added this numbers. It passed :P

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know how to solve the following problem. With solving the below I would be able to solve d1-hard, but maybe my approach isn't a good one. So, maybe the following problem doesn't have a solution.

You are given n (n ≤ 106) integers t1, t2, ..., tn (0 ≤ ti < 230). For each of n2 pairs of numbers we take their bitwise or (in code it would be t[i] | t[j]) and we find the first bit set to 0. For each of 31 bits count for how many pairs we found this bit.

Do you see how to solve it? Maybe incl-excl principle?

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

    Why 230? There are only 26 possible answers, and this can be solved in 226·26 (forward pass — compute Di, mask =  count of tj so that tj is submask of mask and the last i bits are identical to the bits of mask, backward pass — compute di, mask =  count of ti, tj such that ti|tj is submask of mask, the last i - 1 bits are 1 and i'th bit is 0).

    But 226·26 is almost 2 billion, and I sincerely hope jury's solution is much faster (otherwise this is rather evil).

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

      It's 26 indeed, sorry.

      I think and hope that O(2k·k) is too slow here.

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

        My 2^k * k implementation passes =)

        http://puu.sh/paG0G/b57485addc.png

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 4   Vote: I like it +41 Vote: I do not like it

        well you can speed it up by considering the primes only — you will have 6 (1, 2, 4, 8, ..., 32) * 4 (1, 3, 9, 27) * 3 (5, 25), 3 (7, 49 :D), * 2 ^ 13 states which isn't much and you could apply the same idea. this is about 27 * 2 ^ 16 states
        mask means the state which we are in
        dp[mask][i] = the sum of cnt[other_mask]'s which other_mask has the same numbers from the last 17 — i primes and its first i primes are more than mask's

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

        The backward pass is only 227, so we just need to solve problem "given ti, count number of submasks of a mask among ti for all 226 masks" faster than 26·226. Not sure about the general case, but in this particular case, there is a structure on ti induced by the problem — subrectangles of a rectangle correspond to submasks. So maybe this can be solved with a careful counting of subrectangles (which seems painful).

        (btw, where are topcoder problem editorials located nowadays? I wanted to see what's the jury solution for the problem, but finding it turned out surprisingly difficult)

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I spent majority of challenge phase trying to hack specific code and when I finally got test it was rejected because I inputted numbers separated by commas and spaces however I shouldn't have spaces there and when I was getting rid of them that code was challenged >_>. Screw you TopCoder >_>.

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

    Think positive: at least you're not getting Internal Server Error.

    → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When do they post the editorials on tc site ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div 2 1000 anyone?

→ Reply