4408

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

4408

Post by f74956227 » Tue Mar 31, 2009 2:36 pm

Can someone tell me how to solve this problem with the correct algorithm? I saw many people solve this problem,
but i have no idea with it. Please help me orz...
electron

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 4408

Post by helloneo » Tue Mar 31, 2009 4:59 pm

I solved it with BFS :-)

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 4408

Post by f74956227 » Tue Mar 31, 2009 11:42 pm

Hi! Could you explain it clearly? I has a bottleneck in how to check the halting condition...because such as the third test case
5234 -> 1212, should i check 5234 -> 11212 -> 21212 -> 31212 -> ... ? :cry: By the way, Thank for your reply :D
electron

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 4408

Post by helloneo » Wed Apr 01, 2009 3:17 am

Well, the statements say
The lock always uses least significant 4 digits after addition
So, all possible states are 0000~9999.. I simply did mod 10000 every time moving into other state..
When I meet the already visited state during the search, I stopped the search..

Hope this help.. :-)

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 4408

Post by f74956227 » Wed Apr 01, 2009 4:00 am

Oh!! I think i make a big mistake... i transform the problem to the coin change one and solve it by DP...
But due to the cyclic property, i can't always find the best solution :( ...

I was too fool to make this mistake orz... and thank you very much!!! :) By the way, your blog is very usefull and a perfect site :)
Thank you again !! :P
electron

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 4408

Post by helloneo » Wed Apr 01, 2009 5:34 am

You mean Felix Halim's site..? It's not mine.. it's Felix Halim's :-)
He also built the great tool for TopCoder if you are interested..

http://felix-halim.net/tc

Post Reply

Return to “ACM ICPC Archive Board”