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

External Contest questions.
Автор thezodiac1994, 9 лет назад, По-английски

I require help solving these couple of questions :

NOTE: It is a past contest i attended onsite.

1) https://www.hackerrank.com/contests/codemania-finals/challenges/barcode-formatter

I thought along the lines of max flow however was not able to construct a network for the problem.

2) https://www.hackerrank.com/contests/codemania-finals/challenges/dorae-games

Thought of Bipartite matching after construction of the graph using GCD(trying all n*n pairs for creating edges) but the solution times out on the last test case I think due to the large number of edges which are possible making the matching slow.

Here is my soln for 2 -> http://ideone.com/2uj2OD

Thanks in advance.

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

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

The first one is quite straightforward DP: d[n][k][c] -- we processed n columns, and last k of them are of color c. The value is minimal cost of such configuration. Seems to be O(n2).

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

    So if cost[i] [j] [c] represents cost to color columns i to j with color c (which could be pre computed in n*n)

    dp[n][k][c] = cost[n-k+1][n][c] + min (dp[n-k][x....y][c'])

    where c' is the complementary color.

    This would be the main equation ? Thanks

    → Ответить