ELOMAX - Editorial

PROBLEM LINK:

Practice
Contest
Video Editorial

Setter: Akash Bhalotia
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Simple

PREREQUISITES:

Ad-hoc and Sorting.

PROBLEM:

There are N players each having some initial rating, there is a tournament held for M months and rating change for each player is given after the ith month of the tournament. You have to count the number of players whose month of highest rating(in case of multiple months choose the first month after he reached the highest rating) and month of best rank(in case of multiple months choose the first month in which we achieved the best rank) are different.

EXPLANATION:

You have given the initial rating of each player, his rating after the first month is given by initial rating + rating change for first month, for second month it is given by rating after first month + rating change for second-month, and so-on. After computing the rating for each month for each player you can compute the 1^{st} month when he reached the maximum rating.(Note you don't have to consider the initial rating of the players). In this way, you have computed the month in which the player reached his highest rating for each player. Now to compute the first month when a player has the best rank let us compute the ranking of each player after each month and again find the first minimum(Why? because smaller the rank the better) for each player. Let us do this by considering rating of the people after each month and then sort them in descending order of there rating(To know which rating belongs to which person you can an array of pairs {rating of ith player, i} and then sort this array)

vector<pair<int, int>> rating_ID(N); // to store the pair as {rating of ith person, i}, we will sort it to compute rank.
for(int i = 1; i <= N; i ++) {
   rating_ID[i-1].first = rating[i][month];
   rating_ID[i-1].second = i;
}
sort(rating_ID.rbegin(), rating_ID.rend()); // to sort it in decreasing order of rating.

Now we have to compute the rank of each player for this month. This can be done by iterating through the descendingly sorted array of pairs and assigning them ranks starting from rank 1. Now things to be noted :

  • You have to assign the same rank to the people with same rating.
  • if there are 6 players with a rating 2000, 2000, 2000, 1800, 1800, 1700 then their corresponding ranks will be (1, 1, 1, 4, 4, 6) Note the rank of the players, I think many people made the mistake in computing ranks
int cur_rank = 1, prev = rating_ID[0].first, next_rank = 2;
for(int i = 0; i < N; i ++) {
	if(prev == rating_ID[i].first) { // as there can be multiple person with same rank.
		rank[rating_ID[i].second][j] = cur_rank;
		next_rank ++;
	}
	else {
		cur_rank = next_rank;
		next_rank ++;
		rank[rating_ID[i].second][j] = cur_rank;
		prev = rating_ID[i].first;
	}
}

And after computing the first month in which ith player reached the best rating you can simply compute the answer by counting the number of players whose month of highest rating(in case of multiple months choose the first month after he reached the highest rating) and month of best rank(in case of multiple months choose the first month in which we achieved the best rank) are different.

TIME COMPLEXITY:

  • Time taken for computing the highest rating for each player O(N*M) and to compute best ranking O(N*M*\log{N}). So total time complexity per test case is O(N*M*\log{N}).

SOLUTIONS:

Setter's Solution
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
    static class Pair implements Comparable<Pair>
    {
        int f, s;
        Pair(int f, int s){this.f = f;this.s = s;}
        public int compareTo(Pair b){return Integer.compare(b.s,this.s);}
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,j,N;

        int T=Integer.parseInt(br.readLine().trim());
        StringBuilder sb=new StringBuilder();

        while(T-->0)
        {
            String[] s=br.readLine().trim().split(" ");
            N=Integer.parseInt(s[0]);
            int M=Integer.parseInt(s[1]);

            int[][] ratings=new int[N][M];
            int[] cur=new int[N];
            s=br.readLine().trim().split(" ");
            for(i=0;i<N;i++) cur[i]=Integer.parseInt(s[i]);

            for(i=0;i<N;i++) //calculating ratings after each month
            {
                s=br.readLine().trim().split(" ");
                ratings[i][0]=cur[i]+Integer.parseInt(s[0]);

                for(j=1;j<M;j++) ratings[i][j]=ratings[i][j-1]+Integer.parseInt(s[j]);
            }

            int[][] rankings=new int[N][M];
            ArrayList<Pair> list=new ArrayList<>();

            for(i=0;i<M;i++) //calculating rankings after each month
            {
                list.clear();
                for(j=0;j<N;j++) list.add(new Pair(j,ratings[j][i]));
                Collections.sort(list);

                int prevRate=list.get(0).s,prevId=0;
                for(j=0;j<N;j++) 
                {
                    int id=list.get(j).f;
                    if(list.get(j).s==prevRate) rankings[id][i]=rankings[prevId][i];
                    else rankings[id][i]=j;

                    prevRate=list.get(j).s;
                    prevId=id;
                }
            }

            int count=0;
            for(i=0;i<N;i++)
            {
                int rateMonth=0,best=0;
                for(j=0;j<M;j++) //finding month of peak rating for player i
                {
                    if(ratings[i][j]>best)
                    {
                        best=ratings[i][j];
                        rateMonth=j;
                    }
                }

                int rankMonth=0; best=N+10;
                for(j=0;j<M;j++) //finding month of peak ranking for player i
                {
                    if(rankings[i][j]<best)
                    {
                        best=rankings[i][j];
                        rankMonth=j;
                    }
                }

                if(rateMonth!=rankMonth) count++;
            }

            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int 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;
			}
			assert(l<=x && x<=r);
			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 pre(){


}
int a[509][509],r[509][509];
int rnk[509][509];
int pkm[509],pkr[509];
void solve(){
	int n=readIntSp(1,50);
	int m = readIntLn(1,50);
	rep(i,n-1) r[0][i] = readIntSp(1800,2800);
	r[0][n-1]=readIntLn(1800,2800);
	rep(i,n){
		rep(j,m-1){
			a[j][i]=readIntSp(-20,20);
		}
			a[m-1][i]=readIntLn(-20,20);
	}
	rep(i,n) rep(j,m) r[j+1][i]=r[j][i]+a[j][i];
	rep(i,m+1){
		vector<pii> s;
		rep(j,n) s.pb(mp(r[i][j],j));
		sort(all(s));
		reverse(all(s));
		rnk[i][s[0].snd]=1;
		repA(j,1,sz(s)-1){
			if(s[j].fst==s[j-1].fst) rnk[i][s[j].snd] = rnk[i][s[j-1].snd];
			else rnk[i][s[j].snd] = j+1;
		}
	}
	int ans = 0;
	rep(j,n){
		int rt =-1e9;pkr[j]=0;
		int rn =1e9;pkm[j]=0;
		repA(i,1,m){
			if(r[i][j]>rt) rt=r[i][j],pkr[j]=i;
			if(rnk[i][j]<rn) rn=rnk[i][j],pkm[j]=i;
		}
		if(pkr[j]!=pkm[j]) ans++;
	}
	cout<<ans<<endl;

}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int n=readIntLn(1,10);
	rep(i,n) solve();
	assert(getchar()==EOF);
	return 0;
}


Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solveTestCase() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> rating(N+1, vector<int>(M+1)); // rating of ith player after jth month.
	vector<int> max_rating_reached(N+1); // to store the month after which ith player has the maximum rating. And in case of multiple month store the first month.
	vector<vector<int>> rank(N+1, vector<int>(M+1)); // to store the rank of ith player after jth month.
	vector<int> best_rank_reached(N+1); // to store the month in which ith player has the best rank. And in case of multiple month store the first month.

	for(int i = 1; i <= N; i ++) {
		cin >> rating[i][0];
	}
	for(int i = 1; i <= N; i ++) {
		for(int j = 1; j <= M; j ++) {
			int delta;
			cin >> delta;
			rating[i][j] = rating[i][j-1] + delta;
		}
		int maxRat = -100000, id = -1;
		for(int j = 1; j <= M; j ++) {
			if(maxRat < rating[i][j]) {
				maxRat = rating[i][j];
				id = j;
			}
		}
		max_rating_reached[i] = id;
	}
	for(int j = 1; j <= M; j ++) {
		vector<pair<int, int>> rating_ID(N); // to store the pair as {rating of ith person, i}, we will sort it to compute rank.
		for(int i = 1; i <= N; i ++) {
			rating_ID[i-1].first = rating[i][j];
			rating_ID[i-1].second = i;
		}
		sort(rating_ID.rbegin(), rating_ID.rend()); // sorting in decreasing order.
		int cur_rank = 1, prev = rating_ID[0].first, next_rank = 2;
		for(int i = 0; i < N; i ++) {
			if(prev == rating_ID[i].first) { // as there can be multiple person with same rank.
				rank[rating_ID[i].second][j] = cur_rank;
				next_rank ++;
			}
			else {
				cur_rank = next_rank;
				next_rank ++;
				rank[rating_ID[i].second][j] = cur_rank;
				prev = rating_ID[i].first;
			}
		}
	}
	for(int i = 1; i <= N; i ++) {
		int bestRank = 100000, id = -1;
		for(int j = 1; j <= M; j ++) {
			if(bestRank > rank[i][j]) {
				bestRank = rank[i][j];
				id = j;
			}
		}
		best_rank_reached[i] = id;
	}
	int ans = 0;
	for(int i = 1; i <= N; i ++) {
		if(best_rank_reached[i] != max_rating_reached[i]) ans ++;
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int testCase;
	cin >> testCase;
	for(int i = 1; i <= testCase; i ++) {
		solveTestCase();
	}

	return 0;
}

Video Editorial

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

2 Likes

for ranking part we can simply use the ArrayList to store all the ratings monthly wise then we can sort that list in descending order then we can put the rating and corresponding ranking in HashMap and the we can simply store the the ranking in ranking table by looking the HashMap .Once we get the ranking table . we simply traverse through it and find the max ranking student student get in which month.

link to my solution:-https://www.codechef.com/viewsolution/37362850

1 Like

Please help me why i am getting wrong answer as my appraoch is same as that of the editorial

Solution link : https://www.codechef.com/viewsolution/37369718

here mm is the array which contains the month of max rating for each player.

Can anyone help me with a counter testcase for my WA submisstion?

My Approach

  1. store the max rating of each row in the mrating array of size n.

  2. sort each column and find rankings as said in the editorial and store the ranks in a matrix (say brr here)

  3. find the max rank in each row ( of brr matrix) and store it in array of size n .

  4. for( in each row){

         for(in each col)  map each of the highest rating to 1;
    
         for(in each col)
    
               if(check if the corresponding map (mp[j]) !=1  && higest ranking occurrs at that positon){
    
                        then ans++ and break;
    
             }
    

    }

So that if there is any map which is not mapped to 1 and there is a minimum rank at that jth place then ans is incremented and we continue to check the same for next row.

I tried this question for hours, but still got WA for the approach mentioned in the above comment.
@psychik, the Tester’s solution is giving SIGABRT when I copy paste and submit it.
I see that the Editorialist’s solution is giving a incorrect output for the testcase I created which gives correct output for my answer .
Here’s the testcase
`
1

2 3

2980 3000

20 -20 20

-20 -20 20
`
and the ratings are
3000 2980 3000
2980 2960 2980

here the ranks are
111
222
Both player satisfies the output condition.
For each test case, print the number of players whose peak ratings did not occur in the same month as their peak ranking, in a new line.

I maybe wrong in some other testcases, if any then can anyone provide a testcase?

For peak rating, you have to find the first month i in which the player has reached its peak rating. Similarly you have to find the first month j in which the player has best rank. And you have to add 1 to the answer if (i != j).

1 Like

Oh, I didn’t see that :sweat_smile:. Thank you.

https://www.codechef.com/viewsolution/37329892
same as all the others said , I did exactly like it is given in editorial :smile:. It does have a mistake somewhere , that I am sure of. I spent literally 1 hour(:cry:) trying to debug this during the contest and another 2 afterwards (:sob:). As my good friend mallela says, “To your eyes, your code seems perfect. But to another, every error just stands out clear and outright”.
As for the question it is very time taking for sure :roll_eyes:.

1 Like

I don’t know about any other errors but your code it printing some unnecessary things starting at line 85, which result in WA.

for(i=0;i<m;i++){
   cout<<"\nmonth "<<i+1<<"\n";
   for(j=0;j<n;j++){
       cout<<rate[i][j]<<"\t";
   }
   cout<<"\n";
   for(j=0;j<n;j++){
       cout<<rank[i][j]<<"\t\t";
   }
}
1 Like

Can anyone please explain to me why my code is giving WA for even 50 points, when I followed the same approach as the Editorialist, just in place of vectors I used arrays.
I have tried various test cases including cases in this discussion present and I get correct output but still, I get WA. Your little help will be very appreciated. Thank You

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define bs binary_search
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define For(i,a,b) for(int i=a; i>=b ;i–)
#define mem(a,b) memset(a,b,sizeof(a))
#define setprec(x) cout << fixed << setprecision(x);
#define one(x) __builtin_popcount(x)
#define endl “\n”
#define mod 1000000007
void solve()
{
ll int n, m, cnt=0;
cin >> n >> m;
ll int arr[n][m], inirt[n+1]={0}, rnk[n][m];
mem(rnk,0);
FOR(i,0,n) cin >> inirt[i];
FOR(i,0,n)
{
FOR(j,0,m)
{
cin >> arr[i][j];
}
}
FOR(i,0,n)
{
FOR(j,0,m)
{
if(j==0)
arr[i][j]=arr[i][j]+inirt[i];
else
arr[i][j]=arr[i][j-1]+arr[i][j];
}
}
FOR(i,0,m)
{
ll int temp[n+1]={0}, k=1;
FOR(j,0,n)
{
temp[j]=arr[j][i];
}
sort(temp,temp+n);
For(l,n-1,0)
{
FOR(j,0,n)
{
if(arr[j][i]==temp[l] && rnk[j][i]==0)
{
rnk[j][i]=k;
k++;
}
}
}
ll int p=1;
For(l,n-1,1)
{
if(temp[l-1]==temp[l])
{
rnk[p][i]=rnk[p-1][i];
p++;
}
else
p++;
}
}
FOR(i,0,n)
{
ll int mx=0, mn=INT_MAX, x=0, y=0;
FOR(j,0,m)
{
if(arr[i][j]>mx)
{
mx=arr[i][j];
x=j;
}
if(rnk[i][j]<mn)
{
mn=rnk[i][j];
y=j;
}
}
if(x!=y)
cnt++;
}
cout << cnt << endl;
}
int main()
{
IOS;
ll int t;
cin >> t;
while(t–)
solve();
return 0;
}

Sorry for this messed up code, This is my first time asking doubts in discussion for better understanding of code click this link.

Thanks for pointing it out, I forgot to comment it :smile: It’s ACnow :partying_face:

1 Like