thezodiac1994's blog

External Contest questions.
By thezodiac1994, 10 years ago, In English

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.

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

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

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

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

    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

    → Reply