I know you guys hate the dreaded look at my code question
But bear with me
Approach 1
I tried to approach the problem by first decomposing n into 4a+5b , 4a+6b , 4a+7b 5a+6b , 5a+7b , 6a+7b and breaking it down to solving individually for 4 , 5, 6 , 7
Four :
1 1 2 3
1 2 3 4
1 1 2 4
1 1 3 4
Five :
1 1 2 4
1 1 2 5
1 1 3 5
1 2 3 4
1 3 4 5
Six :
1 1 2 4
1 1 2 5
1 3 4 5
1 3 5 6
1 4 2 6
1 1 3 6
Seven :
1 1 2 3
1 1 2 4
1 3 4 5
1 3 4 6
1 5 6 7
1 2 6 7
1 1 5 7
And applying a set of appropriate xors to find the value .
Issue
It was a huge code , gave wa , got dejected
Now since n is always 4a,4a+5,4a+6,4a+7
Made my code much smaller and then submitted , I got -1 indicating that I have used more than n queries when that isn’t the case?
Doubts
- Is there a neat mathematical proof that n is always of 4a,4a+5,4a+6,4a+7
- Please enlighten me on why my code fails .
- I kind of figured all these combinations to solve for 4 , 5 , 6 , 7 by hand . Is there a pattern or simpler way ?
My (noobish )Code
(https://www.codechef.com/viewsolution/22000554)
I've been stuck at 3 star since forever and want to up my game so I thought I'd upsolve all problems from the first long challenge . Is anyone interested ?
I solved the problem in the similar way at first. I figured out that we can always solve for 4 so I reduced the array by solving segments of 4 until there was a segment of (4 or 5 or 6 or 7) left. Then I solved for 5,6,7 by hand and used that in the code. It was painful process but doing that made me realize that there was a pattern to it(that you can always use the previously found values to find the next two values and so on). This second approach was much smaller as compared to the first one.
Pattern: after using 1,2,3 and 1,2,4 we can get 3^4. Now use 3^4 and ask questions like (3,4,5) and (3,4,6). Now you have 5 and 6. Use 5^6 and ask similar questions and get the next two values. After you arrive at end it’s simple to figure out the end case. I’ll leave that as an excercise.
Let me know if you need any more clarity.
No need to use for seven. Since constraints are N>=8, we can calculate N%4=3 case by 1 Five, 1 Six. You can see my solution. It’s easy to understand.
Yes I got your approach , thanks 
Will try to code it later
I don’t really know why our code fails 
. I saw your post and your approach involving cyclic xor .
I am aware of the simpler methods now thanks to our friendly coders here but I am still stuck on why my code fails
Yes , I have seen your video . Well made as usual .
You and codereport provide nice editorials
1 Like
I also used this naive method to solve the question, you can see my code, it’s a bit long but compartmentalized so you might easily be able to understand.
Logic :
Take n%4
C1(n%4==0): solve it in sets of 4 each (total n/4 sets)
C2(n%4==1) solve it in set of 4 and 1 as a set of 5 (total n/4 sets of 4 and 1 set of 5)
C2(n%4==2) solve it in sets of 4 and 1 as a set of 5 (total n/4 -1 sets of 4 and 1 set of 10 (2 sets of 5 each))
C3(n%4==3) solve it in sets of 4 and 1 as set of 7 (total n/4 sets of 4 and 1 set of 7)
Link to my implementation : https://www.codechef.com/viewsolution/21976641
It’s a big code with a lot of redundancy but it got me an AC :>)
Is there a neat mathematical proof that n is always of 4a,4a+5,4a+6,4a+7
What? The statement is simply saying that, every number is either a multiple of 4 or gives a remainder of 1,2 or 3 when divided by 4, which is a universal truth. 
Made my code much smaller and then submitted , I got -1 indicating that I have used more than n queries when that isn't the case?
Thats wrong. -1.0000 is given when your code does something unexpected, like not terminating after receiving -1, giving multiple answers per query or any other random stuff which you arent supposed to do in first place. I advise to use assert statements and see the number of queries and number of times indices are used per test case and do stress testing locally.
every number greater than except 11 can be expressed as sum of any no. of 4s and 5s
1 Like
11 was not included in the test cases btw
I am up for upsolving too. Stuck at three-star since 2000.