解决ACM ICPC - SEERC 2009

Question

我已经在这上面坐了将近一个星期了。Here是一个PDF格式的问题。

到目前为止，我只能想到一个想法，但它失败了。这个想法是递归地创建所有连通子图，它在O(num_of_connected_subgraphs)中工作，但这太慢了。

如果有人能给我指点方向，我会非常感激。我倾向于认为唯一的方法是动态编程，但我似乎不知道如何做到这一点。

Answer 1

好的，这是我提出的算法的概念性描述：

1. 在两个维度上形成一个从-7到7的(x，y)板映射数组，并将对手的棋子放在上面。
2. 从第一行(最低Y值，-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

--使用以下命令将行编码为向量：

=0对于任何未占用或对手位置= (1-8)对于该棋子/位置所在的网络组。

--给每个这样的分组一个计数1，并使用编码的向量作为它的关键字将它添加到字典/哈希集

​

1. Now，对于随后的每一行，按升序{y=y+1}:

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

--如果条目恰好有一个组，则将其计数添加到总数中

--枚举当前行中第二个玩家的棋子的所有可能组合，只排除那些与对手棋子冲突的棋子。(change:)您应该跳过此步骤的初始组合(其中所有条目都为零)，因为上面的步骤实际上涵盖了它。对于当前行上的每个这样的组合：

• 如上所述生成一个分组向量+将当前行的组向量与字典中的前一行的组向量进行比较：++如果前一行的向量中有任何group-*数字*与当前行的向量中的任何都不相邻，*对于X*的至少一个值，则跳到下一个组合。对与前一行的任何组相邻的当前行的任何组进行计数，获取与前一行的任何组不相邻的当前行的任何组的最低组号，分配未使用的组号+重新归一化当前行的组合(**)的组号分配，并对向量进行编码，给出等于前一行向量的计数+使用当前行的编码向量作为关键字，将当前行的向量添加到当前行的字典中。如果它已经存在，则将它的计数添加到

的预存现项的计数中

​

1. 最后，对于字典中最后一行的每个条目：

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

​

**：重新归一化只是指重新分配分组编号，以消除分组模式中的任何排列。具体地说，这意味着新的组号应该按从左到右的递增顺序分配，从1开始。因此，例如，如果您的分组向量在将ot分组到前一行后如下所示：

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

它应该重新映射到这个范式：

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

请注意，如本例所示，在第一行之后，分组可以是不连续的。这种关系必须保留，因此在重新规范化中，两组“5”被重新映射为相同的数字("2")。

好的，有几个注意事项：

答:我认为这种方法是正确的，但我我真的不确定，所以它肯定需要一些审查，等等。

虽然它很长，但仍然相当粗略。每一步本身都不是微不足道的。

C.虽然有大量的个体优化机会，但整体算法仍然相当复杂。这比暴力破解要好得多，但即便如此，我对N=7的粗略估计仍然是(2.5到10)*10^11次操作。

因此，这可能是容易处理的，但距离在3秒内完成74个案例还有很长的路要走。我还没有读过Peter de Revaz回答的所有细节，但他旋转“菱形”的想法可能对我的算法是可行的。虽然这会增加内部循环的复杂性，但它可能会将字典的大小(以及要比较的分组向量的数量)减少100倍，尽管不实际尝试就很难判断。

还要注意的是，这里没有任何动态编程。我不能想出一个简单的方法来利用它，所以这可能仍然是一个改进的途径。

好了，我列举了所有可能的有效分组向量，以得到上面(C)的更好的估计，这使得N=7的估计值降低到O(3.5x10^9)，这要好得多，但仍然比你在3秒内完成74个测试所需的值高出一个数量级。不过，这取决于测试，如果它们中的大多数都比N=7小，它可能会成功。

Answer 2

以下是解决此问题的一种方法的粗略草图。

首先请注意，晶格点需要|x|+|y| < N，这会导致菱形形状从坐标0,6到6,0，即每个边都有7个点。

如果你想象将这个菱形旋转45度，你最终会得到一个7*7正方形的格子，这可能更容易理解。(但请注意，也有中间6个高列。)

例如，对于N=3，原始晶格点为：

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

它旋转到

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

在(可能是旋转的)格子上，我会尝试通过动态编程来解决在前x列中放置军队的方式的计数问题，使得最后一列是某个字符串(加上一个布尔标志来说明是否已经放置了一些点)。

该字符串包含每个晶格点的一个数字。

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

在算法过程中，字符串可以表示包含多个连通组的形状，但我们拒绝任何离开孤立的连通组的转换。

放置完所有列后，只需计算最多有一个连接组的字符串。

例如，下面形状的前5列的字符串为：

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

中间的+当前未连接，但可能会被稍后的列连接，因此仍需要跟踪。(在此图中，我还假设了向上/向下/向左/向右4-连接。旋转网格确实应该使用对角连接，但我发现这有点难以想象，而且我不完全确定它是否仍然是这种连接的有效方法。)

我理解这个答案并不完整(并且可以用更多的图片/解释)，但也许它会促使其他人提供更完整的解决方案。