Sahar's blog

UVA: Free Candies
By Sahar, 14 years ago, In English


Hi everyone,

I've been stuck on this problem for a week, Can someone please give me some hints/tips?


-Sahar

Tags uva
  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
14 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it
It looks like a DP on the heights of each of the piles. From that, you can uniquely determine what has to be in your basket (if it's possible to reach the state at all). Then consider all 4 possible moves when computing DP transitions. Complexity will be n^4.
→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    I would call it BFS, but it can be written in DP manner.

    Note: Current set of candies in the basket is uniquely determined by current heights of the piles, so each vertice of game's graph is four numbers between 0 and 40.

    → Reply