algorithm - 查找缺失的排列

Question

这个问题是谷歌在最近的 codejam 回合中提出的，它仍然困扰着我，我是如何设法解决它的。请告诉我怎么做:

Go, go, Power Arrangers! Everyone loves this team of five superhero high school students who wear the letters A, B, C, D, and E. When they stand side by side to confront evil monsters, they arrange their team in one of 120 possible different left-to-right orders, giving them various different tactical superpowers. They are even more popular than the Teenage Permutant Ninja Turtles!

Some critics of the show claim that the team only has its arrangment gimmick so that the owners of the show can sell 120 separate sets of 5 action figures, each of which features the team in a different left-to-right order, glued to a base so that the set cannot be rearranged. As an avid Power Arrangers fan, you have collected 119 of these sets, but you do not remember which set you are missing. Your 119 sets are lined up horizontally along a shelf, such that there are a total of 119 × 5 = 595 action figures in left-to-right order. You do not remember how the sets are arranged, but you know that the permutation of the sets is selected uniformly at random from all possible permutations, and independently for each case.

You do not want to waste any time figuring out which set you are missing, so you plan to look at the letters on at most F figures on the shelf. For instance, you might choose to look at the letter on the eighth figure from the left, which would be the third figure from the left in the second set from the left. When looking at a figure, you only get the letter from that one figure; the letters are hard to see, and the different team members look very similar otherwise!

After checking at most F figures, you must figure out which of the sets is missing, so you can complete your collection and be ready to face any possible evil threat!

Input and output

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing two integers T, the number of test cases, and F, the number of figures you are allowed to inspect per test case. Then, you need to process T test cases.

Within each test case, the missing set of figures is chosen uniformly at random from all possible sets, and the order of the remaining sets is chosen uniformly at random from all possible orders as well. Every choice is made independently of all other choices and of your inputs.

In each test case, your program will process up to F + 1 exchanges with our judge. You may make up to F exchanges of the following form:

• Your program outputs one line containing a single integer between 1 and 595, inclusive, indicating which figure (in left-to-right order along the shelf) you wish to look at. As a further example, 589 would represent the fourth figure from the left in the second set from the right.
• The judge responds with one line containing a single uppercase letter A, B, C, D, or E, indicating the letter on that figure. If you sent invalid data (e.g., a number out of range, or a malformed line), the judge will instead respond with one line containing the single uppercase letter N.

Then, after you have made as many of the F exchanges above as you want, you must make one more exchange of the following form:

• Your program outputs one line containing a single string of five uppercase letters: the permutation corresponding to the missing set (e.g., CADBE).
• The judge responds with one line containing a single uppercase letter: Y if your answer was correct, and N if it was not (or you provided a malformed line). If you receive Y, you should begin the next test case, or stop sending input if there are no more test cases.

After the judge sends N to your input stream (because of either invalid data or an incorrect answer), it will not send any other output. If your program continues to wait for the judge after receiving N, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment. Limits

1 ≤ T ≤ 50. Time limit: 40 seconds per test set. Memory limit: 1GB. The missing set, and the order of the remaining sets, are chosen uniformly and independently at random. Test set 1 (Visible)

F = 475. Test set 2 (Hidden)

F = 150.

Answer 1

你可以尝试这样的事情:

• 使用您的前 119 个查询来查询每个“ block ”的第一个元素，即第 0、5、10 等元素
• 计算您找到每个字母的频率和位置；每个首字母应该有 24 种排列，但对于一个只有 23 种排列
• 继续这 23 个排列并查询这些 block 的第二个字母，例如如果它们的起始位置是15,40,60,...,查询第16,41,61,...字母
• 再次计算您找到第二个字母的频率；每个字母应该有 6 个，但一个字母只有 5 个
• 继续那 5 个并查询其中的第 3 个字母；对于其中之一，只有一个排列而不是两个
• 现在您知道缺失排列的前三个字母；使用上一步中相同的前三位数字对该单个排列的第四(或第五)个字母进行最终查询，您可以推断出缺失排列的最后两位数字

这样，您将需要 119 + 23 + 5 + 1 = 148 次查询才能找到缺失的排列。

Python 中的示例实现:

import itertools, random, collections
permutations = list(itertools.permutations("ABCDE"))
random.shuffle(permutations)
permutations.pop()
flat_permutations = [c for p in permutations for c in p]

queries = 0
candidates = [i * 5 for i in range(119)]
missing = ""
for i in [0, 1, 2, 4]:
    where = collections.defaultdict(list)
    for t in candidates:
        queries += 1
        c = flat_permutations[t + i]
        where[c].append(t)
    c, candidates = min(where.items(), key=lambda item: len(item[1]))
    missing += c

# we queried for the 5th and used it as 4th in 'missing'
missing += next(c for c in "ABCDE" if c not in missing)

print("queries", queries)
print("missing", missing)
print("correct?", tuple(missing) not in permutations)

这将总是找到丢失的排列，但它也将总是¹⁾进行 148 次查询。

如果 F 较小，您可能只查询随机位置，然后使用概率来猜测最不符合这些猜测的排列。

---

¹⁾ 从技术上讲，您可以用更少的查询找到它，例如如果您非常幸运，在 100 次查询之后您已经有 4 个字母，每个字母有 24 个位置，那么您不需要进行最后 19 次查询，但这纯属运气，而且这种机会相当渺茫。