PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ayush Rusiya
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
1739
PREREQUISITES:
Sorting
PROBLEM:
N Pokemon trainers participate in a tournament. Each of them has one Pokemon, with a power of A_i on land and B_i in the water.
Trainer i can defeat trainer j if A_i \gt A_j or B_i \gt B_j. The strength of a trainer is the number of other trainers this trainer can defeat.
All the values of A_i are distinct, as are the values of B_i. Find the number of trainers with maximum strength.
EXPLANATION:
First, note that the maximum possible strength is \leq N-1, since a trainer can only defeat the other N-1 trainers at best.
In fact, the maximum strength will always be exactly N-1.
Proof
Since all the A_i are distinct, consider the trainer with highest A_i value — without loss of generality, less this be A_1.
Now, trainer 1 can beat every other trainer on the ground, and thus has a strength of N-1. So, there is always a trainer with strength N-1, as required.
Now that we know the maximum strength, all that remains is counting: we need to count the number of trainers with strength N-1. Of course, doing this with brute force in \mathcal{O}(N^2) is too slow so we need to be better.
For a trainer to have a strength of N-1, he must be able to defeat every other trainer, either on land or in water.
Suppose we sort the pairs of (A_i, B_i) so that A_1 \lt A_2 \lt \ldots \lt A_N. Now, note that trainer i can surely defeat any trainer j with j \lt i on land, so we don’t have to care about B_j for j \lt i.
So, for trainer i to have a strength of N-1, B_i must be larger than all of B_{i+1}, B_{i+2}, \ldots, B_N — all of these trainers beat trainer i on land, so they must lose in the water for i to have a strength of N-1.
Note that the condition on B_i can be rephrased as B_i \gt \max(B_{i+1}, B_{i+2}, \ldots, B_N).
This gives us a rather simple algorithm:
- Sort the pairs (A_i, B_i) in increasing order of A_i.
- Iterate i in decreasing order, from N to 1. Keep a variable mx to denote the current maximum value of B_i.
- At position i, if B_i \gt mx, add 1 to the answer.
- Then, set mx \gets \max(mx, B_i).
TIME COMPLEXITY
\mathcal{O}(N\log N) per test case.
CODE:
Setter's code (Python)
# cook your dish here
for i in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a=[(a[i],b[i]) for i in range(n)]
a.sort(key=lambda x:x[0])
ans=1
curr_max=a[-1][1]
for i in range(n-2,-1,-1):
if a[i][1]>curr_max:
ans+=1
curr_max=a[i][1]
print(ans)
Tester's code (C++)
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
#define fbo find_by_order
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
int sum = 0;
int solve(){
int n = readIntLn(2,1e5);
sum += n;
assert(sum <= 2e5);
vector<int> a = readVectorInt(n,1,1e9);
vector<int> b = readVectorInt(n,1,1e9);
auto check_distinct = [&](auto a){
set<int> st;
for(auto i:a)st.insert(i);
assert(sz(st) == sz(a));
};
check_distinct(a);
check_distinct(b);
vector<int> ord(n);
iota(all(ord),0);
sort(ord.begin(),ord.end(),[&](auto &i,auto &j){
return a[i] < a[j];
});
Tree<int> tr;
vector<int> res(n);
for(int i = n - 1; i >= 0; i--){
res[ord[i]] = i + tr.ook(b[ord[i]]);
tr.insert(b[ord[i]]);
}
int mx = *max_element(all(res));
cout << count(all(res),mx) << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t = readIntLn(1,1000);
while(t--){
solve();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [(a[i], b[i]) for i in range(n)]
c.sort()
ans, mx = 0, 0
for i in reversed(range(n)):
if c[i][1] > mx:
ans += 1
mx = max(mx, c[i][1])
print(ans)