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
This method gives only 15 points
1 Like
How can this solution pass ? Which reduces 33% portion in worst 3 queries. I found this solution in the first day, but thought It can’t work and spent 2 more days to find the other solution.
Here is the procedure :
Query N/3, if it is ‘G’, we query N/3 again. if both are the same we reduce 33% in 2 queries. which as you said won’t happen.
So we get ‘L’ at 1st or 2nd query, then we Query for 2N/3.
If is ‘G’, the portion [N/3,2N/3] is removed.
else the portion [2N/3,N] is removed.
This should give more than 140 queries in the worst case. (Calculated as T(n) = T(2n/3)+ 2 ). If checker is adaptive, how is it not failing this ? Is it that such checker is impossible to prepare ?
1 Like
asking too many queries, so you got a WA(-1.00000)
A single task failed means 0 points for the entire subtask
YOU ONLY GET POINTS IF ALL TESTCASES OF THE SUBTASK ARE PASSED (AC)
BUT NOT EXACTLY …
THIS IS THE DIFFERENCE :
the only restriction is
that, among any k + 1 consecutive answers, at least one answer must be truthful
- Grader says G if x > N , E if x == N and L if x < L.
- Grader can lie (not in consecutive queries)
I was interested to know the algo behind the grader how it managed to keep track of all possible numbers .I guess its also same as the solution of this problem.
maybe forget about the formula. Think about it like this. if you get two continuous G G, then you remove 33\% using 2 queries. If not then you remove \frac{33}{2}\% in 1 query, (approximately).
1 Like