Блог пользователя chrome

Topcoder Single Round Match 648
Автор chrome, 9 лет назад, По-русски

Всем привет!

Завтра в 15:00 MSK состоится Topcoder SRM 648.

Предлагаю обсудить задачи после контеста!

  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

How to solve B div1?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится +42 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А где можно посмотреть место в общем зачете?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      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

      → Ответить