Hii, Can anyone help me understand the editorial where we took care of truth lie situation. Sorry just started with cp.
1 Like
you have to pass each task of a sub task to get accepted.
What if it gives true but the sequence is for false answers. The better approach would be to consider two separate sequences. One considering all odd answers to be true and one considering even.
https://www.codechef.com/viewsolution/34299609
i think mine is so near to soultion but can find whats wrong in this
I had similar idea, ask at N/2 if G, then go to N/3 if it’s also 3 then remove 33%, if not same then ask for 2N/3 if 2N/3 and N/3 have same verdict then remove 33%. And if all have different verdict that means the number is not present in that region and discard it, It will only arise when
If answer was given in FTF or TFT order
And so i spilt my search in 2 parts [1,N/3] and [2N/3, N].
My approach could only get threw 75 points and then also there were few shortcoming.
So can you pls explain slightly more how you removed 16.66% portion.
@nishant403
Since the ranges are not continuous, is it ok to use a vector of all the allowed values amd look at the (n/4),(n/2) and (3n/4) values?
June long challenge editorial beginner friendly video explanation with animation and code
Delicious cake (CONTAIN) : Codechef June Long Challenge||The Delicious Cake(CONTAIN) - YouTube
Tom and jerry (EOEO) : CodeChef June Long Challenge||The Tom and Jerry Game!||EOEO - YouTube
Even matrix (EVENM) : CodeChef June Long Challenge||Even Matrix|| EVENM - YouTube
2 Likes
I think trend over editorial writing has been changed considerably. But this new type is much easier to understand and beginner’s friendly.
1 Like
-
Query N/2 : G (No loss of generality)
-
Query N/3 :
If G then [1,N/3] is removed. (+33.33%)
If L then [N/3,N/2] is removed. (+16.66%) (consider this only)
- Query 2N/3 :
If L then [2N/3,N] is removed. (+33.33%) So here we get 50% reduction.
If G then [N/2,2N/3] is removed (+16.66%). So here we got 33.33% reduction. (consider this only)
- Query N/6.
If L then [N/6,N/3] is removed. (+16.66%)
IF G then [1,N/6] is removed. (+16.66%)
So we get 50% total reduction.
2 Likes
Such a lovely Question, took me 3 days to solve it completely!!
1 Like
I am not sure of a “Trend” per se 
.
I just like writing in the way I myself thought about a problem, and then elaborating on them.
6 Likes
Yes, at first I thought it was copied
1 Like
Can you tell how the grader was working ?
i used the method of dividing the range in 3 parts as said earlier by n/4 , n/2 , 3n/4 and quering respectively still got 45 pts.
can anyone check why i am getting wa (0000) for 2nd task of subtask 3, for which test case it might be failing?
https://www.codechef.com/viewsolution/34417781
i did the same thing but with a little change … once check it (python 3)
https://www.codechef.com/viewsolution/34418909
1 Like
Instead of using vector to store all the remaining numbers , try to store ranges in the vector.
Make a struct that contains left , right , size integers for a range and make a vector of the remaining ranges.
I had also implemented the same solution as yours first for which I got 45 pts , then I thought of this idea to get a 75pt solution. Hope this helps : )
Yup sure, this can be optimized more. This approach clicked me just hours before the contest ended and I submitted a naive solution. However, it does work for a 15pt answer, if one just implements the given conditions.
@rajarshi_basu or some one else please elaborate on the last part i.e ~33% removed per 2 queries (like derivation of the formula given or intuition or better if there is some easier way to convince that it will remove ~33% at 2 query) .
May be test cases are pretty weak. I had some two solution which were giving me AC to some test files. So I took a random number and if it’s odd chosen the first algo and int even the other.
I then submitted this solution 8 times and in the 8th time I got 75 pts
2 Likes