Solving ACM ICPC - SEERC 2009

Question

I have been sitting on this for almost a week now. Here is the question in a PDF format.

I could only think of one idea so far but it failed. The idea was to recursively create all connected subgraphs which works in O(num_of_connected_subgraphs), but that is way too slow.

I would really appreciate someone giving my a direction. I'm inclined to think that the only way is dynamic programming but I can't seem to figure out how to do it.

Answer 1

OK, here is a conceptual description for the algorithm that I came up with:

1. Form an array of the (x,y) board map from -7 to 7 in both dimensions and place the opponents pieces on it.

2. Starting with the first row (lowest Y value, -N):

   • enumerate all possible combinations of the 2nd player's pieces on the row, eliminating only those that conflict with the opponents pieces.

   • for each combination on this row: --group connected pieces into separate networks and number these networks starting with 1, ascending

     --encode the row as a vector using:

     = 0 for any unoccupied or opponent position
     = (1-8) for the network group that that piece/position is in.
     

     --give each such grouping a COUNT of 1, and add it to a dictionary/hashset using the encoded vector as its key

3. Now, for each succeeding row, in ascending order {y=y+1}:

   • For every entry in the previous row's dictionary:

     --If the entry has exactly 1 group, add it's COUNT to TOTAL

     --enumerate all possible combinations of the 2nd player's pieces on the current row, eliminating only those that conflict with the opponents pieces. (change:) you should skip the initial combination (where all entries are zero) for this step, as the step above actually covers it. For each such combination on the current row:

     + produce a grouping vector as described above
     
     + compare the current row's group-vector to the previous row's 
       group-vector from the dictionary:
     
         ++ if there are any group-*numbers* from the previous row's 
           vector that are not adjacent to any gorups in the current
           row's vector, *for at least one value of X*, then skip 
           to the next combination.
     
         ++ any groups for the current row that are adjacent to any
           groups of the previous row, acquire the lowest such group
           number
     
         ++ any groups for the current row that are not adjacent to 
           any groups of the previous row, are assigned an unused
           group number
     
     + Re-Normalize the group-number assignments for the current-row's
       combination (**) and encode the vector, giving it a COUNT equal 
       to the previous row-vector's COUNT
     
     + Add the current-row's vector to the dictionary for the current
       Row, using its encoded vector as the key.  If it already exists,
       then add it's COUNT to the COUNT for the pre-exising entry
     

4. Finally, for every entry in the dictionary for the last row:

   • If the entry has exactly one group, then add it's COUNT to TOTAL

---

**: Re-Normalizing simply means to re-assign the group numbers so as to eliminate any permutations in the grouping pattern. Specifically, this means that new group numbers should be assigned in increasing order, from left-to-right, starting from one. So for example, if your grouping vector looked like this after grouping ot to the previous row:

2 0 5 5 0 3 0 5 0 7 ...

it should be re-mapped to this normal form:

1 0 2 2 0 3 0 2 0 4 ...

Note that as in this example, after the first row, the groupings can be discontiguous. This relationship must be preserved, so the two groups of "5"s are re-mapped to the same number ("2") in the re-normalization.

---

OK, a couple of notes:

A. I think that this approach is correct , but I I am really not certain, so it will definitely need some vetting, etc.

B. Although it is long, it's still pretty sketchy. Each individual step is non-trivial in itself.

C. Although there are plenty of individual optimization opportunities, the overall algorithm is still pretty complicated. It is a lot better than brute-force, but even so, my back-of-the-napkin estimate is still around (2.5 to 10)*10^11 operations for N=7.

So it's probably tractable, but still a long way off from doing 74 cases in 3 seconds. I haven't read all of the detail for Peter de Revaz's answer, but his idea of rotating the "diamond" might be workable for my algorithm. Although it would increase the complexity of the inner loop, it may drop the size of the dictionaries (and thus, the number of grouping-vectors to compare against) by as much as a 100x, though it's really hard to tell without actually trying it.

---

Note also that there isn't any dynamic programming here. I couldn't come up with an easy way to leverage it, so that might still be an avenue for improvement.

OK, I enumerated all possible valid grouping-vectors to get a better estimate of (C) above, which lowered it to O(3.5*10^9) for N=7. That's much better, but still about an order of magnitude over what you probably need to finish 74 tests in 3 seconds. That does depend on the tests though, if most of them are smaller than N=7, it might be able to make it.

Answer 2

Here is a rough sketch of an approach for this problem.

First note that the lattice points need |x|+|y| < N, which results in a diamond shape going from coordinates 0,6 to 6,0 i.e. with 7 points on each side.

If you imagine rotating this diamond by 45 degrees, you will end up with a 7*7 square lattice which may be easier to think about. (Although note that there are also intermediate 6 high columns.)

For example, for N=3 the original lattice points are:

..A..
.BCD.
EFGHI
.JKL.
..M..

Which rotate to

A   D   I
  C   H
B   G   L
  F   K
E   J   M

On the (possibly rotated) lattice I would attempt to solve by dynamic programming the problem of counting the number of ways of placing armies in the first x columns such that the last column is a certain string (plus a boolean flag to say whether some points have been placed yet).

The string contains a digit for each lattice point.

0 represents an empty location
1 represents an isolated point
2 represents the first of a new connected group
3 represents an intermediate in a connected group
4 represents the last in an connected group

During the algorithm the strings can represent shapes containing multiple connected groups, but we reject any transformations that leave an orphaned connected group.

When you have placed all columns you need to only count strings which have at most one connected group.

For example, the string for the first 5 columns of the shape below is:

....+  = 2
..+++  = 3
..+..  = 0
..+.+  = 1
..+..  = 0
..+++  = 3
..+++  = 4

The middle + is currently unconnected, but may become connected by a later column so still needs to be tracked. (In this diagram I am also assuming a up/down/left/right 4-connectivity. The rotated lattice should really use a diagonal connectivity but I find that a bit harder to visualise and I am not entirely sure it is still a valid approach with this connectivity.)

I appreciate that this answer is not complete (and could do with lots more pictures/explanation), but perhaps it will prompt someone else to provide a more complete solution.