If you run the local testing tool enough times, you'll get an error. Try
the case where the server starts with '11111111111111111111' (20 ones) and
flips to '00000000000000000000' (20 zeros) on 21st query. The code below is
a judge I adapted from the official judge that tests for this case. Save it
into judge.py and run `python3 interactive_runner.py python3 judge.py --
python3 your_solution.py`. See if you can figure out why you got a WA.
from __future__ import print_function
import sys
try:
input = raw_input
except NameError:
pass
def read_input():
response = input()
if len(response) == 20:
return response, None
num = int(response)
if not 1 <= num <= 20:
return None, 'Input position is out of range.'
return num, None
def main():
print(1, 20)
sys.stdout.flush()
i = 1
test_case = '1' * 20
while i <= 150:
inp, err = read_input()
print(i, inp, test_case, file=sys.stderr)
if err is not None:
print('Case #{} fails:\n{}'.format(1, err), file=sys.stderr)
if isinstance(inp, str):
if test_case != inp:
print('Wrong answer: contestant input {}, but answer is
{}.'.format(
inp, test_case), file=sys.stderr)
print('N')
return
print('Y')
sys.stdout.flush()
return
if i == 20:
test_case = '0' * 20
print(test_case[inp - 1])
sys.stdout.flush()
i += 1
print('Contestant tries to query too many times.', file=sys.stderr)
sys.exit()
if __name__ == "__main__":
result = main()
If you are struggling, here's the reason (white text, select to reveal it):
Line
139 calls 11th query for position 6 to get ans[5]. Now, your ans is
111111xxxxxxxxx11111. Then, `validate()` spends 12th query on
`value_change()` on 89 because there's `equal_values` but not
`diff_values`. Then, back to `main()`, `query()` on line 141 calls 13th
query. Then the while loop calls 14th and 15th, 16th and 17th, 18th and
19th. Then, line 139 calls 20th query for position 10 to get ans[9], and it
gets 1. Now your ans is 1111111111x111111111. Then, line 141 calls 21st
query for position 11 to get ans[10], and it gets 0, because the bit-flip
happened. Now your ans is 11111111110111111111. 22nd query is used to check
bit-flip, which it got. 23rd query is used to check reversing because the
code incorrectly identified a `diff_values`, and therefore your answer is
00000000010000000000.
How to solve this (white text, select to reveal it): Make sure `validate()`
makes 2 queries under all cases, even if that means sometimes one query is
wasted (just use `query(1)` and discard the answer. This will make sure
that the query number for line 139 is always odd, and query number for line
141 is always even. Then, when the server data changes, it always happen
after line 141, and not between 139 and 141.
On Tuesday, April 7, 2020 at 9:56:59 AM UTC-7, guillalva wrote:
>
> Hello everyone,
>
> I'm trying to solve this issue using the strategy described on the
> analysis of that problem. I tested locally and the solution is passing all
> three test cases. When I sent to the server is failing on the test set 3.
>
> import sys
> from sys import stdin
>
> def do_complement():
> #print('Complement')
> global ans
> #print(ans)
> for i in range(len(ans)):
> if ans[i] == '0':
> ans[i] = '1'
> elif ans[i] == '1':
> ans[i] = '0'
> #print(ans)
>
> def do_swap():
> #print('Swap')
> global ans
> #print(ans)
> n = len(ans)
> for i in range(n//2):
> ans[i], ans[n-1-i] = ans[n-1-i], ans[i]
> #print(ans[i], ans[n-1-i])
> #print(ans)
>
> def query(i):
> global ans
> val = get_index(i)
> validate()
> ans[i-1] = val
>
> def find_index():
> global ans
> for i in range(len(ans)//2):
> if ans[i] == '' or ans[len(ans)-1-i] == '':
> return i
> return len(ans)
>
> '''
> Get the value of the bit string on i index
> '''
> def get_index(i):
> print(i)
> sys.stdout.flush()
> global cont
> cont = cont + 1
> val = stdin.readline().strip()
> return val
>
> '''
> Check if the value on index i has changed and differs from the stored value
> '''
> def value_change(i, old_value):
> val = get_index(i)
> return val != old_value
>
> def find_equal_pair():
> global ans
> n = len(ans)
> for i in range(n):
> if ans[i] != '' and ans[i] == ans[n-1-i]:
> return (i+1, ans[i])
> return None
>
> def find_diff_pair():
> global ans
> n = len(ans)
> for i in range(n):
> if ans[i] != '' and ans[n-1-i] != '' and ans[i]!=ans[n-1-i]:
> return (i+1, ans[i])
> return None
>
> '''
> Validate which change occurs on the bit string after 10 queries
> '''
> def validate():
> # In this moment the bit string has changed so We need to find how it
> change?
> if cont % 10 == 1:
> equal_values = find_equal_pair()
> diff_values = find_diff_pair()
> global ans
> #print('Validate')
> #print(ans)
> #print(equal_values)
> #print(diff_values)
> if equal_values != None:
> # The string has an pair of 0's or 1's so we need to check
> what was
> i = equal_values[0]
> old_value = equal_values[-1]
> if value_change(i, old_value):
> # The value change so it could be a complement or
> # a swap-complement. We need to validate what was using
> # a pair of different numbers
> do_complement()
> if diff_values != None:
> j = diff_values[0]
> if value_change(j, diff_values[-1]):
> # The value of the pair change so it was a
> complement
> pass
> else:
> # The value of the pair didn't change so it was
> complement-swap
> do_swap()
> #do_both()
> else:
> # The values are the same so it could be a swap or
> # the string didn't change. We need to validate what was
> using
> # a pair of differents numbers
> if diff_values != None:
> j = diff_values[0]
> if value_change(j, diff_values[-1]):
> # The value of the pair change so it was a swap
> do_swap()
> else:
> # The value of the pair didn't change so the
> string didn't change
> pass
> else:
> # Do nothing for this string.
> pass
> elif diff_values != None:
> # The bit string is composed only for pair of differents
> numbers
> j = diff_values[0]
> if not value_change(j, diff_values[-1]):
> # Do nothing
> pass
> else:
> # It is a swap or a complement but both produces the same
> change
> # on the bit string
> do_complement()
>
> def main():
> cases, n = [int(x) for x in stdin.readline().strip().split()]
> for c in range(cases):
> global cont, ans
> cont = 0
> ans = ['' for x in range(n)]
> i = 0
> while i < len(ans):
> # ask for the ith and jth bit
> if ans[i] == '':
> query(i + 1)
> if ans[n-1-i] == '':
> query(n - i)
> i = find_index()
> print(''.join(ans))
> sys.stdout.flush()
> check_ans = stdin.readline().strip()
> if check_ans == 'N':
> break
>
> main()
>
>
> I'm using python 3. Do anyone has an idea of an error on this code?
>
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/dd2d74ea-7143-4bc9-98db-93d670482007%40googlegroups.com.
