# PROBLEM LINK:

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

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

@djaycoding can you please explain your approach

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