What if I force the grader to lie to a query which I know the answer to, such as N, to which I always know the answer will be L and if it’s reply is G, then it’s a lie and in the next query it will definitely give me a right answer, on which I can just narrow down my range by originally setting the upper limit of my range to N and lower limit of 1. Would it work or not???
My code-
n = int(input())
upper = n
lower = 1
while True:
print(upper)
a1 = input()
if a1=='E':
break
elif a1=='G':
e=(upper+lower)//2
print(e)
k = input()
if k=='E':
break
elif k=='L':
upper = e
elif k=='G':
lower = e
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.
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
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%)
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
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 : )
.