PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: TheScrasse
Preparer: Aryan Agarwala
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1815
PREREQUISITES:
Prefix sum
PROBLEM:
There are N people (numbered from 1 to N). One of these people is a thief and always lies, the others are honest people and always tell the truth.
Person i claims that the thief is one of l_i, l_{i+1}, l_{i+2}, \cdots, r_i.
How many people could be the thief?
EXPLANATION:
Let’s iterate through each person and check if they could be a thief or not. For the person i to be a thief, two conditions must satisfy:
- The range that this person provide must not include i, i.e. i \notin [l_i, r_i]
- For every other person, the range that they provide must include i, i.e. i \in [l_j, r_j] for all j \neq i.
The first condition is easy to check on the fly, but we need to transform the second condition a bit. That condition is equivalent to: the intersection of the ranges of every other person must include i. This leads us to this observation:
- If we compute the “prefix” intersection (just as we compute the prefix sum of an array), as well as the “suffix” intersection, then we can easily find out the intersection of every person that isn’t i (simply take the intersection of prefix i - 1 and suffix i + 1).
This gives us the solution:
- We first precompute the prefix intersection and the suffix intersection.
- Then for each person i, we check the first condition, then compute the intersection of prefix i - 1 and suffix i + 1 and check whether this range includes i.
TIME COMPLEXITY:
Time complexity is O(N) for each test case.
SOLUTION:
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
typedef pair<int,int> pii;
int n;
pii a[100001];
pii pf[100002],sf[100002];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
cin >> n;
pf[0]=sf[n+1]={1,n};
for(int i=1; i<=n ;i++){
cin >> a[i].fi >> a[i].se;
pf[i].fi=max(pf[i-1].fi,a[i].fi);
pf[i].se=min(pf[i-1].se,a[i].se);
}
for(int i=n; i>=1 ;i--){
sf[i].fi=max(sf[i+1].fi,a[i].fi);
sf[i].se=min(sf[i+1].se,a[i].se);
}
int ans=0;
for(int i=1; i<=n ;i++){
int l=max(pf[i-1].fi,sf[i+1].fi);
int r=min(pf[i-1].se,sf[i+1].se);
if(l<=i && i<=r && (i<a[i].fi || i>a[i].se)) ans++;
}
cout << ans << '\n';
for(int i=1; i<=n ;i++){
int l=max(pf[i-1].fi,sf[i+1].fi);
int r=min(pf[i-1].se,sf[i+1].se);
if(l<=i && i<=r && (i<a[i].fi || i>a[i].se)) cout << i << '\n';
}
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
pair<int, int> add(pair<int, int> a, pair<int, int> b) {
return {max(a.first, b.first), min(a.second, b.second)};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<pair<int, int>> a(n), pre(n), suf(n);
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
partial_sum(a.begin(), a.end(), pre.begin(), add);
partial_sum(a.rbegin(), a.rend(), suf.rbegin(), add);
vector<int> ans;
for (int i = 0; i < n; i++) {
pair<int, int> xd = {1, n};
if (i > 0) {
xd = add(xd, pre[i - 1]);
}
if (i + 1 < n) {
xd = add(xd, suf[i + 1]);
}
if (i + 1 >= xd.first && i + 1 <= xd.second
&& (i + 1 < a[i].first || i + 1 > a[i].second)) {
ans.push_back(i + 1);
}
}
cout << ans.size() << '\n';
for (int v : ans) {
cout << v << '\n';
}
}
}
