algorithm - 解决 ACM ICPC - SEERC 2009

Question

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

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

如果有人能给我指明方向，我将不胜感激。我倾向于认为唯一的方法是动态规划，但我似乎无法弄清楚该怎么做。

Answer 1

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

1. 在两个维度上形成一个从 -7 到 7 的 (x,y) 棋盘图数组，并将对手的棋子放在上面。

2. 从第一行开始(最低 Y 值，-N):

   • 枚举该行第二位玩家棋子的所有可能组合，仅消除与对手棋子冲突的组合。

   • 对于此行中的每个组合:--将连接的部分分组到单独的网络中并编号 网络以 1 开始，升序

     --使用以下方法将行编码为向量:

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

     --给每个这样的分组 COUNT 1，并使用编码向量作为其键将其添加到字典/哈希集中

3. 现在，对于每个后续行，按升序 {y=y+1}:

   • 对于前一行字典中的每个条目:

     --如果条目恰好有1组，则将其COUNT加到TOTAL

     --枚举第二位玩家棋子的所有可能组合 在当前行，只删除那些与 对手棋子。 (更改:)您应该跳过初始组合 (其中所有条目均为零)对于此步骤，实际上与上面的步骤一样 覆盖它。对于当前行中的每个这样的组合:

     + 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. 最后，对于最后一行字典中的每个条目:

   • 如果条目只有一组，则将它的 COUNT 添加到 TOTAL

---

**:重新归一化只是意味着重新分配组号，以消除分组模式中的任何排列。具体来说，这意味着新的组号应按递增顺序分配，从左到右，从一个开始。因此，例如，如果您的分组向量在将 ot 分组到上一行之后看起来像这样:

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

它应该被重新映射到这个正常的形式:

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

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

---

好的，一些注意事项:

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

B.虽然很长，但还是很简略的。每个单独的步骤本身都非常重要。

C.虽然有很多单独的优化机会，但整体算法仍然相当复杂。这比蛮力好很多，但即便如此，我的餐巾纸估计仍然在 N=7 的 (2.5 到 10)*10^11 次左右。

所以它可能很容易处理，但距离在 3 秒内完成 74 个案例还有很长的路要走。我还没有阅读 Peter de Revaz 回答的所有细节，但他旋转“钻石”的想法可能适用于我的算法。虽然它会增加内部循环的复杂性，但它可能会降低字典的大小(因此，要比较的分组向量的数量)多达 100 倍，尽管如果不实际尝试它真的很难说.

---

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

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