 # PBATTLE - Editorial

Author: Ayush Rusiya
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh

1739

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)

ans=1
curr_max=a[-1]
for i in range(n-2,-1,-1):
if a[i]>curr_max:
ans+=1
curr_max=a[i]

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] > mx:
ans += 1
mx = max(mx, c[i])
print(ans)

1 Like

My Solution

I am rather new . Is there anything I could have modified in my solution such that it would not show TLE error?

My solution

I did the exact same thing, and implemented the solution using maps in c++. Still TLE error? Any help will be appreciated.

learn about time complexity and how to calculate it for the code… time complexity of your code is O(n^2) which is greater than 10^10 given constraints. and in 1sec there can only be 10^7 - 10^8 operations possible

You are iterating over the whole map that is causing the TLE
as it will make the solution close to O(N^2)

I used binary search on a sorted array to skip iterating the whole array

You could also use the DS ordered_set

@iceknight1093
I think this problem’s test cases are very weak.
This( CodeChef) solution’s time complexity is O(n^2).
It should not have passed but it did.
please update the test case if what I am saying is correct;

1 Like

Thanks buddy.

I almost had the same solution in python, but I used too may dictionaries.
I got AC in 2 cases, but for bottom 2 I got RE(error).

Can anyone help.

code