You use “eliminate” again and again…how do we know the judge is not lying? If we don’t, how can we completely eliminate the possibility?
One of the best tutorials I have ever seen 
1 Like
I was a bit confused in the problem statement since it said that Alice cannot lie two times in a row. So why can’t we just query each point twice? If Alice’s next response is the same as her previous response, then we know that she wasn’t lying. Otherwise, she was.
We cant do that. Suppose Alice first says L , then says G, on the same point query. How do you know which was the truth ? If Alice keeps alternating between L and G, you would never know the correct direction.
Can anybody point out where am I going wrong, I am aiming for the 75 points task.
ll askQ(ll N) // To ask queries
{
cout << N << '\n';
cin >> ch;
if (ch == 'G')
return 1;
else if (ch == 'L')
return -1;
else
exit(0);
}
struct Interval
{
ll start, end;
Interval(ll a, ll b) : start(a), end(b){};
void print()
{
cout << "\t\t" << start << ' ' << end << '\n';
}
};
void solve()
{
ll n, i, j;
cin >> n;
ll l = 1, h = n, mid = l + (h - l) / 2, a1, v, p;
queue<Interval> range;
range.emplace(1, n);
while (!range.empty())
{
Interval cur = range.front();
l = cur.start;
h = cur.end;
// cur.print();
mid = l + (h - l + 1LL) / 2LL;
a1 = askQ(mid);
range.pop();
if (l == h)
continue;
if (a1 == -1LL)//less than mid
{
v = mid + ((h - l + 1LL) / 4LL);
p = askQ(v);
if (p == -1LL)//less than 3 quartile
{
if (v - 1LL >= l)
range.emplace(l, v - 1LL);
}
elsel//more than 3 quartile
{
if (mid - 1LL >= l)
range.emplace(l, mid - 1LL);
if (v + 1LL <= h)
range.emplace(v + 1LL, h);
}
}
else// more than mid
{
v = mid - ((h - l + 1LL) / 4LL);
p = askQ(v);
if (p == 1LL)// more than 1st quartile
{
if (v + 1LL <= h)
range.emplace(v + 1LL, h);
}
else //less than 1st quartile
{
if (v - 1L >= l)
range.emplace(l, v - 1LL);
if (mid + 1 <= h)
range.emplace(mid + 1LL, h);
}
}
}
}
@arthurfn @rajarshi_basu I have a doubt. Let us suppose the judge says truth 2 times continuously. Suppose the correct number is 45 which we need to guess. And the range is 1-100. So first we make a query X=50. Now X>45 so alice gives G as the answer. Now we query at X=25. Suppose alice tells truth this time as well so since X<45, answer returned will be L. Now according to the above logic if we get G and then L we will remove the interval 25-50 right ? So don’t you think our correct interval is removed in case of judge telling the truth 2 consecutive times ?