数学问题：答单选题，结果只有分数不知道每道题对错，问最佳策略（更新码农问题）

#1 - 2022-10-1 09:28

烈之斩 (V1046-R MAHORO)

有10个单选题，每题4个选项。

每次答完题之后可以知道总得分，但是不知道每道题对错

问能最少次数答对所有题的策略

再来个新题，还是上面这些条件，某个人收集了N份答案（和得分），很显然这些答案并不是都是按照最优策略来答的。

现在，请实现一个算法可以自动用收集到答案来推算每道题的答案——能推算出多少算多少 (bgm38)

#2 - 2022-10-1 09:29

你好F8 (整衣正色往南三拜焚琴煮鹤挂印封金 ... ...)

最小作用量？

#3 - 2022-10-1 09:43

夏日勘探者 (家に帰るまでが遠足です)

首先naive的上界是41 (bgm38)

#3-1 - 2022-10-1 09:45

烈之斩

删除了回复

#3-2 - 2022-10-1 10:14

Kane

为什么不是40？每个题试四个答案保持其他题目回答不变，只有一个答案总分比其他三个高一分

#3-3 - 2022-10-1 10:16

夏日勘探者

Kane 说: 为什么不是40？每个题试四个答案保持其他题目回答不变，只有一个答案总分比其他三个高一分

算上了得到正确答案后提交的那次，虽然仔细一想发现不需要。

#3-4 - 2022-10-1 10:35

Kane

夏日勘探者说: 算上了得到正确答案后提交的那次，虽然仔细一想发现不需要。

39，进入最后一题的时候有一个答案已经试过了
按这思路好像还能再减。。。？第一题最坏情况试4次的话，最有一个选项不用试可以进入第二题的环节了
包括这个~40的最坏情况只会发生在第一次全选错的情况，但看到0分可以每题直接排除掉一个错误答案

#3-5 - 2022-10-1 10:48

Kane

Kane 说: 39，进入最后一题的时候有一个答案已经试过了
按这思路好像还能再减。。。？第一题最坏情况试4次的话，最有一个选项不用试可以进入第二题的环节了
包括这个~40的最坏情况只会发生在第一次全选错的情况，但看...

I see是这样。第一次的得分是Ｘ，之后按照这个流程，如果有一题初始答案正确，那么只需要一次尝试(发现分掉了)就可以move on；如果初始答案不正确，需要尝试两次其他答案，如果分都没有涨那剩下没选得就是正确的

这样一共是1 + 2(10-X) + X=21-X，如果算上最后提交的一次那是22-X

题多的话可以优化一下起始的X。上来先答全Ａ全Ｂ全Ｃ全Ｄ，至少一次3分。那么就是4 + 20 - 3 + 1 = 22，和上面最坏情况一样，但题数>>选项的时候应该有用

#3-6 - 2022-10-1 11:03

Blackadder

Kane 说: I see是这样。第一次的得分是Ｘ，之后按照这个流程，如果有一题初始答案正确，那么只需要一次尝试(发现分掉了)就可以move on；如果初始答案不正确，需要尝试两次其他答案，如果分都没有涨那剩下没选得...

只用试全Ａ全Ｂ全Ｃ可知全D，且试出第9题答案时，已可知第10题答案。因此是3+18-3+1=19

#3-7 - 2022-10-1 11:05

Kane

Blackadder 说: 只用试全Ａ全Ｂ全Ｃ可知全D，且试出第9题答案时，已可知第10题答案。因此是3+1+18-3=19

👍

#3-8 - 2022-10-1 11:10

Kane

Blackadder 说: 只用试全Ａ全Ｂ全Ｃ可知全D，且试出第9题答案时，已可知第10题答案。因此是3+18-3+1=19

那还剩两题的时候ABCD里至少两个已经满了可以排除，所以第９题也只要试一次。。

#3-9 - 2022-10-1 11:14

Kane

Kane 说: 那还剩两题的时候ABCD里至少两个已经满了可以排除，所以第９题也只要试一次。。

好像有double count，包括之前的第10题，如果本来就是对的话那就只能-1

#3-10 - 2022-10-1 11:16

Blackadder

Kane 说: 那还剩两题的时候ABCD里至少两个已经满了可以排除，所以第９题也只要试一次。。

全A+全B为4，假设全C为3，将C一个个改为D，最多9次可找出C、D的6个全部位置，剩下4个AB则需要试3次，因此为3+9+3+1=16

#3-11 - 2022-10-1 11:29

Blackadder

Blackadder 说: 全A+全B为4，假设全C为3，将C一个个改为D，最多9次可找出C、D的6个全部位置，剩下4个AB则需要试3次，因此为3+9+3+1=16

2次试出全A+全B为X
X>=5，最多9次可找出A、B的X个全部位置，剩下（10-X）个CD位则需要试（9-X）次，因此为2+9+（9-X）+1=21-X<=16

X<5，10次找出C、D的全部位置，AB试（X-1）次，2+10+（X-1）+1=X+12<=16

#3-12 - 2022-10-1 12:00

Kane

Blackadder 说: 2次试出全A+全B为X
X>=5，最多9次可找出A、B的X个全部位置，剩下（10-X）个CD位则需要试（9-X）次，因此为2+9+（9-X）+1=21-X<=16

X<5，10次找出C、D的全部位置...

把你这思路推广到一般n题m选项（假设n >> m)，就是先试全X，然后从高到低排序组对？这样主部大概是个nm/4的样子。不知道这个1/4的constant是不是最优的

#3-13 - 2022-10-1 12:26

Blackadder

Kane 说: 把你这思路推广到一般n题m选项（假设n >> m)，就是先试全X，然后从高到低排序组对？这样主部大概是个nm/4的样子。不知道这个1/4的constant是不是最优的

不，思路是折半搜索简化成2个n题（m/2）项，在一些情况应该比（m/2）个n题2项快，另n题2项的解法应该有优化空间

#3-14 - 2022-10-1 17:00

烈之斩

删除了回复

#3-15 - 2022-10-1 18:01

烈之斩

Blackadder 说: 2次试出全A+全B为X
X>=5，最多9次可找出A、B的X个全部位置，剩下（10-X）个CD位则需要试（9-X）次，因此为2+9+（9-X）+1=21-X<=16

为啥是9-X次呢？

假设X=8，剩下2个CD位，最差情况要试2次才能知道吧？

(A/B已经找出)
试C,C: 9分
试D,C: 8分

试C,D:过关

比如这题 [3, 4, 1, 2, 1, 2, 1, 2, 1, 2]， X=8，按照你的计算需要21-8=13次，但是实际需要14次：

Attempt #01: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Score: 04 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #02: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] Score: 04 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
A+B count: 8
Attempt #03: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] Score: 04 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #04: [1, 2, 1, 1, 1, 1, 1, 1, 1, 1] Score: 04 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #05: [1, 1, 2, 1, 1, 1, 1, 1, 1, 1] Score: 03 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #06: [1, 1, 1, 2, 1, 1, 1, 1, 1, 1] Score: 05 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #07: [1, 1, 1, 2, 2, 1, 1, 1, 1, 1] Score: 04 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #08: [1, 1, 1, 2, 1, 2, 1, 1, 1, 1] Score: 06 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #09: [1, 1, 1, 2, 1, 2, 2, 1, 1, 1] Score: 05 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #10: [1, 1, 1, 2, 1, 2, 1, 2, 1, 1] Score: 07 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #11: [1, 1, 1, 2, 1, 2, 1, 2, 2, 1] Score: 06 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Tried 9 times to find all A/B answers.
Attempt #12: [3, 3, 1, 2, 1, 2, 1, 2, 1, 2] Score: 09 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #13: [4, 3, 1, 2, 1, 2, 1, 2, 1, 2] Score: 08 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])
Attempt #14: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2] Score: 10 (Solutions: [3, 4, 1, 2, 1, 2, 1, 2, 1, 2])

再比如这道题：

[3, 4, 2, 3, 4, 2, 1, 1, 2, 4]
全A = 2，全B = 3

同样按照这策略，需要17次（我写的算法是测试时会把已知的正确答案带上，便于撞大运；不影响最坏情况结果。）

Attempt #01: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Score: 02 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #02: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #03: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] Score: 02 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #04: [1, 2, 1, 1, 1, 1, 1, 1, 1, 1] Score: 02 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #05: [1, 1, 2, 1, 1, 1, 1, 1, 1, 1] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #06: [1, 1, 2, 2, 1, 1, 1, 1, 1, 1] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #07: [1, 1, 2, 1, 2, 1, 1, 1, 1, 1] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #08: [1, 1, 2, 1, 1, 2, 1, 1, 1, 1] Score: 04 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #09: [1, 1, 2, 1, 1, 2, 2, 1, 1, 1] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #10: [1, 1, 2, 1, 1, 2, 1, 2, 1, 1] Score: 03 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #11: [1, 1, 2, 1, 1, 2, 1, 1, 2, 1] Score: 05 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #12: [3, 3, 2, 3, 3, 2, 1, 1, 2, 3] Score: 07 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #13: [4, 3, 2, 3, 3, 2, 1, 1, 2, 3] Score: 06 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #14: [3, 4, 2, 3, 3, 2, 1, 1, 2, 3] Score: 08 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #15: [3, 4, 2, 4, 3, 2, 1, 1, 2, 3] Score: 07 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #16: [3, 4, 2, 3, 4, 2, 1, 1, 2, 3] Score: 09 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])
Attempt #17: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4] Score: 10 (Solutions: [3, 4, 2, 3, 4, 2, 1, 1, 2, 4])

用上面的策略跑了全部的组合：
Ran 1048576 times, average attempt count: 14.55; max: 17

但是好像A+B<5的情况，真的max=16

source code https://gist.github.com/fireatta ... 535b49a6556b417c68f

另外如果出现例如count(A) =6, count(B)=0的极端情况，不知道有没有更优的处理方式？

#3-16 - 2022-10-1 22:42

Blackadder

烈之斩说: 为啥是9-X次呢？

假设X=8，剩下2个CD位，最差情况要试2次才能知道吧？

(A/B已经找出)
试C,C: 9分
试D,C: 8分

试C,D:过关

比如这题 [3, 4, 1, 2, 1, ...

确实17，我忽略了count(C)的步骤
count(B)=0，可以直接count(C)来与A比对

#3-17 - 2022-10-2 00:52

Blackadder

烈之斩说: 为啥是9-X次呢？

假设X=8，剩下2个CD位，最差情况要试2次才能知道吧？

(A/B已经找出)
试C,C: 9分
试D,C: 8分

试C,D:过关

比如这题 [3, 4, 1, 2, 1, ...

又看了一眼，想到一个16及以下的通解：

先countABC，可得countD，按大小排序为abcd，其中必有a+b=X<5
（按#3-11第二种情况）
9次找出c、d的全部位置，a,b试（X-1）次

3+9+（X-1）+1=X+12<=16

#3-18 - 2022-10-2 01:24

烈之斩

Blackadder 说: 又看了一眼，想到一个16及以下的通解：

先countABC，可得countD，按大小排序为abcd，其中必有a+b=X<5
（按#3-11第二种情况）
9次找出c、d的全部位置，a,b试（X-1）次...

nb, 这个厉害
Ran 1048576 times, average attempt count: 13.9450; max: 16

代码更新到那个gist了

#4 - 2022-10-1 10:10

Kane (この勝利を、近所のおばさんに捧げる！)

你把正确答案1-hot encode成一个40x1的vector，你的回答同理，得分就是dot product，那不就是一个linear design problem

#4-1 - 2022-10-1 10:19

Kane

所以不考虑正确答案的1-hot结构的话，40应该是minimax optimal的。直觉上这结构应该没用。。

#5 - 2022-10-1 10:46

庄生晓梦 (more power!)

我的策略应该不是最优，但也算种思路。
把题简化成2个单选题，每题4个选项。提交答案时依次aa、bb、cc这样提交，然后结果就是两题都错，一对一错和两题都对。两题都错的情况下那就只有dd是正确答案，两题都对可以开始下一组的2个单选题，一对一错时需要循环其中一个答案，比如提交bb时对了1题，接下来就提交bc。这时又会出现两种情况，题1对题2错和题1错题2对，也就是当提交bc分数不变时可以提交bd，提交bc分数为0时应该把循环改为cb和db。

#5-1 - 2022-10-1 10:57

庄生晓梦

---

#5-2 - 2022-10-1 11:01

Kane

庄生晓梦说: 两道题的极端情况的答案是bd，使用我的算法提交过程是aa、ab、ba、bb、bc、bd，即6次。如果两道题使用遍历的话，极端是8次。所以至少比遍历算法要强点。

我上面有个一般的方法，在２题的情况下也是６次

上来随便猜一个答案，之后就每道题试就行了，每题最多试两个不一样的答案就可以确定正确答案，加上最初的一次和最后一次提交，2 + 2n （n是题数）

#5-3 - 2022-10-1 21:48

庄生晓梦

Kane 说: 我上面有个一般的方法，在２题的情况下也是６次

上来随便猜一个答案，之后就每道题试就行了，每题最多试两个不一样的答案就可以确定正确答案，加上最初的一次和最后一次提交，2 + 2n （n是题数）

嗯，如果把我的思路套到10题中，第一组的两题最多只需要提交5次就知道第6次一定是对的，所以第6次可以把第一组的两题按照正确答案提交，同时将第二组的两题开始遍历（假设第一次提交十道题都选a，第二到五组可以都排除掉aa的组合），所以第二到四组只需提交4次就知道本组遍历时的第5次提交一定是对的，最后一组需要提交5次才能完成正确答案的提交，5+4+4+4+5，确实是2 + 2n

#6 - 2022-10-1 10:59

snylonue (表达能力极差)

能不能留一些题不做

#6-1 - 2022-10-1 11:01

烈之斩

不能

#7 - 2022-10-1 11:17

頂上ノ月🌙 (DD雷达搜寻中...?)

先全选a 得出初始分数
然后每题最多再试两遍其他选项去比较总分变化就行了吧(

#7-1 - 2022-10-1 11:19

頂上ノ月🌙

最少次数答对所有题的策略就是一次蒙对全部题x

#8 - 2022-10-1 11:18

Yuan

删除了回复

#9 - 2022-10-1 11:36

伊々若羽

就是破译4进制密码，排列组合费时而已，最多试40次左右。
或者直接偷答案

#9-1 - 2022-10-1 11:49

Kane

密码你得试4^10

#9-2 - 2022-10-1 11:53

伊々若羽

Kane 说: 密码你得试4^10

每个题4个选项试4次，其余题空白，得到全部正确选项也就最多40次。

#9-3 - 2022-10-1 11:56

Kane

伊々若羽说: Kane 说: 密码你得试4^10每个题4个选项试4次，其余题空白，得到全部正确选项也就最多40次。

我的意思是这题的机制和“密码”“排列组合”有本质区别，如果是密码的话需要尝试的次数是指数级的

#10 - 2022-10-1 12:18

幽石堰

删除了回复

#11 - 2022-10-1 13:22

bangumi大西王 (天生万物以养人，人无一物以报天)

感觉我没理解题目，在最简单的只有一道题，或者两道题目的情况下，这个最少次数答对所有题的策略是什么？是针对不同的答案分布下的步数期望最低，还是针对所有答案分布（也就是最差的情况）能唯一确定答案的步数最低，比如我从A开始一个一个试那答案就是D？

#12 - 2022-10-1 13:38

Cedar (｡´-д-)

最少当然是1次因为我运气贼好

#13 - 2022-10-1 13:45

[已注销]

假如我用一些private coin toss把每个题的K个选项都随机打乱（这样problem instance就都变成同一个了），那naive的办法看起来试出单个题的答案的期望次数也在 K/2 + O(1) 里面吧

#14 - 2022-10-1 15:42

自由落体

所有答案全部设为同一个选项即可知道该选项的出现频率，先逐个求出各个选项的出现频率，假如A频率最高，则把全选A的状态设为初始状态，逐题按出现频率从高到低的选项尝试直到全对。
其中，对于每题而言，至少尝试1遍，至多尝试2遍（假设从全选A开始，出现频率从高到低依次为ABCD，第一次尝试选B导致总分下降则确定为A，上升则确定为B，不变则再次尝试选C，第二次尝试若总分上升则确定答案为C，不变则排除ABC选D，故只需试两次）

#14-1 - 2022-10-1 16:01

自由落体

突然想到还能改进

如果已经确定的题目中有某个选项的数量等于其出现频率则可以在接下来的尝试中直接排除这个选项，那接下来的题目只比较一次就够了

#15 - 2022-10-1 16:55

年轮蛋糕 (Bangumi ❤er)

删除了回复

#16 - 2022-10-1 17:21

rock1995 (人生五十年如梦亦如幻有生斯有死壮士何所憾 ... ...)

话说，最佳的评判标准是什么？运气最差的时候也保证能全对的最佳，还是说综合考虑概率因素之后的最佳？两个应该有不一样的设计思路。

#16-1 - 2022-10-1 17:59

烈之斩

都可以

#17 - 2022-10-1 18:55

rock1995 (人生五十年如梦亦如幻有生斯有死壮士何所憾 ... ...)

试任意三种组合，要求每个组合的同一题答案不一样，比如，全选ABC三种。通过这种方式可以获得四种组合的分数。最高分的一组两三个题一次换成第二高的组，用二题三题决于总分，一二组总分至少是六，也就是说要筛出四个错题，一次换两个，保证换的题里错题数数学期望大于0.5，不大于1。观察分数变化，有必要的话再拆一部分有可能的次单独筛查，查出两组的共同错题。最后将错题二分换成第三第四的组……估计，多的话二十次上下？有一些随机应变的空间。
不过我又想了想，任意排列出有6个正确的概率可能是万分之四多？这块只是忘得差不多了，不确实是不是这个数字。这个概率没错的话，试二十次数学期望有一次左右能对六次，实际上如果尽量降低与分数过低的组合的相似度并且提升与分数较高的组合的相似度，数学期望还好看一点，之后再按第一个方法进行的话，估计二十加四五次也会出结果。

感觉好像做过这个题

#18 - 2022-10-1 19:43

Nightwing (SHAFT系動畫小組 →https://bgm.tv/group/shaft)

mark

#19 - 2022-10-2 00:22

烈之斩 (V1046-R MAHORO)

目前采用#3-11策略
最差需要17次（含正确答案提交次数），总体平均 14.5481（忘了加最后提到那个特例优化了）

无论哪个指标能提升都欢迎 (bgm38)

#19-1 - 2022-10-2 01:25

烈之斩

更新：

Ran 1048576 times, average attempt count: 13.9450; max: 16

#20 - 2022-10-2 00:35

Acylation

mark，今早手解了一下三题四选项的优化，现有策略最差6次保证知晓，7次保证作答
不知有无更优

#21 - 2022-10-2 05:20

一起加入一次元！ (如果是无法证明的事情，我会…选择浪漫的一方 ...)

这个和珠玑妙算/mastermind有点像

#22 - 2022-10-2 09:37

徒手开根号二 (nobody cares.)

13
generally, b(p, 4) ≤ p+3
§7 of The number of pessimistic guesses in Generalized Black-peg Mastermind

#23 - 2022-10-5 17:55

Acylation

base
对于更新的算法题的话
答案去重，取最高分的几份答案diff？

#23-1 - 2022-10-6 13:25

烈之斩

我最后直接枚举了，稍微答过几次之后剩余的选项其实就很少了

#23-2 - 2022-10-6 13:30

Acylation

烈之斩说: 我最后直接枚举了，稍微答过几次之后剩余的选项其实就很少了

两个优化思路，一个是以最高分的为基础，找和他相近的比对

还有一种，因为期望得分是2.5，可以想见低分答案比高分答案多很多，可以从低分答案入手，比对排除

比如把所有答0分的倒霉蛋用起来

#23-3 - 2022-10-6 13:32

Acylation

Acylation 说: 两个优化思路，一个是以最高分的为基础，找和他相近的比对

还有一种，因为期望得分是2.5，可以想见低分答案比高分答案多很多，可以从低分答案入手，比对排除

比如把所有答0分的倒霉蛋用起来

再有就是答案数比较好的话可以找找正交对（两两diff = 10），找三份相互正交的答案也有一定的信息量

正交对 + 幸运儿应该可以快速做出来，先用正交对摸出来4列的答案的个数分布，再用高分答案去匹配

#24 - 2022-10-6 12:31

矮木油希希 (都是异端！)

删除了回复

#25 - 2022-10-6 13:00

久远

mark，感觉比我想象总的难 (bgm38)

#26 - 2022-10-6 17:40

NekoNull

听起来是个很有意思的问题 (bgm38)

，完全没有什么思路

Bangumi 番组计划

～技术宅真可怕～ » 讨论
数学问题：答单选题，结果只有分数不知道每道题对错，问最佳策略（更新码农问题）

Bangumi 番组计划

～技术宅真可怕～ » 讨论数学问题：答单选题，结果只有分数不知道每道题对错，问最佳策略（更新码农问题）

～技术宅真可怕～ » 讨论
数学问题：答单选题，结果只有分数不知道每道题对错，问最佳策略（更新码农问题）