11376 - Tilt!

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

Moderator: Board moderators

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

Interesting read on wiki. Ill see if I can't figure out how to implement such a system. If not I might have to ask for some more help :)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

I search in Google and find this paper:
https:// drum.umd.edu/dspace/bitstream/1903/702/2/CS-TR-3420.pdf
(I don't want to be accused of "deep-linking", so I break up the link above with a space. Sorry.)

You can find a pseudocode of IDA* on page 5.

(My own IDA* handles "z' = infinity" somewhat differently.)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

Thanks for the article. Always nice to learn something new, not the greatest expert in CS. More of a hobby :)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

My major subject is also not Computer Science la... :D

Programming is a great hobby~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

Ok I have a decent understanding of how A* works. Another helpful site I found was http://www.policyalmanac.org/games/aStarTutorial.htm . The problem I am having now is figuring out how to use it for multiple goals, which I don't see being easy to do.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

You don't have to modify the A* algorithm in any way for multiple goals. Just make sure that your heuristic is still admissible in this case (doesn't overestimate the distance to the closest goal state), and everything should work fine.

Alternatively, you can look at the problem in the following way. Let's add an extra move to the game: if all blue squares are taken, then you're allowed to remove the ball off the maze. The new state, corresponding to the ball after it has been removed, will be the new, unique goal state.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

BFS is enough for this particular problem. I was thinking of using "meet-in-the-middle" if my solution timed out, but it didn't. I might try it just to see if it can catch up to mf's solution.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

I don't have a BFS judge solution. But I think heuristic search is not so hard to code for this problem. And such an idea is also not hard to come up with. Of course, to get a better timing for this particular problem, you can add the heuristic function to your BFS, since it is given that you won't need >53 steps for each case.

If one is thinking of using "meet-in-the-middle" (which is by no means easy to code), then I think they'd better try heuristic searches... But it is always fun experimenting with different approaches~ :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

In this case "meet-in-the-middle" doesn't work. At least for me it doesn't.

I seem to be doing something wrong (printing?) but, regardless, I don't think you can gain much going backwards. I realized I needed some sort of heuristic going the other way :)

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

Well I improved upon my program, and made a BFS solution that can solve the 53 step maze in ~11s. Not sure if Ill be able to improve it without fully understanding how to add the hueristic function into my program without killing it :) (I have tried adding some hueristic but so far it doesn't work in my program)

EDIT: Thanks to help from Darko I got my program accepted :) I might try and work on a hueristic approach now. I also made a c++ version, which runs slightly faster than the java version.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

I think it is about time for me to change the test cases a bit. As you may guess the 53-step maze mentioned in previous posts can be found in the judge input. :D So I think I need to change the input file so future solvers cannot cheat.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

First of all, thanks for the nice set! And I specially liked this problem very much. But a complain :D. Why this line was added?
All except two test cases can be solved within 35 steps. One of the two harder cases takes at least 49 steps to solve, and the other 53.
It could be...
There is no case which takes more than 53 steps.
Thanks again...

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

I got AC using BFS. I also tried IDA*, but couldn't find a strictly enough heuristic to avoid TLE.
How could I get a good heuristic for this problem ?

Thanks in advance.
-----
Rio

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

I also tried but the hueristic I came up with only reduced the end node count by about 3%. Not enough to improve time by much, specially since it takes extra implementation to add in the hueristic.

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG »

Kinda weird, but my code keeps getting RTE now. I have changed my code to make it A*, and im fairly certain it works. Has the input set changed at all? And if it has is there an error in it? Can you guys submit again to see if you get RTE as well?

Post Reply

Return to “Volume 113 (11300-11399)”