Re: [gcj] Round 1B 2020 Blindfolded Bullseye: method of finding initial point in dartboard

[Arti Schmidt]

You're right, I missed that and it works after fixing. Thanks!

On Wednesday, April 22, 2020 at 11:51:32 AM UTC-4, Luke Pebody wrote:
>
> One possible issue in your problem is you don't check any of the initial 
> queries for if they are equal to 'CENTER'
>
> On Wed, 22 Apr 2020, 16:32 Arti Schmidt,  > wrote:
>
>> In Round 1B 2020 I'm getting TLE on test set 3 for Blindfolded Bullseye 
>> using nearly the same strategy explained in the analysis (binary search 
>> from a point in the dartboard to the edge of the wall in four directions 
>> and find midpoints). The only difference is how I am finding the initial 
>> point inside the dartboard. I queried points (-10^9/2, 0), (10^9/2, 0), (0, 
>> -10^9/2), and (0, 10^9/2). I thought this would ensure that at least one 
>> point is in the dartboard, but I must be missing something because when I 
>> add a few additional points to query my program passes all test sets. My 
>> full program is below, can anyone tell me why it doesn't work with just the 
>> four mentioned points?
>>
>> bound_max = 10 ** 9
>> t, a, b = map(int, input().split())
>>
>> def query(x, y):
>>   print(x, y)
>>   return input()
>>
>> def binary_search(lower, upper, axis, pos, miss_lower):
>>   while lower < upper:
>> mid = (lower + upper) // 2
>> point = (mid, pos) if axis == 'x' else (pos, mid)
>> if query(*point) == 'MISS':
>>   if miss_lower:
>> lower = mid + 1
>>   else:
>> upper = mid - 1
>> else:
>>   if miss_lower:
>> upper = mid - 1
>>   else:
>> lower = mid + 1
>>   return upper if upper > -bound_max else -bound_max
>>
>> for case in range(t):
>>
>>   # fails with these points
>>   points = (
>> (-bound_max // 2, 0),
>> (bound_max // 2, 0),
>> (0, -bound_max // 2),
>> (0, bound_max // 2)
>>   )
>>
>>   # succeeds with these points
>>   points = (
>> (-bound_max // 2, -bound_max // 2),
>> (0, -bound_max // 2),
>> (bound_max // 2, -bound_max // 2),
>> (-bound_max // 2, 0),
>> (0, 0),
>> (bound_max // 2, 0),
>> (-bound_max // 2, bound_max // 2),
>> (0, bound_max // 2),
>> (bound_max // 2, bound_max // 2),
>>   )
>>
>>   for point in points:
>> if query(*point) == 'HIT':
>>   hit_x, hit_y = point
>>   break
>>
>>   left = binary_search(-bound_max, hit_x, 'x', hit_y, True)
>>   right = binary_search(hit_x, bound_max, 'x', hit_y, False)
>>   bot = binary_search(-bound_max, hit_y, 'y', hit_x, True)
>>   top = binary_search(hit_y, bound_max, 'y', hit_x, False)
>>
>>   x = (left + right) // 2
>>   y = (bot + top) // 2
>>
>>   done = False
>>   for i in range(-2, 3):
>> for j in range(-2, 3):
>>   if query(x + i, y + j) == 'CENTER':
>> done = True
>> break
>> if done:
>>   break
>>
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Google Code Jam" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to googl...@googlegroups.com .
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com
>>  
>> 
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/a8ecb29f-6a73-4c22-8acb-80dfbe21a381%40googlegroups.com.

Re: [gcj] Round 1B 2020 Blindfolded Bullseye: method of finding initial point in dartboard

[Luke Pebody]

One possible issue in your problem is you don't check any of the initial
queries for if they are equal to 'CENTER'

On Wed, 22 Apr 2020, 16:32 Arti Schmidt,  wrote:

> In Round 1B 2020 I'm getting TLE on test set 3 for Blindfolded Bullseye
> using nearly the same strategy explained in the analysis (binary search
> from a point in the dartboard to the edge of the wall in four directions
> and find midpoints). The only difference is how I am finding the initial
> point inside the dartboard. I queried points (-10^9/2, 0), (10^9/2, 0), (0,
> -10^9/2), and (0, 10^9/2). I thought this would ensure that at least one
> point is in the dartboard, but I must be missing something because when I
> add a few additional points to query my program passes all test sets. My
> full program is below, can anyone tell me why it doesn't work with just the
> four mentioned points?
>
> bound_max = 10 ** 9
> t, a, b = map(int, input().split())
>
> def query(x, y):
>   print(x, y)
>   return input()
>
> def binary_search(lower, upper, axis, pos, miss_lower):
>   while lower < upper:
> mid = (lower + upper) // 2
> point = (mid, pos) if axis == 'x' else (pos, mid)
> if query(*point) == 'MISS':
>   if miss_lower:
> lower = mid + 1
>   else:
> upper = mid - 1
> else:
>   if miss_lower:
> upper = mid - 1
>   else:
> lower = mid + 1
>   return upper if upper > -bound_max else -bound_max
>
> for case in range(t):
>
>   # fails with these points
>   points = (
> (-bound_max // 2, 0),
> (bound_max // 2, 0),
> (0, -bound_max // 2),
> (0, bound_max // 2)
>   )
>
>   # succeeds with these points
>   points = (
> (-bound_max // 2, -bound_max // 2),
> (0, -bound_max // 2),
> (bound_max // 2, -bound_max // 2),
> (-bound_max // 2, 0),
> (0, 0),
> (bound_max // 2, 0),
> (-bound_max // 2, bound_max // 2),
> (0, bound_max // 2),
> (bound_max // 2, bound_max // 2),
>   )
>
>   for point in points:
> if query(*point) == 'HIT':
>   hit_x, hit_y = point
>   break
>
>   left = binary_search(-bound_max, hit_x, 'x', hit_y, True)
>   right = binary_search(hit_x, bound_max, 'x', hit_y, False)
>   bot = binary_search(-bound_max, hit_y, 'y', hit_x, True)
>   top = binary_search(hit_y, bound_max, 'y', hit_x, False)
>
>   x = (left + right) // 2
>   y = (bot + top) // 2
>
>   done = False
>   for i in range(-2, 3):
> for j in range(-2, 3):
>   if query(x + i, y + j) == 'CENTER':
> done = True
> break
> if done:
>   break
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAECKw-NnefCPqLPh24NoniJVJ_tafZ6XcqRtgoTgj-zq-t3YzA%40mail.gmail.com.

[gcj] Round 1B 2020 Blindfolded Bullseye: method of finding initial point in dartboard

[Arti Schmidt]

In Round 1B 2020 I'm getting TLE on test set 3 for Blindfolded Bullseye 
using nearly the same strategy explained in the analysis (binary search 
from a point in the dartboard to the edge of the wall in four directions 
and find midpoints). The only difference is how I am finding the initial 
point inside the dartboard. I queried points (-10^9/2, 0), (10^9/2, 0), (0, 
-10^9/2), and (0, 10^9/2). I thought this would ensure that at least one 
point is in the dartboard, but I must be missing something because when I 
add a few additional points to query my program passes all test sets. My 
full program is below, can anyone tell me why it doesn't work with just the 
four mentioned points?

bound_max = 10 ** 9
t, a, b = map(int, input().split())

def query(x, y):
  print(x, y)
  return input()

def binary_search(lower, upper, axis, pos, miss_lower):
  while lower < upper:
mid = (lower + upper) // 2
point = (mid, pos) if axis == 'x' else (pos, mid)
if query(*point) == 'MISS':
  if miss_lower:
lower = mid + 1
  else:
upper = mid - 1
else:
  if miss_lower:
upper = mid - 1
  else:
lower = mid + 1
  return upper if upper > -bound_max else -bound_max

for case in range(t):

  # fails with these points
  points = (
(-bound_max // 2, 0),
(bound_max // 2, 0),
(0, -bound_max // 2),
(0, bound_max // 2)
  )

  # succeeds with these points
  points = (
(-bound_max // 2, -bound_max // 2),
(0, -bound_max // 2),
(bound_max // 2, -bound_max // 2),
(-bound_max // 2, 0),
(0, 0),
(bound_max // 2, 0),
(-bound_max // 2, bound_max // 2),
(0, bound_max // 2),
(bound_max // 2, bound_max // 2),
  )

  for point in points:
if query(*point) == 'HIT':
  hit_x, hit_y = point
  break

  left = binary_search(-bound_max, hit_x, 'x', hit_y, True)
  right = binary_search(hit_x, bound_max, 'x', hit_y, False)
  bot = binary_search(-bound_max, hit_y, 'y', hit_x, True)
  top = binary_search(hit_y, bound_max, 'y', hit_x, False)

  x = (left + right) // 2
  y = (bot + top) // 2

  done = False
  for i in range(-2, 3):
for j in range(-2, 3):
  if query(x + i, y + j) == 'CENTER':
done = True
break
if done:
  break

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com.