help with a DP problem. 
Difference between en3 and en4, changed 2,111 character(s)
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↵

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. ↵


The test case that fails is the following↵

~~~~~↵

-100 -100 10 200↵
0 1↵
1 0↵
1 1↵
31 41↵
3 4↵
5 2↵
1 2↵
3 3↵
9 8↵
10 2↵
~~~~~↵


Code starts below↵

~~~~~↵

import math↵


vectors = []↵

line_parts = raw_input().split()↵
x = int(line_parts[0])↵
y = int(line_parts[1])↵
n = int(line_parts[2])↵
d = int(line_parts[3])↵

for i in range(n):↵
  l = raw_input().split()↵
  vectors.append((int(l[0]), int(l[1])))↵

mp = {}↵


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

  if math.sqrt(math.pow(x, 2) + math.pow(y, 2)) > float(d):↵
    return False↵

  if (x, y, t) in mp:↵
    return mp[(x, y, t)]  ↵
    ↵
  result = True ↵
    ↵
  if t == False and ss == False:  #if Dasha turn and if dasha hasnt swapped then can swap 1 time↵
    for v in vectors:↵
      result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss)))↵
    result = result and (not canWin(y, x, not t, fs, True)) #swap step↵
  elif t == True and fs == False: #if Anton turn and if Anton hasnt swapped then can swap 1 time↵
    for v in vectors:↵
      result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss)))↵
    result = result and (not canWin(y, x, not t, True, ss)) #swap step↵
  else: #since both has swapped 1 time now cannot swap further↵
    for v in vectors:↵
      result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss)))↵

      ↵
  mp[(x, y, t)] = result↵
  ↵
  return result↵
      ↵

result = False↵

for v in vectors:↵
  result = result or canWin(x + v[0], y + v[1], False, False, False)      ↵
      ↵
if result == True:↵
  print "Anton"↵
else:↵
  print "Dasha"↵

~~~~~↵
solved

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kofhearts 2015-12-18 11:48:03 1070
en4 English kofhearts 2015-12-14 17:18:49 2111 solved
en3 English kofhearts 2015-12-14 07:05:45 1465 added full code
en2 English kofhearts 2015-12-14 06:14:07 228 added a clarification
en1 English kofhearts 2015-12-14 06:06:59 1978 Initial revision (published)