# SEGFAULT - Editorial

Setter: TheScrasse
Preparer: Aryan Agarwala
Tester: Harris Leung
Editorialist: Trung Dang

1815

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;
}
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';
}
}
}

5 Likes

I want to know how some O(N^2) solutions got accepted

3 Likes

Binary index tree solution:

• activate all ranges in BIT. (BIT[si]++, BIT[ei+1]â€“)
• for each i check i doesnot belong[Si, Ei]
• deactivate [Si, Ei] range in BIT
• check value at i in BIT == n-1 or not
• if yes then i is thief

https://www.codechef.com/viewsolution/68132656

1 Like

Problem can also be solved without Precomputing the prefix and suffix intersection.
All you need to know is that, how many ranges include index i where (1 <= i <= n).
This can be done by having two vectors:

1. Which keeps all the starting points
2. Which keeps all the ending points

Now, for a particular i,
(A) Check how many points are there whose starting points are less than or equal to i,
&
(B) Check how many points are there whose ending points are strictly less than i.

Then subtract, i.e., A - B, (This gives us the number of ranges in which i is included)
Now, if this number = n - 1, and also the i doesnâ€™t include itself in itâ€™s own range, then person i can be considered as a thief.

My Submission

2 Likes

This is one of those popular questions, when we have to increase subarray of elements by some k and q queries are givenâ€¦
We can do it in linear time using prefix array
Increment range of elements

#include <bits/stdc++.h>
#define int long long int

void solve(){
int n;
std::cin >> n;
int a[n+1] = {0};
std::vector <std::pair<int,int>> p;
for(int i=0; i<n; i++){
int l, r;
std::cin >> l >> r;
p.push_back({l-1, r-1});
a[l-1] += 1;
a[r] -= 1;
}
for(int i=1; i<n; i++)
a[i] += a[i-1];
std::vector <int> t;
for(int i=0; i<n; i++){
if(a[i] == n-1 && !(p[i].first <= i && i <= p[i].second))
t.push_back(i+1);
}
std::cout << t.size() << "\n";
for(auto &i:t)
std::cout << i << "\n";
std::cout << "\n";
}

signed main() {

std::ios::sync_with_stdio(false);
std::cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

int t = 1;
std::cin >> t;
while(t--){
solve();
}
}


Practice problem you can try

5 Likes

1 Like

Can anybody plzz find whatâ€™s wrong with my code, I think it should give AC similar approach to editorial

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod = 1e9 + 7;

void sol(){

int n; cin>>n;

vector<pair<int,int>>pr;

vectorv(n + 2,0);

for(int i = 0;i<n;i++){

int l,r; cin>>l>>r;

pr.push_back({l,r});

lâ€“;

v[l]++; v[r]â€“;

}

for(int i = 1;i<n;i++){

v[i] += v[i-1];

}

setans;

for(int i= 0;i<n;i++){

if(v[i] == n - 1)ans.insert(i+1);

}

for(auto &it : ans){

if(pr[it - 1].first <= it && pr[it-1].second >= it )ans.erase(it);

}

cout<<ans.size()<<"\n";

for(auto &x : ans)cout<<x<<"\n";

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

//sieve();

ll t;

t=1;

cin>>t;

for(int tc = 1;tc<=t;tc++){

//cout<<â€śCase #â€ť<<tc<<": ";

sol();

}

return 0;

}

Itâ€™s never a good idea to do erase while iterating vectorsâ€¦Most of the times throw exceptions and undefined behaviourâ€¦Stackoverflow, Issues while removing item from vectorâ€¦You can try and do it without using erase or use generic for loopâ€¦
In general donâ€™t use range based for loop for modifying vector, use it for iterating only Why canâ€™t erase using auto in for loop?

thank u bro , another bad experience with sets

1 Like

//----------------------------------<https://lnkd.in/eSDbra2>--------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
typedef long long ll;
typedef unsigned long long ull;
ll mod = 1000000007;
#define YES cout<<"YES\n";
#define Yes cout<<"Yes\n";
#define No cout<<"No\n";
#define NO cout<<"NO\n";
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define lcm(a,b) (a/gcd(a,b))*b
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

//----------------------------------Real game starts here--------------------------------------

void solve()
{
ll n;
cin >> n;
vector<int> a(n + 1);
vector<pair<int, int>> b(n);
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
b[0].first = l;
b[0].second = r;
a[l - 1] += 1;
a[r] -= 1;
}
for (int i = 1; i < n; i++)
a[i] += a[i - 1];
vector<int> ans;
for (int i = 0; i < n; i++)
{
if (a[i] == n - 1)
{
if (b[i].first <= i + 1 && i + 1 <= b[i].second)
;
else
ans.push_back(i + 1);
}
}
cout << ans.size() << "\n";
for (auto x : ans)
cout << x << "\n";

}

int main()
{
fast_cin();
ll t = 1;
cin >> t;
for (int it = 1; it <= t; it++)
{
//cout << "Case #" << it+1 << ": ";
solve();
}
return 0;
}

//unordered_map STOP NO WTF ARE U DOING?
//in graph sometimes to get out of loop use set instead of bool check --> ------> in dfs other end will be blocked even u can travel
// on set use set.lower_bound(x) becuase normal lower_bound give On
//33331112222 van moore n/3 intutuion for double minus


Did almost same as you didnt worked for me?

Are you sure ?

1 Like

Really Helpful bro. can you suggest us more websites from where we can learn these types of interesting facts about array manipulationâ€¦OR any other techniques that you know?

How many of you agree that question statement was not very clear.

2 Likes

Actually when I started coding 1.5 years ago, I stumbled across this question on hacker rank. So just remembered this because I could not solve this for daysâ€¦ You can practice more and more questions on gfg, leetcode and give as many contests as you can. Glad you found it useful

3 Likes

Why are you checking a[i]==n-1 instead of max(a)==a[i] ?

Because thief will not tell himself that he is thief, that will be contradiction. And there is only 1 thief, all others speak truth. So all others will point to thief i.e. n-1 peopleâ€™s will say who is thiefâ€¦thatâ€™s why n-1

I had the O(N^2) solution in my mind but didnâ€™t write it as I thought it would give TLE. But after the contest, I saw people getting AC in O(N^2) approach.

Multiple Persons should be there with same probablility

try:
for _ in range(int(input())):
n = int(input())
array = []
for k in range(n):
a,b = map(int,input().split())
for j in range(a,b+1):
if k+1 != j :
array += [j]
c = Counter(array)
c= c.most_common()
ans = []
for item in c :
if list(item)[1] != n-1 :
break
else :
ans.append(list(item)[0])
ans = sorted(ans)
for item in ans :
print(item)

except :
pass

thats my code ,its Giving WA (any help appricated)

guys can someone please! look into to this, i am new to python and i am not able to find the error! its giving me runtime error (NZEC) . I have tried alot to search but i failed to find the error. am i not taking input correctly? is thats what producing the runtime error? i have followed the discussed O(n) approach only of prefix sum method.

My solution link: Solution: 68293254 | CodeChef