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