TRUTHLIE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N people who always tell the truth, and M people who may or may not.
You will ask X random people among them a question with a binary answer.
Find the minimum X such that no matter which set of X people you ask, and no matter what their responses are, you will always be able to determine the actual answer.

EXPLANATION:

Suppose we ask some subset of X people.
Among these X people, let p of them be truth-tellers and q be (possible) liars.

Then, if p \leq q, we cannot determine the correct answer from their responses.
On the other hand, if p\gt q, we can always determine the correct answer.

Why?

If p\gt q, there are more truth-tellers than liars.
So, no matter what the liars say, the number of correct answers will be strictly more than the number of wrong answers; and from here we can determine the correct answer.

If p \leq q, the liars can answer in such a way that either the correct answer is more frequent, or the wrong answer is more frequent - we have no way to distinguish these cases just by knowing the number of people who give each answer.

So, we need to choose X such that, no matter which subset of X people we ask, there are more truth-tellers than liars.
This is impossible for X \leq 2M (since in the worst case, we end up choosing every liar to ask).
So, we need at minimum X = 2M+1.

On the other hand, there are only N+M people.
So, if 2M+1 \leq N+M (which also means N\gt M) the answer is 2M+1, otherwise it’s -1.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    if n <= m: print(-1)
    else: print(2*m + 1)
2

Hey, can we solve this problem using binary search?

3

why did this didn’t work ???

#include <iostream>
#include<cmath>
using namespace std;

int minimalPeopleToAsk(int n, int m) {
    int total = n+m;
    int half = (total+1)/2;
    if(n>=half){
        // think
        int x = half-m;
        if(x>m) return half;
        else{
            return 2*m+1;
        }
    }
    else return -1;
    
}


int main() {
	// your code goes here
	int t; cin>>t;
	while(t--){
	    int n, m; cin>>n>>m;
	    int result = minimalPeopleToAsk(n,m);
	    cout<<result<<endl;
	}
	return 0;
}
4

If N = M = 1 you print 3 which is clearly wrong.

1 Like
5

damm ok got it :,)