sturdyplum's blog

South Pacific Regional Finals 2017 Problem B: Banner Help
By sturdyplum, history, 6 years ago, In English

I've been working on this problem for a while but can't find an efficient solution. So far my solution runs in about 40 seconds worst case. However the time limit is only 6 seconds. There seems to be no editorial for this contest and it went unsolved during the contest. My solution is bellow. Basically I am doing a backtracking solution that has some amount of memoization, and uses Hungarian matching to do heavy pruning. I was wondering if anyone has solved this problem or could offer some insight to how to solve it. Thank you!

PROBLEM & DATA

MY CODE

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

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Auto comment: topic has been updated by sturdyplum (previous revision, new revision, compare).

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

This explanation may be a bit patchy, since it is purely from memory. I am sure EvgeniSergeev (who wrote this problem), or MathCrusader (who helped to develop it) can give a better explanation.

The idea is to build a graph containing 26 vertices (one for each letter), with the edges weighted by the number of transitions between those characters in the input string. We wish to count the number of optimal TSP-like tours. Doing this the typical way (Held-Karp recursions) will exceed the time limit. Instead, let's search for maximal disjoint path covers. (Since some edges have weight 0, let's ignore them, hence the 'disjoint' part of the path cover.) For clarity, we are looking for all ways of covering all vertices with disjoint paths such that no additional edge could be added--that is, they are maximal. All optimal permutations (of sewing machines) correspond to some permutation of the disjoint paths in a maximal cover. So, if we enumerate all of them, we can find the solution. How do we enumerate them all efficiently? Well, we can do a backtracking search with a heuristic. We will try adding some edges in each recursion, but not just any edges. Find the edge that, when picked, rules out the fewest number of edges. Call the set containing this edge, and the edges it rules out, S. Our backtracking search should try adding each element of S in turn, which causes all other edges in S to be ruled out. It turns out that if we always pick an edge that rules out the fewest number of edges (minimises |S|), we can do an analysis similar to enumerating all maximal independent sets, and get a complexity like O(3|E| / 3|E|). Note that you will also need to deal with issues like accidentally creating loops during the backtracking search.

→ Reply