PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
N logicians walk into a bar. You know, for each one, whether they want a beer or not — this information is encoded in binary string S.
The bartender asks them, “Does everyone want a beer?”
The logicians reply to this in order, with their only information being knowledge of their own choice and the replies of the people ahead of them.
Can you predict all their replies?
EXPLANATION:
The key to solving this extension of a well-known riddle is understanding when a logician will reply with “Yes” and when the reply is “No”.
A logician will answer the question “Does everyone want a beer?” with “Yes” if and only if it is known that everyone wants a beer.
Further, notice that this implies that only logician N can say “Yes” (if at all); since anyone before that has no information about the ones following them.
To the contrapositive, if it is known that at least one person doesn’t want a beer, a logician can definitively reply with “No”.
If neither pieces of information are known, no conclusion can be made and the response is “IDK” instead.
So, let’s look at logician i.
- If S_i = 0, at least one person (logician i themself) doesn’t want a beer; so the reply will be “No”.
- Otherwise, S_i = 1. Now we consider some more cases.
- If logician i-1 replied “No”, logician i can also reply with “No” — there exists someone who doesn’t want a beer.
- Otherwise, logicians 1 through i-1 don’t know if everyone wants a beer; but they all themselves want a beer. So, if i = N the reply is “Yes”, otherwise it’s “IDK”.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
string s; cin >> s;
int cnt = 0;
for (int i = 0; i < n; i++){
if (s[i] == '0'){
cnt++;
}
if (cnt == 0){
if (i + 1 == n) cout << "Yes\n";
else cout << "idk\n";
} else cout << "no\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
auto __solve_testcase = [&](int testcase) -> void {
int N = input.readInt(1, 100); input.readEoln();
string S = input.readString(N, N, "01"); input.readEoln();
bool need = 1;
vector<string> fac = {"IDK", "YES", "NO"};
for(int i = 0 ; i < N ; ++i) {
need = need && S[i] == '1';
if(need) {
cout << fac[i == N - 1] << '\n';
} else {
cout << fac[2] << '\n';
}
}
};
int no_of_tests = input.readInt(1, 100); input.readEoln();
for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)
__solve_testcase(test_no);
input.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
no = 0
for i in range(n):
no += s[i] == '0'
if no > 0: print('No')
else:
if i+1 < n: print('Idk')
else: print('Yes')