You are not logged in. Please login at www.codechef.com to post your questions!

×

Need help with one test file for problem INTXOR

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.

asked 18 Dec '18, 05:40

ritam777's gravatar image

4★ritam777
12
accept rate: 0%

edited 18 Dec '18, 07:55

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.

(18 Dec '18, 06:02) ritam7774★

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

(18 Dec '18, 07:59) ritam7774★

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

(18 Dec '18, 08:33) avi2244★

WA (-1.000000) is all I see.

(18 Dec '18, 09:06) ritam7774★

@vijju123: Any response to this?

(18 Dec '18, 15:52) ritam7774★

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.

(18 Dec '18, 23:53) vijju123 ♦♦5★

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

(18 Dec '18, 23:53) vijju123 ♦♦5★

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

(19 Dec '18, 12:51) ritam7774★

I think it's something with how judge interact with output produced in python3(Not Sure). I have 2 same solution(Algorithm wise). one in python3(AC 35 Points) and other in C++14(AC 100 Points). 1. In python3 here 2. In C++14 here

(19 Dec '18, 18:30) shivam_g14704★
showing 5 of 9 show all

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.

link

answered 18 Dec '18, 23:42

oleg_b's gravatar image

7★oleg_b
2574
accept rate: 17%

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

Yes, its perfectly fine to punish participants here. You ought to read the interactive problem guides before first, which clearly state that if your code does not terminate after the judge gives a WA verdict, you can crash judge and get any verdict (except AC) which can be TLE, WA or some weird RE:XXXXXX.

I think it's something with how judge interact with output produced in python3(Not Sure).

Unless there are $0$ accepted solutions n python 3, this claim cannot be explored.

In python3 here 2. In C++14 here

Its much more likely you unconsciously did a very minor change while translating to C++ code which fixed the error? Also, your way to terminate the program in python seems unnatural.

Clarifying my statement-

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.

Its not possible to account for ALL possible cases. For all we know, the participant may output a string instead of number, like "Enter a number" or output some weird large number as string output any random damn thing he could xD. Hence, its not possible to make judge 100% crash proof unless all the infinite possible behaviors of thousands of coders are accounted for. But please know, the judge will work and give correct verdict if you do everything as expected, i.e. adhere to I/O format and use correct algorithm. I feel this answers your doubt?

link

answered 20 Dec '18, 15:32

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

@vijju123: I think you missed the whole point again in trying to defend Codechef. You never looked at my code. I don't even need to read the interactive problem guide in this case since it was mentioned in the problem itself and I took care to terminate the code if -1 is returned.

(21 Dec '18, 18:25) ritam7774★

@ritam777 - I think you missed my entire point again in trying to defend yourself.

You never looked at my code.

I did look at it. But the code was extremely horrible. Also, there isnt any strong reason to look at the code. I am sorry if I missed anything, please reiterate that here :)

I took care to terminate the code if -1 is returned.

Its not terminated if its TLE. From the comments, I can see that your python solution was getting time out which was shown as WA.

The point is, if you were in doubt over $-1$ verdict, then ask in comments, look at previous forum posts, whats the use of shouting over it now? The contest s over, your solution will still get TLE/ WA-1 if rejudged and hence no restoration of points can be done.

And to the crux of it, I dont wanna argue over whose correct. These things disinterest me. Tell me what CAN be done to correct it, if you have grievance and I will look at it. ARguing over such things is a time waste, with lot of redundant mud throwing on me for nothing usually.

(21 Dec '18, 18:53) vijju123 ♦♦5★

@vijju123: "The code was extremely horrible". I know you have bragging rights since you're a "5-star rated" coder, but I didn't know a moderator on a public forum is allowed to make personal remarks targeting others' coding practices. FYI I am a noob at python practices & I never studied python formally. I'm not getting paid here for writing maintainable code. I am here to test my logic. You should not be bothered about practices here.

"I am sorry if I missed anything": Turns out you should be since you missed the point again. I said look at the code to see that I had added the -1 check.

(22 Dec '18, 00:32) ritam7774★

@vijju123: You are so casual while declaring TLE was displayed as WA as if it is normal on codechef and everywhere else and it was all my fault. Is it not an issue and shouldn't "figuring out how it CAN be corrected" be a top priority for the judging panel?

WHY DO YOU INHERENTLY EXPECT THAT APART FROM DEBUGGING THEIR OWN CODE, PEOPLE SHOULD ALSO SPEND TIME DEBUGGING YOUR JUDGE?

And why do you think I need to "defend myself"? I am here pointing out an issue with the judge right (which others have also done)? Don't you know it's "prosecution" vs "defence"?It's not like "defence" vs "defence".

(22 Dec '18, 00:35) ritam7774★

There were atleast two posts by people asking what is wrong with the judge. One of the links is below (asked later during the course of the contest). https://discuss.codechef.com/questions/142160/giving-wa-10000 There was another one asked which was prematurely closed by someone saying "contest is on, we will comment on it after contest ends". Both threads didn't provide much. You expect me to just have created a third thread at that time? Is your task not to make coder's life a bit easier at your platform? On top of that you come and say "Yes, its perfectly fine to punish participants here".

(22 Dec '18, 00:42) ritam7774★

@vijju123: This is another example: https://discuss.codechef.com/questions/142104/wa-1000-coming-in-my-code

I could find 4-5 similar posts by different people during the contest with no concrete response. What should I have done in that case?

It is very easy to sit there and provide suggestions and not look into improving the system or compensating the coders who were facing all these issues. Instead you say you are "perfectly fine to punish" them for it.

(22 Dec '18, 00:57) ritam7774★
1

@ritam777 I don't think this needs to be discussed any further unless you have solution for the problem. Nothing in world is perfect. We have to live on with what we have or improve it ourselves. Peace!

(22 Dec '18, 11:07) shivam_g14704★

TLDR, I cannot waste more of time. I have to spend it addressing real issues rather than hearing someone rant over a problem on long.

(22 Dec '18, 14:09) vijju123 ♦♦5★

@shivam_g1470: Good to see you using my post for building your "reputation points" and registering in moderator's good books. Nothing in the world is perfect you say. The moderators (@vijju123) are not even sorry for the panel's mistakes. Heck they are not even sorry for personally attacking a python-noob's coding practices (calling my code as "extremely horrible").

(23 Dec '18, 06:21) ritam7774★
showing 5 of 9 show all

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)

link

answered 18 Dec '18, 06:03

diegohdmgz's gravatar image

5★diegohdmgz
263
accept rate: 33%

edited 18 Dec '18, 06:07

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.

(18 Dec '18, 06:07) ritam7774★

I saw your code but couldn't find the bug :( Sorry

(18 Dec '18, 07:59) diegohdmgz5★

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.

(18 Dec '18, 08:07) ritam7774★
link

answered 18 Dec '18, 09:14

cenation092's gravatar image

5★cenation092
17711
accept rate: 6%

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

(18 Dec '18, 09:17) ritam7774★

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

link

answered 18 Dec '18, 09:24

wmoise's gravatar image

7★wmoise
1072
accept rate: 9%

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

(18 Dec '18, 09:32) ritam7774★

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.

link

answered 18 Dec '18, 17:19

sorcerer48's gravatar image

5★sorcerer48
1055
accept rate: 30%

edited 18 Dec '18, 17:22

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

link

answered 18 Dec '18, 20:19

shoom's gravatar image

6★shoom
2734
accept rate: 22%

It was because of TLE.

I changed res = res +.... to res+=

and it was accepted

check the code here https://ideone.com/OaN571

link

answered 19 Dec '18, 20:32

ksskreddy2015's gravatar image

5★ksskreddy2015
11
accept rate: 0%

I did it in the same manner, although this method is a bit naive but it got me an AC, here is my implementation https://www.codechef.com/viewsolution/21976641

link

answered 19 Dec '18, 22:21

kartikay101's gravatar image

3★kartikay101
133
accept rate: 0%

Now I feel gutted. I lost points and got a bad ranking because of CodeChef error and @vijju123 won't reply too.

(20 Dec '18, 01:15) ritam7774★

Please report important matters/grievances to me on mail so I dont miss them. Not possible to go through every thread of forum at all times dear. :(

(20 Dec '18, 15:35) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,410
×37
×17

question asked: 18 Dec '18, 05:40

question was seen: 755 times

last updated: 23 Dec '18, 06:23