Re: [gcj] Round 1B 2020 Blindfolded Bullseye: method of finding initial point in dartboard
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 >> >> <https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com?utm_medium=email_source=footer> >> . >> > -- 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.
[gcj] Round 1B 2020 Blindfolded Bullseye: method of finding initial point in dartboard
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.
Re: [gcj] Why didn't my solution for Rounding Error in Round 1B 2018 pass the hidden test set?
Thanks Xiongqi, it worked with your fix! -- 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 post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/768ed006-881b-416d-8729-f4974e72f710%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Why didn't my solution for Rounding Error in Round 1B 2018 pass the hidden test set?
My solution passed both visible test sets, but I got a "TIME_LIMIT_EXCEEDED" error on the hidden one. As far as I can tell, I did exactly what was described to solve test set 3 in the analysis. What did I do wrong? (Python 3) for T in range(int(input())): N, L = list(map(int, input().split())) C = list(map(int, input().split())) if 100 % N != 0: remaining = N - sum(C) counts = C + [0 for i in range(remaining)] needed = [] for cnt in counts: num = cnt while num * 100 / N - int(num * 100 / N) < 0.5: num += 1 needed.append(num - cnt) needed, counts = list(map(list, zip(*sorted(zip(needed, counts) for i in range(len(counts)): if needed[i] <= remaining: counts[i] += needed[i] remaining -= needed[i] counts[-1] += remaining result = [] for cnt in counts: percentage = cnt * 100 / N if percentage - int(percentage) < 0.5: result.append(int(percentage)) else: result.append(int(percentage) + 1) print('Case #' + str(T + 1) + ': ' + str(sum(result))) else: print('Case #' + str(T + 1) + ': 100') -- 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 post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/c7efd9ae-a678-476d-b579-e64bf35c6514%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.