Wow, that’s funny. Early in the contest I made a submission along those lines and failed on the second-to-last subtask in Group 4…
First query is 0.5n. Let the answer be L.
Second query is yn.
If the answer is G, then there is third query before starting over and it is 0.25n.
Coefficient y satisfies equation y^3 = (1.25-y)^2. The solution is approximately 0.684135, which is more than 2/3.
how to perform query when we delete a specific subset i mean whats the flow of performing query
just like you , i also did . i also got the same result …
I DID NOT UNDERSTAND , AFTER THE FIRST STEP , HOW DO YOU FIND THE NEXT NUMBER TO BE QUERIED !
auto size = &{
int len = 0;
for(auto e : ranges) len += e.second - e.first + 1;
return len;
};
here what is auto size =&{}//means
Well, now we are effectively removing \{\frac{1}{4} \} of the search space for every 2 queries that we make. This solution is intended to give up to 75pnts.
can someone please explain me how to jump to such conclusions from reading the constraints?
i thought it would be \log_{4/3}{N} which is very less than 300
i also did tried the same thing now CodeChef: Practical coding for everyone
but i got 0 points
My guess based on the descriptions given is that the grader works with a similar implementation to a good solution - maintaining a list of answers consistent with its answers so far, and then giving a ‘G’ or ‘L’ response either consistent with the list or randomly chosen if it’s allowed to lie this turn, saying “E” when it’s finally reduced to a list consisting of a single number.
If the grader had a number fixed in advance, it would probably lead to “hack” solutions that figured out which of the finite number of test cases they were in, and went straight to the right number, or to “lucky” solutions whose implementation happened to guess the number earlier than expected on a particular test run.
A smarter grader could have used a heuristic to decide when to lie (with the result that if guesser keeps guessing ‘1’ it will keep responding ‘G’ to avoid being caught in an obvious lie), but based on comments about solutions that got accepted, that clearly wasn’t the case THIS TIME. One such heuristic would be to say ‘G’ or ‘L’ with probabilities based on the number of elements in each list (which would be the same probability distribution as if a single number had been picked in advance and no lying was occurring).
-1 means my program is not stopping , running forever
0 means your program is stopping after k = 120
okay thanks
welcome
I updated my implementation to one that I believe optimal for all reasonable values of N.
https://www.codechef.com/viewsolution/34682829
For the problem given, this should always complete within K=95 (an exhaustive search later confirmed this should even work for K=93 depending on how the judge enforces the K limit)
The exact ratio to use is optimised based in part on the golden ratio - if all numbers compatible with the last response were listed Q times, and all numbers incompatible with the last response were listed Q * 2.618034 times (golden ratio squared), then we should guess the median of this list.
A more precisely-specified version could probably be created using lists of known Fibonacci sequences.
Here is my 75% points code…
https://www.codechef.com/viewsolution/34408542
what should i change in this to get 100%?
1 Like
Can someone explain How to come up with a reduction factor of 33% seeing n and maximum queries (120) possible?
1 Like
I don’t understand how do you remove 2nd section (or any section somewhere in the middle) ? If we remove 1st section then we can call next recusion(n/3,n).
I tried this recursion(1,n/3) and recursion(n/2,n). One of these two is the wrong section for sure and that takes too many queries inside that recursion.
This question had almost fried my head 
. Great editorial!! 