2009/10/12 Bharath Raghavendran <[email protected]> > > > 2009/10/12 Paul Smith <[email protected]> > >> >> Some observations: >> >> Every position is either a win for you or your opponent - the game >> does not contain draws. >> >> Furthermore, the sub-game played from one consecutive set of biscuits >> is entirely independent of the other sub-games. >> >> A single '1' is always winnable (b >= 1) >> >> A string of 1s is winnable if its length is less than b. >> >> A string of 0s is identical to a single 0 : 11100000000111 is the same >> game as 1110111 >> >> A position is winnable if it contains an even number of unwinnable >> sub-positions. >> >> > are you sure of this ? > > suppose there are just 2 symmetric subpositions .. its impossible to win > this because whatever move i do, the opponent can do the same in the other > sub-position and hence winning. this means irrespective of whether the > subpositions are winnable or not, a problem having 2 symmetric subpositions > is unwinnable. > > infact, just because a sub-position is unwinnable doesnt mean you will > definitely lose the sub-position. the opponent may play it in such a way > that you may still win the sub-position if that leads to his victory. this > is where i don't know how to proceed. would i need to use 2 flags for > winnable and losable ? > > here is an example : say b = 1 and the problem is 11011 ... both subpositions are unwinnable but yet the main position is also unwinnable.
Infact, while trying to find this example, i realized that a problem with only '1's without gaps is unwinnable only if its even number of 1s and b=1. As any other case, you can split the problem into 2 symmetric sub-problems and mirror whatever move your opponent does. > > >> I think you can DP it from there. >> >> On Mon, Oct 12, 2009 at 12:11 PM, Brats <[email protected]> wrote: >> > >> > Hey .. here is a problem I saw somewhere on net. Can anyone give me >> > some ideas on its algo ? >> > >> > There is a tray that contains a row of "s" slots where biscuits may be >> > placed. You can have atmost one biscuit per slot. You and your friend >> > play a game with it. Each of you get to pick biscuits in turns. You >> > can pick atmost "b" biscuits in a single turn provided they are in >> > consecutive slots with no gaps (empty slots) in between (but you have >> > to pick atleast one in your turn). Whoever picks the last biscuit wins >> > the game. >> > >> > You are given a snapshot of the game and its your turn. Assuming that >> > from this point onwards, both the players play optimally. Find out if >> > you can win the game. And if yes, what is your next move? If there are >> > multiple options for the next move, choose the one where you pick the >> > highest number of biscuits in the next turn. If still there are >> > multiple options, choose the one where you take the leftmost biscuit >> > among them. >> > >> > As input, you will be given 't' which indicates the number of test >> > cases. For each case, you will be given s ( 1<=s<=2000 ), b >> > ( 1<=b<=20 ) seperated by space and the next line will contain s >> > characters that are either '0' or '1' representing each of the s >> > slots. '0' indicates that a biscuit is not present at that particular >> > slot and '1' indicates that a biscuit is present. >> > >> > As output, print "yes" or "no" indicating if you can win and if the >> > answer is yes, print a string of s characters of either '0' or '1' >> > that indicates whether a biscuit is absent or present at the >> > particular slot after you have played your turn. >> > >> > Sample input: >> > 3 >> > 3 2 >> > 111 >> > 8 3 >> > 10110111 >> > 8 4 >> > 11111111 >> > >> > Sample output: >> > yes 101 >> > no >> > yes 11000011 >> > >> > > >> > >> >> >> >> -- >> Paul Smith >> http://www.nomadicfun.co.uk >> >> [email protected] >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
