chrome's blog

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

Hello, %username%!

Tomorrow at 15:00 MSK will be held Topcoder SRM 648.

Let's discuss problems after contest!

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

»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve B div1?

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

    Think the problem as choosing n numbers from ∞ × k matrix, where the first row has numbers from 1 to k, and then every row is previous row with values doubled.

    We have to minimize the sum of the chosen numbers, which is the same as minimizing the largest chosen number.

    Now it's possible to see that if you choose m numbers from a row to the solution, you choose ⌊m / 2⌋ numbers from the next row, ⌊m / 4⌋ from the next and so on, unless you choose the whole row. Using this fact, you can first binary search how many whole rows has to be chosen, and then binary search how many numbers have to be chosen from the first not entirely chosen row.

    The largest chosen number is either the last number of the last entirely chosen row, or the last number of the first not entirely chosen row.

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

      All the last numbers of not entirely chosen rows will be the same?

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

Have you seen Petr's solution for div1 hard problem? :O

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

Div-2 1000 pointer :

Here is my dynamic programming solution :- Let us define the state as follows:- (currentPos, A's till now, B's till now, pairsTillNow) with the meaning, can we reach state where we have exactly 'k' pairs and currentPos=n ?

TRANSITIONS:- 1) Fill in 'A', to move to the state (currentPos + 1, A's till now + 1, B's till now, pairsTillNow).

2) Fill in 'B', to move to the state (currentPos + 1,A's till now, B's till now +1, pairsTillNow + (A's till now) )

3) Fill in 'C' to move to the state (currentPos + 1,A's till now, B's till now, pairsTillNow + (A's till now) + (B's till now) ).

If from the present state, any of the future state yields the value true, then the value of present state is true as well.

Finally, a string can be constructed if the value of state (0,0,0,0) is true. After this, a simple backtracking can be done to get one of the required string(s).

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

    String with maximal number of pairs is "AAA...ABBB...BCCC...C". Start with this string and pull down Cs, each swap gives -1 to number of pairs. If it's not enough, pull down Bs (final string "CCC...CBBB...BAAA...A" has 0 pairs). Number of pulled down Cs and Bs are easy to calculate and also last C/B pulldown is also trivial.

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

Div. 1 Hard was also given at NEERC's Western Subregional 2014. https://contest.yandex.ru/QF2014/contest/794/problems/G/ (requires Yandex login).

It's not 100% the same as it requires to calculate only the number of connected graphs, but it is easy to account for disconnected graphs afterwards.

There is a video editorial (unfortunately, only in Russian), which helped me understand the approach for this kind of problems a lot. (problem G starts at 48:48)

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

    Hi, since it's in Russian, do you mind giving some hint on how to solve it?

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

      Here's the solution from the editorial plus extra D(N,B) recurrence to account for disconnectedness:

      T(N) = 2N * (N - 1) / 2 — the number of graphs with N vertices.

      — the number of connected graphs with N vertices. We subtract the number of disconnected graphs from the total number of graphs assuming that the first vertex lies in the component of size k. Later we will be using the same technique (assuming that the first vertex lies in one of the subgraphs).

      — the number of 2-edge-connected graphs of size N. From the total number of connected components we subtract the number of connected components which have at least one bridge.

      — auxiliary function to calculate F(N, 0). Here we have a 2-edge-connected component of size K and N free vertices which we have to split into connected components. Each one of the connected components will have exactly one edge going to our 2-edge-connected component of size K, which leads to the multiplication by K * l.

      — the number of connected graphs with exactly B bridges.

      — auxiliary function to calculate F(N, B). Here we have a 2-edge-connected component of size K, N free vertices and B has the following meaning: the number of connected components + the total number of bridges in these components. On each step we assume that the first vertex lies in the component of size l with j bridges.

      — the number of graphs with N vertices and B bridges allowing disconnected components this time.

      In all these recurrences we assume that a single vertex is a 2-edge-connected component.

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

      I'll try to explain.

      My solution may be a little different from the intended one because I was too lazy to watch full video editorial for that problem.

      Consider the tree of biconnected components with the root at component contains 1. Our goal is to calculate the number of rooted labeled trees with biconnected components as the nodes.

      Let's calculate the following 3 functions:

      • dp1(n, b) -- the number of connected labeled graphs of n nodes with exactly b bridges.
        To calculate it we should iterate over size of root (biconnected component contains 1) and number of our childs in the tree.

      • dp2(n, b, k) -- the number of labeled forests of biconnected components (order of trees is important!) with exactly k trees and each tree have one colored node in its' root (the node is going to connect this tree with global root from dp1, in other words -- it will be one the bridges).
        To calculate it we can fix the number of bridges in the first tree and the number of nodes in the first tree and then call dp3 :)

      • dp3(n, b) -- the number of labeled trees of biconnected components with one colored node in its' root (it is going to connect that tree with global root from dp2).
        The way to evaluate it is almost the same as calculation dp1.

      One can find dp1(n, 0) as .

      As for dp2(n, b, k), one can calculate the same number of forests, but with no order is important condition just as .

      I hope my code will help to understand the rest.

      UPD: slowpoke.jpg

      → Reply