help with a DP problem. 
Разница между en1 и en2, 228 символ(ов) изменены
hello codeforces,↵

I have come here to ask help to dp experts. I will highly appreciate it if you can help solve this dilemma. I have been struggling with this for a while now. ↵

THe problem can be found here.↵

http://mirror.codeforces.com/contest/69/problem/D↵

Now i am not working on a general solution. My algorithm is just for the first test case and i am confused why the result is  "Anton loses" when the correct answer is "Anton wins". I have stepped through the logic of my DP formulation and i dont seem to spot the fallacy. So, can you please point out the point where my logic fails. I will highly appreciate it. Thanks for your time. I have commented out parts of my code for legibility. ↵



~~~~~↵

import math↵


#For the following test case↵
#0 0 2 3↵
#1 1↵
#1 2↵
#↵
#↵
#x --> x coordinate↵
#y --> y coordinate↵
#t --> if t == True then Anton turn, if t == False then Dasha turn↵
#fs --> if first player or Anton has swapped, since only 1 swap is possible↵
#ss --> if second player or Dasha has swapped, since only 1 swap is possible↵


def canWin(x, y, t, fs, ss):↵

  if math.sqrt(float(x)*float(x) + float(y)*float(y)) > 3:↵
    return False↵


  if t == False and ss == False:  #if Dasha turn and if dasha hasnt swapped then can swap 1 time↵
    return (not (canWin(x + 1, y + 1, not t, fs, ss))) and (not canWin(x + 1, y + 2, not t, fs, ss)) and (not canWin(y, x, not t, fs, True))↵
  elif t == True and fs == False: #if Anton turn and if Anton hasnt swapped then can swap 1 time↵
    return (not (canWin(x + 1, y + 1, not t, fs, ss))) and (not canWin(x + 1, y + 2, not t, fs, ss)) and (not canWin(y, x, not t, True, ss))↵
  else: #since both has swapped 1 time now cannot swap further↵
    return (not (canWin(x + 1, y + 1, not t, fs, ss))) and (not canWin(x + 1, y + 2, not t, fs, ss))↵
    ↵

print canWin(0, 0, True, False, False)↵

#Expected result was True since Anton wins but the result is False↵


~~~~~↵

Also, please note that i have removed the memoization part for now as to make the code short and easy to understand so i guess this is not a dp solution. But i am just trying to find the fallacy in my recurrence formula. Thanks!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский kofhearts 2015-12-18 11:48:03 1070
en4 Английский kofhearts 2015-12-14 17:18:49 2111 solved
en3 Английский kofhearts 2015-12-14 07:05:45 1465 added full code
en2 Английский kofhearts 2015-12-14 06:14:07 228 added a clarification
en1 Английский kofhearts 2015-12-14 06:06:59 1978 Initial revision (published)