データ構造と検索

またトップコーダーオープンのアルゴリズム問題に苦しんでいる。　今回壁を行と列に置かなければいけません。しかし隙間を分裂する問題もある。羊とオオカミの間に置く。しかし順番の問題があります。ギャップに壁を置く前にギャップを並べ替えるのが必要かどうかと言う事が不明です。残念ながらデータの順番や計算式の複雑性よりプログラムの正しさがとりあえず問題になっています。オオカミが一つな行か列にまっすぐ動く場合に大丈夫ですが縦も横も可能です。だから壁がオオカミと羊を分裂しなければいけません。こちらのアルゴリズムがこの所に足りません。　The logic of my algorithm does not consider the possiblity of horizontal moves followed by vertical moves by the wolves to reach the sheep and thus does not correctly separate them. Thus, in many cases, the code outputs a value which underestimates the minimal number of walls necessary.
正解は以外な方法です。横の壁の置き方を全て見て最適な縦の置き方を探す訳です。Each row placement is considered to be a binary tuple, and this tuple is converted to an integer vector. Then for a given row placement, columns are placed such that each additional column placed is set as far to the right as possible. This is done by checking that, for a given region right of the current rightmost column and between the two row fences consecutively placed, no wolf and sheep exist. The data structure used to ensure that checking can be done efficiently is a pair of maps mapping index of the row fences vector to the number of wolves and sheep. This pair of maps is reset each time a new vertical wall is placed (the left boundary moves).
Thus, the total complexity of the algorithm is O*1 = O(2^(R-1)*C*R) <= O(2^15*256)=O(2^23)=O(8000000), which is computationally tractable.
Strangely, even after I implement an algorithm in this fashion, I cannot obtain the correct answer. Many test cases passed after I updated the code to pass the index in the row vector to use as the key in the memorization of wolf and sheep counts, but a 16 by 7 case is still failing. This problem was remedied by introducing logic to check the validity of a row placement(ie whether no column between row walls contains a wolf and sheep), as otherwise illegal row placements would be accepted. Lastly, the edge case of a field of one column needed to be handled by checking validity of the row placement (without placing any vertical walls).

*1:number of row placements) * (number of vertical wall placements per row placement) * (cost of vertical wall placement