wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Forcing a test
        
(Message started by: Leonid Broukhis on Feb 3rd, 2009, 4:52pm)
Title: Forcing a test
Post by Leonid Broukhis on Feb 3rd, 2009, 4:52pm
This is a puzzle offered at last Fall's Russian "Tournament of Cities" with a variation by me.

Original:
There is a 30-question online test with "true/false" answers. Submitting it (all questions must be answered) yields a score - the number of correct answers. You don't know the topic of the test at all; you can only guess.

a) Can you guarantee yourself a score of 30 at the 30th attempt?
b) At the 25th attempt?
c) At some Nth (N < 25) attempt?
d*) What is the min. N for which it is possible?

Variation: A written test (30 true/false questions) is administered on two days with the same answer key; the scores are known at the end of the day. A test sheet is not scored unless all 30 questions are answered. How many proxies do you need to send the first day to fill out the test to be able to get a score of 30 the next day?
Title: Re: Forcing a test
Post by towr on Feb 4th, 2009, 2:17am
I can do the variation with 29 30, and so also a).
I'll have to think more about how to improve on it.

[edit]I think I miscounted, and my method gives 30, rather than 29. Which unfortunately means I can't get it right on the 30th attempt.[/edit]
Title: Re: Forcing a test
Post by towr on Feb 4th, 2009, 6:01am
I think I can do the original in [hide]21+1[/hide], and it may still be improved. [hide]I used the ID3 decision tree algorithm, for 10 questions the tree has a depth of 7 to find out which questions are right. Splitting the questions into 3 groups doesn't seem to actually cost you an attempt.[/hide]

[e]Shaved off one more attempt [hide]by splitting in 2 x 11 + 8, which tells you the correct answers in 20 tries, so you get it right on the 21th.[/hide] And due to computational limitations that's as far as my current approach can bring me.[/e]
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 4th, 2009, 8:48am
Thanks, towr! I did not know about the [hide]decision tree[/hide] algorithms before. My first idea - [hide]to do a binary search[/hide] - happened to solve b).
[hide] Is your solution 2 x 11 + 8 due to the fact that 30/e = 11?[/hide]
Title: Re: Forcing a test
Post by towr on Feb 4th, 2009, 9:36am

on 02/04/09 at 08:48:13, Leo Broukhis wrote:
Thanks, towr! I did not know about the [hide]decision tree[/hide] algorithms before.
The problem is that it doesn't give very nice solutions. It's a long list of "if this than that else if this", etc


Quote:
My first idea - [hide]to do a binary search[/hide] - happened to solve b).
I tried something similar, but only got to 31. :-/
Could you elaborate on how you get to 25?


Quote:
[hide] Is your solution 2 x 11 + 8 due to the fact that 30/e = 11?[/hide]
I wouldn't dare say. It's just the limit of what my computer could handle calculating. So it's more likely a coincidence.
I think you can probably do better. And the ID3 algorithm doesn't necessarily give the shallowest decision tree in the first place (it's heuristic).

Here's my list of how many attempts you need to find the correct list of answers:

[hide]N   tries
1 - 1
2 - 2
3 - 3
4 - 4
5 - 4
6 - 5
7 - 6
8 - 6
9 - 7  
10 - 7
11 - 7
12 - 8
[edit] using leo's program
13 - 8
14 - 9
15 - 9
[/edit]
[/hide]

So I'd expect more savings later on. But the way I compute it each next step takes 4 times as much memory, and I hit 44% already.
For example it seems in line with the pattern that [hide]15 would only take 9[/hide], which means you can do it in [hide]18[/hide] attempts or less. But I'd need a more clever way to calculate it to confirm this suspicion. (Or wait for SMQ to inevitably set his teeth into it ;) )
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 4th, 2009, 11:09am

on 02/04/09 at 09:36:20, towr wrote:
Could you elaborate on how you get to 25?


Sorry, I miscalculated. Binary search solves a).
Title: Re: Forcing a test
Post by Hippo on Feb 4th, 2009, 11:18am
It seems to me it should do something with theory of codes.
(At least the variant with filling all tests at once).

Lower bound seems to be eight ... as 157<230 and inverse test gives the same information.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 4th, 2009, 12:00pm

on 02/04/09 at 11:18:19, Hippo wrote:
It seems to me it should do something with theory of codes.
(At least the variant with filling all tests at once).
I've guessed as much.

Quote:
Lower bound seems to be eight ... as 157<230 and inverse test gives the same information.

According to my calculations, the least information of a popcount of a 30-bit vector is 2.79 bits (when you get 15), therefore the lower bound is 11.
Title: Re: Forcing a test
Post by towr on Feb 4th, 2009, 12:03pm
[e] I = too slow [/e]


on 02/04/09 at 11:18:19, Hippo wrote:
Lower bound seems to be eight ... as 157<230 and inverse test gives the same information.
You never get lg(15)=3.9 bits of information out of a test. At best it's lg(230/C(30,15)) ~= 2.79 So you need at minimum 11 tests. And you get increasingly less new information from a test, since it overlaps.
Title: Re: Forcing a test
Post by Hippo on Feb 4th, 2009, 2:11pm

on 02/04/09 at 12:03:41, towr wrote:
[e] I = too slow [/e]

You never get lg(15)=3.9 bits of information out of a test. At best it's lg(230/C(30,15)) ~= 2.79 So you need at minimum 11 tests. And you get increasingly less new information from a test, since it overlaps.


Of course it was not tight lower bound ;).
I am not sure with the test dependency ... at least parity is fixed so you can avoid result 15.
So may be lg(230/C(30,14))?
Title: Re: Forcing a test
Post by towr on Feb 5th, 2009, 1:55am
For the variation, splitting into 3 x 10 gives the same number of tries as the original [hide]21 attempts to find the answer key

For 10, here is one possible list of patterns that can be used
0000000000 - 0
0000011111 - 31
0001100011 - 99
0011010101 - 213
0100100101 - 293
0010111011 - 187
0000000110 - 6
(They're in the order in which the heuristic of maximum local information gain gave them)[/hide]

Same disclaimer as before applies: ID3 isn't guaranteed to be optimal, and in any case the split may not be optimal.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 5th, 2009, 11:30am

on 02/05/09 at 01:55:50, towr wrote:
For the variation, splitting into 3 x 10 gives the same number of tries as the original [hide]21 attempts to find the answer key[/hide]


While it is easy to see how the cost of the first attempt is saved in case of splitting in the "online" version, I don't understand how that works in this case, i.e. how do you replicate the patterns for a multiple of n?
Title: Re: Forcing a test
Post by towr on Feb 5th, 2009, 11:53am

on 02/05/09 at 11:30:58, Leo Broukhis wrote:
While it is easy to see how the cost of the first attempt is saved in case of splitting in the "online" version, I don't understand how that works in this case, i.e. how do you replicate the patterns for a multiple of n?
You can start with a 'baseline' of answering "true" to everything. And then each pattern of n (except the last) is run independently, i.e. only changing those n questions, leaving the rest "true". For the last block of n, you can skip the first test, because you know how many true answers there are in total and how many there are in the first (k-1) blocks and therefore know the result of the first test.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 5th, 2009, 12:11pm
:-[ Thank you. Sometimes thinking parallel is bad.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 5th, 2009, 4:46pm
towr,

my minimax algorithm gives 10 for n=15.

my max inf. gain algorithm gives 9 for n=15  ;D
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 5th, 2009, 9:09pm
I was not able to find a 9-element static set for n=15.
The best 10-element set is
[hide]0
127
1927
6553
10922
14659
6884
5993
14387
1[/hide]
Where the last probe is needed to disambiguate 24 pairs.
Title: Re: Forcing a test
Post by towr on Feb 6th, 2009, 12:01am

on 02/05/09 at 16:46:22, Leo Broukhis wrote:
towr,

my minimax algorithm gives 10 for n=15.

my max inf. gain algorithm gives 9 for n=15  ;D
Could you share the algorithm?
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 6th, 2009, 1:07am
Oh well, as they say, please excuse our dust.
Hope that the attachment works.
Title: Re: Forcing a test
Post by towr on Feb 6th, 2009, 1:25am
It performs a lot better than my program, albeit in part because it's c++ rather than python. You can get a little bit improvement by using a different bitcounting technique*, it shaves about 5% off.

* http://www.cs.utk.edu/~vose/c-stuff/bithacks.html#CountBitsSetParallel
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 6th, 2009, 1:45am
Sure, I just didn't bother typing it. The data structure to improve is the set; vector helps but not by much. A sparse bitmap should work well.
Another big improvement would be to only test pivots whose bits are proper subsets of the OR of the values within a group (as all other bits won't affect the result; HAKMEM should have a fast function to iterate over all subsets of a bitset somewhere) This should make it O(n log n) rather than O(n^2) and, in conjunction with the sparse bitmap, will allow to run the algorithm for n=30 in a reasonable time.
Title: Re: Forcing a test
Post by towr on Feb 6th, 2009, 2:16am

on 02/06/09 at 01:45:54, Leo Broukhis wrote:
Another big improvement would be to only test pivots whose bits are proper subsets of the OR of the values within a group (as all other bits won't affect the result; HAKMEM should have a fast function to iterate over all subsets of a bitset somewhere)
It seems to save about half to check pivot & group_or == pivot.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 6th, 2009, 5:18pm
Further, the pivot values that have 0 where the whole group has 1 can be filtered as well.
Title: Re: Forcing a test
Post by towr on Feb 13th, 2009, 3:42am
I've tried a new approach with comes pretty close to log-linear runtime (in the number of numbers). Unfortunately it doesn't give quite as good results.
To find a pivot, what I do is first find the best bit, the find the bit I can best add to that, etc until I have the best pivot that I can find in that way. This takes around O(#bits2). Which means the total is O(2#bits * #bits2)

Here's a list of my results so far:
#bits : max steps
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 6
8 : 7
9 : 7
10 : 8
11 : 8
12 : 9
13 : 9
14 : 10
15 : 11
16 : 11
17 : 12
18 : 12
19 : 13
20 : 14
21 : 14
22 : 15
23 : 15
24 : 16
25 : 16
26 : 17
27 : 17

So generally it's a bit worse than the previous algorithm, but it's much faster. And I have some ideas on how to maybe improve performance.
Title: Re: Forcing a test
Post by Leo Broukhis on Feb 13th, 2009, 9:04am
towr,
I have a feeling that your algorithm will do no better than the result achieved by splitting the bit vector in smaller pieces. Consider 11 that it gives for 15: the best splitting is 10 and 5 using 7 and 4 steps (using the original algorithm). Or 17 that it gives for 27: that's 8 + 9 for pieces of sizes 13 and 14.
Title: Re: Forcing a test
Post by towr on Feb 13th, 2009, 11:31am

on 02/13/09 at 09:04:11, Leo Broukhis wrote:
I have a feeling that your algorithm will do no better than the result achieved by splitting the bit vector in smaller pieces.
Without an improvement to the heuristics, I'd have to agree. But I don't think the approach is necessarily a lost cause and beyond improvement.

For example there is room to reuse the previous better results. If not all the bits of the numbers in a group change (staying either 0 or 1 for all), then you can remove them from the number, and so reduce it to a problem of less complexity.
And one might do better by not searching for the best improvement locally, but for example consider the next step as well.
Title: Re: Forcing a test
Post by Azgard on Feb 16th, 2009, 8:26am
I don't suppose that when scoring the test they tell you which questions were answered correctly and which were not...? Because that would make scoring perfect on the test attainable on the second try!

Then again, if that were the solution, the question would not be in the "Hard" section of the forum...
Title: Re: Forcing a test
Post by Leo Broukhis on Mar 4th, 2009, 11:29am
I know a solution (verified by an exhaustive test) for 30 questions that uses 16 probes:  
16730
4701400
7718455
7880704
8010479
8534452
26199916
29343619
43779229
110902898
260266666
262217797
526377246
526432041
528341489
534958022
(obviously, the first probe can be made 0 by xoring everything by 16730, but that's how it was sent to me).
Here's how it has been found: [hide]by manually constructing a set of 30 N-dimensional vectors with coordinates equal to 1 or -1 which partial sums are all distinct. It was done in a spreadsheet.[/hide]
Title: Re: Forcing a test
Post by Leo Broukhis on Mar 5th, 2009, 9:46am
A small program implementing the algorithm above has found a (verified) solution of 8 probes for 13 questions:
0
4478
3646
3038
5262
2038
6370
7936

This solution can be extended to 9 probes for 15 questions:
0
4478
3646
3038
5262
2038
6370
7937 <-- NB the low bit set
10218

The algorithm claims that 16 probes can resolve up to 33 (!) questions.
Title: Re: Forcing a test
Post by towr on Mar 5th, 2009, 10:38am
Impressive.
Title: Re: Forcing a test
Post by Leo Broukhis on Mar 12th, 2009, 6:44pm
My collaborator on this problem has observed the similarity of what we're trying to find with Hadamard matrices. Indeed, the solutions for 8 and 16 probes include the matrices as subsets. As there exist a Hadamard matrix of order 12, I was able to construct a solution for 20 questions using the matrix as the basis, and then to extend it to 21 questions (losing the Hadamard property, so it remains unclear how to search for the maximal vector set).
A good approximation to the max number of questions that can be solved by N probes is given by A000788(N-1)+1 - but a solution mentioned above of 9 probes for 15 questions stands out.
More things to discover...


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board