Hamada7's blog

ACPC old problem
By Hamada7, history, 8 years ago, In English

Hi,

I was trying to solve this problem (https://a2oj.com/p?ID=332) Any help would be appreciated

Thanks

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

Comments Comments (3)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I thought about this problem for a while, and someone proved me that this is NP hard, cause its 'find hamiltonian path' if theres only 1 color. I might be wrong tho, but i didnt came up with any flow-like solution, except for 'shuffle-shuffle-shuffle till we good', but it has exponentional complexity

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

max-cost(take negative costs) max-flow solution: choose which one of cells you start with and which you end with in one of 2^X ways for each color. Now (start,end) of each color is fixed. Edges from super-source to starts with cap=1, cost=0, from ends to super-sink with cap=1, cost=0, from each vertex to adjacent vertices(cap=1,cost=0). Also, vertex capacities=1(cap=1,cost=1). If flow=X and cost=n*m-2*X, then output solution backtracking from residual edges.
Time Complexity: O(2^X*F(n*m)) where F(n*m) denotes flow complexity(depends on flow algorithm used) for a single graph.

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

    How does it guarantee that colors are conected correctly? I mean why isnt it possible that flow from red source goes to blue sink?

    And also why does this approach find hamiltonian path? Well it doesnt, right? So it has to be wrong

    → Reply