10492 - Optimal Mastermind Strategy

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

10492 - Optimal Mastermind Strategy

Post by 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
GGG

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh »

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

wbodzek
New poster
Posts: 1
Joined: Sun Oct 17, 2004 6:02 pm

CORRECTION PROGRAM NEEDS FIXING!!!

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by 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
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos »

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

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

10492 Some Tests and Answers

Post by rage_true »

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Great~~ :D
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 :(
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Adrian Kuegel wrote: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? :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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.

Post Reply

Return to “Volume 104 (10400-10499)”