aajjbb's blog

A South America regional problem
By aajjbb, 11 years ago, In English

Hi, the South American ICPC regional phase took part yesterday. I wasn't able to solve the problem Link. Some contestants said to me that it's solved by max flow, do someone know another solution or have a clue on how to build the flow graph ? Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe you find these useful:

TopCoder max flow tutorial with the example problem of rooks.

RookAttack

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The idea is convert each '.' in a two nodes left and right, then for each pair of '.' that we can't take at the same time add a undirected edge from left to right. The result will be the (http://en.wikipedia.org/wiki/Maximal_independent_set) Maximal independent set / 2 that in a bipartite graph is (nodes — matching).

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There was a problem from SWERC 2012 that the solution is very similar (Sentry Robots). I guess the judges were not expecting that many teams would solve this problem.

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

    I was impressed by the number of teams solving this problem as well, at a first glance, I didn't imagined of a graph problem, I tried some kind of backtrack/dp which exceed the time limit loose. At least it was one of the problems with the clearest statement in the contest.

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

    It is similar to SRM 594 Div1 Problem 2 too. http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706&rm=319061&cr=23011413

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

      Yes, it's similar, but it seems like this one can be solved by brute forcing successive depth first search. But it's definitely unfeasible in the case of the problem I posted.

      → Reply