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
best editorial i had ever read on code chef till date.
I think you just said it. I wouldn’t know how to prepare a checker to simultaneously block many different strategies. The alternative is not to simultaneously block many strategies, but to “learn” which one is used and block it, but that could be a great effort. Probably, if I were the setter, I wouldn’t do it even if I knew how.
2 Likes
Hey,
Thanks. I get it. It was due to TLE. erasing and copying in vector caused O(n) for each query. Thanks 
Basic assumptions about checker :
-
If you have detetmined that X must be greater or less than some value, checker will always tell truth there.
-
Repeatedly asking for single number will always give alternate answers.
-
Choose the ‘G’ or ‘L’ such that least segment size gets “determined”. In case of equality, choose ‘G’ if integer asked is in left to middle and ‘L’ if it is in right to middle.
-
Answer will become ‘E’ only when the last remaining integer is asked.
I think these are enough to get the worst case of most strategies.
2 Likes
this is a really beautiful way of writing an editorial, great work
I envy you for those 45 points. LOL!