Partial Solution (15 pts)
Just in case someone wants help on how to use the odd-even information to get started.
The trick lies in first querying 1 to check whether evenLie or oddLie pattern is being followed.
Can anyone please tell me why did i get 15 points only as some of the tasks of subtasks 2 and 3 have an AC.
#include<bits/stdc++.h>
using namespace std;
char getResponse(int display){
cout << display << '\n';
string response;
cin >> response;
if(response[0]=='E')exit(0);
return response[0];
}
struct interval{
int s,e,l;
};
struct interval_storer{
vector<interval> v;
int len_v;
int gap(){
len_v = v.size();
int g = 0;
for(int i=0;i<len_v;i++) g+=v[i].l;
return g-1;
}
int findith(int n){
int i=0;
while(i<len_v){
if(n-v[i].l<0)return v[i].s+n;
n-=v[i].l;
i++;
}
}
vector<interval> getFromLeftTill(int n){
int i=0;
vector<interval> temp;
while(i<len_v){
if(v[i].e>n){
if(v[i].s<=n)temp.push_back({v[i].s,n,n-v[i].s+1});
return temp;
}
temp.push_back(v[i]);
i++;
}
}
vector<interval> getFromRightTill(int n){
int i=len_v-1;
vector<interval> temp;
while(i>=0){
if(v[i].s<n){
if(v[i].e>=n)temp.push_back({n,v[i].e,v[i].e-n+1});
reverse(temp.begin(),temp.end());
return temp;
}
temp.push_back(v[i]);
i--;
}
}
};
interval_storer A;
void bs(){
int g = A.gap();
if(g<=8){
for(auto i : A.v){
for(int j=i.s;j<=i.e;j++)char resp = getResponse(j);
}
}
int mid1 = A.findith(g/3);
int mid2 = A.findith(g-g/3);
char resp1 = getResponse(mid1);
if(resp1=='G'){
resp1 = getResponse(mid1);
if(resp1=='G'){
vector<interval> rrr = A.getFromRightTill(mid1);
A.v.clear();
for(auto i : rrr)A.v.push_back(i);
bs();
return;
}
}
char resp2 = getResponse(mid2);
if(resp2=='L'){
vector<interval> lll = A.getFromLeftTill(mid2);
A.v.clear();
for(auto i : lll)A.v.push_back(i);
bs();
}
else{
vector<interval> lll = A.getFromLeftTill(mid1);
vector<interval> rrr = A.getFromRightTill(mid2);
A.v.clear();
for(auto i : lll)A.v.push_back(i);
for(auto i : rrr)A.v.push_back(i);
bs();
}
}
int main() {
int n;
cin >> n;
A.v.push_back({1,n,n});
bs();
}
2 Likes
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
I think your solution is not able to solve the tasks which have big values of n like n = 1e9. I am not sure though but that looks like it.
The grader is adaptive and might always tell the truth if you output N
1 Like
Hii, Can anyone help me understand the editorial where we took care of truth lie situation. Sorry just started with cp.
1 Like
you have to pass each task of a sub task to get accepted.
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.
https://www.codechef.com/viewsolution/34299609
i think mine is so near to soultion but can find whats wrong in this
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
Since the ranges are not continuous, is it ok to use a vector of all the allowed values amd look at the (n/4),(n/2) and (3n/4) values?
June long challenge editorial beginner friendly video explanation with animation and code
Delicious cake (CONTAIN) : Codechef June Long Challenge||The Delicious Cake(CONTAIN) - YouTube
Tom and jerry (EOEO) : CodeChef June Long Challenge||The Tom and Jerry Game!||EOEO - YouTube
Even matrix (EVENM) : CodeChef June Long Challenge||Even Matrix|| EVENM - YouTube
2 Likes
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