All geek questions in one place

Algorithm for solving the problem with Google Jam Tutorial C

I would like to understand the algorithm that solves Google Code Jam, Tutorial, Problem C. So far, I have written my own basic implementation , which solves a small problem. I found that he is unable to cope with a big problem (complexity O (min (n, 2 * k) !, Which is 30! In a larger dataset).

I found this page, but the solutions, of course, are not documented (there is a time limit for the context). I saw that at least one of the solutions used the Union Find structure, but I do not understand how it is applied here.

Does anyone know a page with algorithms that solve these problems, not just code?

+4
source share
3 answers

Not sure if there is a better way to handle this close duplicate of GCJ - Hamiltonian loops , but here is my answer from there:

The O (2 k ) -based solution uses the inclusion exclusion principle . Given that there are forbidden edges k , there are subsets of 2 k of these edges, including the set itself and the empty set. For example, if there were 3 forbidden edges: {A, B, C}, there would be 2 3 = 8 subsets: {}, {A}, {B}, {C}, {A, B}, {A, C }, {B, C}, {A, B, C}.

For each subset, you calculate the number of loops that include at least all the edges in that subset. If the number of cycles containing edges s , f (s) , and S is the set of all forbidden edges, then by inclusion and exclusion the principle is the number of cycles without any forbidden edges:

sum, for each subset s of S: f(s) * (-1)^|s|

where | s | is the number of elements in s . In other words, the sum of the number of cycles with any edges minus the number of cycles with at least 1 forbidden edge plus the number with at least two forbidden edges, ...

Computing f (s) is not trivial - at least I have not found an easy way to do this. You can stop and ponder this before reading further.

To compute f (s) , start with the number of permutations of nodes that are not related to nodes s . If there are m such nodes, then m ! permutations, as you know. Call the number of permutations c .

Now consider the edges in s for chains. If there are any impossible combinations, such as node, associated with 3 edges or a subcycle inside s , then f (s) is 0.

Otherwise, for each increment of the chain m by 1 and multiply c by 2m . (There are places m to put the chain into existing permutations, and the coefficient 2 is because the chain can be directed forward or backward.) Finally, f (s) with / ( 2m ). The last division converts permutations into loops.

+1
source

An important limit imposed on the input is that the number of forbidden edges is k <= 15.

You can continue to include and exclude:

  • calculate the number of all cycles ((n-1)!),
  • for each forbidden edge e, subtract the number of cycles that contain it ((n-2)! / 2 if n is not very small),
  • for each pair of forbidden edges e, f, add the number of loops containing both of them (this will depend on whether e and f touch)
  • for every triple ..., substract ...,
  • etc..

Since there are only 2 ^ k <= 32768 subsets of F (the set of all forbidden edges), you get a reasonable estimate of the runtime.

An analysis of a problem with a bug in Google Endless Knight code uses a similar idea.

0
source

The Hamiltonian cycle problem is a special case of the traveling salesman problem (obtained by establishing the distance between two cities to a finite constant if they are adjacent and infinity otherwise).

This is NP Complete problems, which in simple words mean a quick fix that they do n’t know .

To solve questions about the Google Code Jam, you should know Algorimths Analysis and Design, although they can be solved exponentially, and don’t worry that Google knows this very well.;)

To get started, the following sources should be enough for you:

0
source

Source: https://habr.com/ru/post/1335580/

More articles:


All Articles