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. 
. Thank you.
) trying to debug this during the contest and another 2 afterwards (
). As my good friend mallela says, “To your eyes, your code seems perfect. But to another, every error just stands out clear and outright”.
.
It’s ACnow 