BackendDeveloper's blog

TopCoder Algorithm Round 3A
By BackendDeveloper, 10 years ago, In English

It is strange that nobody created blog about TopCoder round again :D

Question: After how many minutes will be avaible practice round?

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

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

They should be set up right now.

However, I have a better question: is there a way to make the 500-pointer and not to get completely stuck in coding and not to forget a few computation rules? It's obvious you have to do a bitmask DP (something like TSP dynamic solution), but I couldn't make it correctly...

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

    I think we should:

    1) merge each connected components to one vertex and memorize number of vertices within it

    2) compute expected distance between 0 and random vertex from its component (<=> sum of distances from 1)

    3) the same for 1

    4) expected distance between two randomly chosen vertices in other components (<=> sum of distances between each pair)

    5) compute expected edge cost between each two components (<=> sum of edges between all pairs in fixed two components

    6) do a dp on a graph which vertices are components, vertices and edges costs are those expected thingies I explained, where dp[mask] denotes expected distance from 0 to random original node from those components contained in a mask and prob[mask] denotes probability that we will obtain that mask durin our process

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

      I couldn't figure out how to get prob[mask] quickly, could you (or maybe someone else) elaborate?

      Is it fast enough to try getting there from all masks that are one smaller, and count good edges/all edges for each case?

      I'll have to remember that 2^18 can fit in memory for later competitions... :S

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

        Let sz[v] be number of original vertices in a component v.

        You iterate over all vertices in that mask other than that containing 0 and sum following values:

        prob[mask — (1 << v)] * sz[v] / (sz[v] + summed sz[v_i] over v_i which are not in mask)

        EDIT: Edited small bug in that formula

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

For the 250, what I did was like this — Convert the string init to a boolean array of 0s and 1s and now take the difference array. Now, we can add a couple of 1s(modulo 2) to any two equivalent indices modulo k. So, if we arrange them in a grid of (n/k) x k numbers, we need the row xor to be fixed and we have to maximize sum(pref(i) * val(i)) where pref(i) is the sum of the first i numbers(row-wise) in the grid. I spent over 45 minutes here but I couldn't solve it. What is the way to complete this idea?

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

    You first select wether you would invert first row in said table. Then for each column you count sum of associated values and sum of values but smallest one. Depending on oddity of number of zeroes you add one of this values to the answer (and add the other one for inverted first row)

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

    If you flip two consecutive K-element subsequences (that is, (i, i + 1, ..., i + K - 1) and (i + 1, ..., i + K)), only two lamps get toggled (i and i + K).

    Now it's crucial to note that every combination that is possible to do with K-element flips, can also be done with the following two:

    • toggle first K lamps,
    • toggle any two lamps distant by K.

    (each toggling of K consecutive lamps is a compound of these operations). It's much simpler now. Of course, each operation can be done zero times or once (it's no use doing it more than once).

    Let's say we haven't used first operation in optimal solution. Then our sequence dissolves into K sequences of elements distant by K, in which you can toggle two consecutive elements. This is easy to solve; if i-th sequence has an even number of turned off lamps, you can turn them all on; in opposite case it's obvious we can't turn them all on, but it's possible to leave off only the least valuable lamp in the sequence.

    What if we use the first operation? Then we just toggle first K lamps and then do exactly the same steps as before.

    // oops, I'm not the first :)

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

      // oops, I'm not the first :)

      It's sometimes called being ninja'd :D

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

    That wasn't clear for me why those moves mnbvmar explained are sufficient to obtain all possible configurations, but I proved that using linear algebra. In fact what we can achieve is a affine plane in Z2n which can be reached from starting point using (linearly independent) n - k + 1 vectors consisting of k consecutive ones, so that affine plane has dimension n - k + 1 and number of possible flips of lights distant by k is n - k, so after adding switching first k lamps we will obtain n - k + 1 linearly independent vectors spanning the same affine plane :).

    EDIT: Thinking about this one again... That is rather clear that those moves are sufficient. But that can also be a way to think about this :D.

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

    Well, you can split lamps into subarrays with fixed remainder mod K. Then, since 2 operations applied on [i, i + K) and [i + 1, i + K + 1) only flip lamps i and i + K (neighbours in one subarray), you can achieve any state of a subarray that has the same xor of all bits as the initial one. That means if there was an even number of off lamps in a subarray, you can set them all on, and if it was odd, you need to set the weakest one off.

    This is sufficient if the number of steps is even; if it's odd, you can flip some K consecutive lamps (it doesn't matter which) and repeat.

    → Reply