JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 534 Slightly? Harder version of the Div2-500/Div1-250
 Slightly? Harder version of the Div2-500/Div1-250 | Reply Same setup, but now the question is not who will win, since we already know.The question is now this: Knowing who will win, what is the least number of moves in which they can end the game.The player who can win will always aim for the least number of moves, while the player who can't win will always move so as to make the game last as long as possible.An example:The game board looks like this:ooo.In this game, player 2 will win, but player 1 goes first.Player 1 has two options, but he will choose --> oo.. rather than .oo.So the answer was '6' to this board.Example:oooo.Ans: 8There can be more than one way to attain the minimum game-length.------------Hah, another variation could be where the losing player assists the winning player in ending the game as soon as possible.
 Re: Slightly? Harder version of the Div2-500/Div1-250 (response to post by Cricicle) | Reply The "slightly" harder version of this problem was a 2D board up to 50 by 50, which was actually the initial proposal for Div1 250. Then backtrack and bitmask DP wouldn't work, however we decided to allow alternative solutions (and good thing we did that, since the majority of people used these approaches).
 Re: Slightly? Harder version of the Div2-500/Div1-250 (response to post by espr1t) | Reply That actually sounds like a much more interesting version of the problem (but too hard for a 250 pointer!)edit: in retrospect, maybe not so hard. But still more interesting since it requires you to actually think about the game, rather than just going: oh hey, the game is acyclic and the state space fits into memory; let's just do recursion+memoization.
 Re: Slightly? Harder version of the Div2-500/Div1-250 (response to post by espr1t) | Reply Can you please post the match editorials?
 Forums Algorithm Matches SRM 534 Slightly? Harder version of the Div2-500/Div1-250 Previous Thread  |  Next Thread