899 - Colour Circles

All about problems in Volume 8. 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
bryanchris
New poster
Posts: 1
Joined: Thu Aug 21, 2014 11:56 pm

899 - Colour Circles

Post by bryanchris » Fri Aug 22, 2014 12:01 am

I'm keeping getting WA on this problem.

Basically I use breadth-first-search on a graph, in which each vertex is essentially a tuple (a, b) where a and b are the circles where the two counter is. Starting from the final state with one of the counter in the target circle, and keep "backtracking" along the possible move until hitting the starting position (r, s) specified in the problem.

I tested my solution against the two example provided, and also the impossible setting for which the program should return 0 and the game where the target is only one move away.

Did I miss anything?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 899 - Colour Circles

Post by brianfry713 » Thu Sep 04, 2014 2:01 am

I solved it using a BFS starting from the initial position with a counter in R and S, and ending when either counter reaches T.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 8 (800-899)”