PBATTLE - Editorial

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)
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