10492 - Optimal Mastermind Strategy

[Robbie]

I've just got this problem AC. But it's running time is approximate 6s.
And I see somebody can solve this problem in <6s, even in 0.002s.
Could sobody tell me your algo to solve this problem faster???

Thanks in advance

[Dmytro Chernysh]

Robbie, you are a lucky person!!! Not everyone can get AC on Jimmy M

[wbodzek]

CORRECTION PROGRAM NEEDS FIXING!!!

I submitted incorrect solution (exactly that was solution for another problem - 10494) and I got ACC. I think that it is an error in special correction problem and requires fixing in near future...

[Adrian Kuegel]

Hi,
I just checked that following program gets Accepted:
int main() {
return 0;
}

I wrote to the admins to fix this (they don't have enough time to read the message board).

[Carlos]

I've just mailed Jimmy Mardell to ask him to check the corrector program. If he doesn't answer, or he can't do it, I'll have to make a new corrector program, and it will take me some time (say, 2 weeks).

[Carlos]

Jimmy Mardell has just mailed us the new corrector program, so we're rejudging every submission. The problem should be solved.

[rage_true]

Hello! Can anyone give me several tests for 10492 with answers? plz.

[..]

I don't have the data on hand now.
But as I know, there should be some cases like this:
in some node of the search tree, you already know that the answer will not be a certain string, say 1234, but you still have to make guess 1234 as it will help you to decrease the height of subtrees.

[Adrian Kuegel]

But as I know, there should be some cases like this:
in some node of the search tree, you already know that the answer will not be a certain string, say 1234, but you still have to make guess 1234 as it will help you to decrease the height of subtrees.

Thanks, I was wondering for a long time why I got WA. Now I got ACC.
This is my output for test case "2 6 0":

Code: Select all

132
12:0,0 34:0,0 55:0,0 66:2,0
12:0,0 34:0,0 55:1,0 56:0,2 65:2,0
12:0,0 34:0,0 55:1,0 56:2,0
12:0,0 34:0,0 55:2,0
12:0,0 34:0,1 45:0,0 63:2,0
12:0,0 34:0,1 45:0,1 53:2,0
12:0,0 34:0,1 45:1,0 46:2,0
12:0,0 34:0,1 45:2,0
12:0,0 34:0,2 43:2,0
12:0,0 34:1,0 35:0,0 44:1,0 64:2,0
12:0,0 34:1,0 35:0,0 44:2,0
12:0,0 34:1,0 35:0,1 54:2,0
12:0,0 34:1,0 35:1,0 33:1,0 36:2,0
12:0,0 34:1,0 35:1,0 33:2,0
12:0,0 34:1,0 35:2,0
12:0,0 34:2,0
12:0,1 23:0,0 41:1,0 51:1,0 61:2,0
12:0,1 23:0,0 41:1,0 51:2,0
12:0,1 23:0,0 41:2,0
12:0,1 23:0,1 31:2,0
12:0,1 23:1,0 24:1,0 25:1,0 26:2,0
12:0,1 23:1,0 24:1,0 25:2,0
12:0,1 23:1,0 24:2,0
12:0,1 23:2,0
12:0,2 21:2,0
12:1,0 34:0,0 15:0,0 22:1,0 62:2,0
12:1,0 34:0,0 15:0,0 22:2,0
12:1,0 34:0,0 15:0,1 52:2,0
12:1,0 34:0,0 15:1,0 11:1,0 16:2,0
12:1,0 34:0,0 15:1,0 11:2,0
12:1,0 34:0,0 15:2,0
12:1,0 34:0,1 13:0,0 42:2,0
12:1,0 34:0,1 13:2,0
12:1,0 34:1,0 14:0,0 32:2,0
12:1,0 34:1,0 14:2,0
12:2,0

before (when I only guessed words that can still be the solution) I got a value of 134.

[..]

Great~~
At first I make the same guess as you and get WA at 2.x s, but after I fix my mistake, my code gets TLE

[Adrian Kuegel]

I got accepted with following assumption: only in first two steps I try all possible guesses, after that I still restrict it to possible solutions like in my WA program. But I also had to optimize my program a lot.

[..]

I got accepted with following assumption: only in first two steps I try all possible guesses, after that I still restrict it to possible solutions like in my WA program.

Thanks Adrain, I get AC with that trick.
By the way......do you think that is some kind of hardcoding?

[Adrian Kuegel]

Yes, it probably is some kind of hardcoding. But hardcoding is not disallowed in ACM regionals/finals (although the judges don't like it), so I consider it a valid solution.