Need help with one test file for problem INTXOR

general
, ,
1

Problem: https://www.codechef.com/DEC18A/problems/INTXOR/

My Solution (in simple python): It works for first 2 subtasks and also 5 out of 6 test files in subtask 3: https://www.codechef.com/viewsolution/21864465

If you see “Access Denied”, check my code here: https://ideone.com/G46A36

Logic: The above solution uses cyclic relationships between XOR results to find the original numbers. I found that these cyclic relationships exist for a group of 4, 5 and 7 numbers. E.g.: if I need to identify a group of 4 numbers say A, B, C and D, I can easily do that by asking 4 questions with each of A, B, C and D repeated atmost thrice.
For a group of 4 numbers the 4 questions will be:

A, B, C -> XOR = X1

B, C, D -> XOR = X2

C, D, A -> XOR = X3

D, A, B -> XOR = X4

then, A = X1 ^ X3 ^ X4, B = X1 ^ X2 ^ X4, C = X1 ^ X2 ^ X3, D = X2 ^ X3 ^ X4

Similarly I found such cyclic relationships for groups of 4, 5 and 7 elements (Not sure why group of 6 elements ends up with indeterminate equations). You can find those relationships in the above solution.

Now, given an array of size N, I break the given array into:

(i) (N/4) groups of 4 elements each if N mod 4 is zero.

(ii) (N-5)/4 groups of 4 elements each plus 1 group of 5 elements if N mod 4 = 1.

(iii) (N-10)/4 groups of 4 elements each plus 2 groups of 5 elements each if N mod 4 = 2

(iv) (N-7)/4 groups of 4 elements each plus 1 group of 7 elements if N mod 4 = 3.

Applying above cyclic relationships to all groups gives all elements of array. The above solution works for all N >=4 except N=6 but it shouldn’t be a problem since N>=8 in the problem.

The above solution has only one test file failing to get the correct result. I struggled to debug my solution but ultimately couldn’t find one failing test case.

Can anyone help me find one breaking test case? I know there could have been easier solutions but this is what came to my mind first and I stopped trying in the long contest once I couldn’t get even the second problem fully correct, out of frustration.

2

I just found this discussion: https://discuss.codechef.com/questions/141708/interactive-problems-and-the-way-to-deal-with-them/141899
If it really was a TLE being shown as WA, then I’m probably done with codechef in general and long contests in particular.
Someone please tell me that it really was a wrong answer, not a TLE otherwise I’ll probably go mad after spending 2 days on debugging my logic. I got so frustrated that I didn’t attempt any question after that, leading to a ratings decline with demotion to div 2.

3

I think your idea is right. Maybe your implementation it’s wrong but I can’t see your code to check that (access denied).

But, I found a way to solve it when the group has 6 elements.
Let’s define XOR(a,b,c) as a^b^c

We have to make 6 questions

X1 = XOR( A , B , C )

X2 = XOR( B , C , D )

X3 = XOR( D , E , A )

X4 = XOR( E , F , C )

X5 = XOR( A , F , D )

X6 = XOR( F , B , E )

And Then
E = XOR( X1 , X2 , X3 )

F = XOR( X1 , X2 , X5 )

C = XOR( X4 , E , F )

B = XOR( X6 , E , F )

A = XOR( X1 , B , C )

D = XOR( X5 , A , F)

4

Thanks for your reply. My code can be found here: https://ideone.com/G46A36
Do you know why regular cyclic flow doesn’t work for group of 6 leading to redundant equations?
Also, I’m now thinking that it was codechef error (TLE showing up as WA). Refer to comment I added to my own question above.

5

I saw your code but couldn’t find the bug :frowning: Sorry

6

@avi224: If you cannot see the code, check the link I posted at the end of the answer as well as in the original question. Do you think I am that naive, that I will spend two days without actually reading the problem properly? If you see the code, you will find a condition that breaks and returns if 1 is not returned by the checker.
So please “Stop blaming me”. If others have also complained about the same issue, it is not like they are all mad.

7

I think no bug exists so you couldn’t find. Thanks for your time though. I believe it is just a codechef goof-up now that I see other posts on the forum.

8

@ritam777 My bad, I didn’t see your code. Are you getting WA with -1 sec or with some positive time?

9

WA (-1.000000) is all I see.

10

This will help you

11

Hi @cenation092 thanks for the link. I am aware of that solution already, but I need help in understanding why this logic fails.

12

You only needed to find the first four.
Then to find R[n], you can ask for R[n-2] ^ R[n-1] ^ R[n]. Since you already know R[n-1] and R[n-2], you can compute the R[n] = ans ^ R[n-1] ^ R[n-2]. Then you can find R[n+1] via the same process, since you now know R[n] and R[n-1].

13

Thanks for your response. Like I said I know there are other ways, but I am curious why this solution fails. Btw I think your explanation is incorrect (though I think you have done it correctly in the contest) coz if you are saying i can calculate first four initially, that means the first four indices 1-4 have already been used up thrice in questions, so you cannot ask another question with 3, 4, 5 since 3 and 4 have appeared thrice already while finding R[1], R[2], R[3] and R[4].

14

@vijju123: Any response to this?

15

For n = 6 , I used questions using this pattern. Let the six indices be a , b, c, d , e ,f;

  1. a b c
  2. a b d
  3. c d e
  4. c d f
  5. e f a
  6. e f b

And for remaining I used similar pattern for finding indexes in multiple of 4. For instance let indices be i,j,k,l.

  1. i j k
  2. i j l
  3. k l i
  4. k l j

You can see my solution that the given pattern works. Solution link is
Solution Link

This answer was just to suggest a new kind of pattern. And sorry I was not able to solve your query.

16

Did you try to flush the output after printing the answer? Not sure if it helps, just a thought.

17

It is definitely TLE while it is shown as WA(-1.00).

Try to run your solution in Python 2.7. Same source code should work but you will get WA (-1.00) for all test cases.

You can also make small modification for your code to make it a bit faster by pre-allocating the memory for the res list. The modification (only relevant part is shown) looks like this:

for _ in xrange(t):
    n = int(raw_input())
    d = n/4
    i = 1
    res = [2]*(n+1)
    if n%4 == 0:
        for _ in xrange(d):
            r4 = solveFor4(i, i+1, i+2, i+3)
            for j in range(4):
                res[i+j] = r4[j]
            i += 4
    elif n%4 == 2:
        for _ in xrange(d-2):
            r4 = solveFor4(i, i+1, i+2, i+3)
            for j in range(4):
                res[i+j] = r4[j]
            i += 4
        r5 = solveFor5(i, i+1, i+2, i+3, i+4)
        for j in range(5):
            res[i+j] = r5[j]
        i += 5
        r5 = solveFor5(i, i+1, i+2, i+3, i+4)
        for j in range(5):
            res[i+j] = r5[j]
    else:
        for _ in xrange(d-1):
            r4 = solveFor4(i, i+1, i+2, i+3)
            for j in range(4):
                res[i+j] = r4[j]
            i += 4
        if n%4 == 1:
            r5 = solveFor5(i, i+1, i+2, i+3, i+4)
            for j in range(5):
                res[i+j] = r5[j]
        else:
            r7 = solveFor7(i, i+1, i+2, i+3, i+4, i+5, i+6)
            for j in range(7):
                res[i+j] = r7[j]
    print " ".join([str(x) for x in res])
    output = int(raw_input())
    if output != 1:
        break

With this modification your code runs faster, and you will get AC on the problem test case.

1 Like
18

While I was not the part of panel for this contest, I can bet that its because of judge not handling all exceptions. Like, when making an interactive problem, there are several norms to adhere to, several headers of spoj to include and to use their functions for verdicts. In case the participants code does something unexpected causing your code to crash, a -1 verdict is given. And since the program crashed, you cannot count on it to give correct verdict.

Usually this means your code did something/printed something which it shouldn’t have and the judge is not handling that exception either.

19

(The above comment is purely my own opinion and is NOT to be taken as formal and confirmatory way of how system works)

20

@vijju123: What should be the next steps? Do you think it is okay to punish the participants for issues with the judge? We spend a lot of time trying to debug our code since we trust the verdict given by the judge.