PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: gunpoint_88
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Greedy
PROBLEM:
A cricket team has N players, player i scores \max(i, j) runs if he plays at position j.
You’re given the fall-of-wickets order of the team. What’s the maximum possible score of the team?
EXPLANATION:
This problem is easiest solved by analyzing the process in reverse.
Notice that the last two players are uniquely determined:
- One player is P_{N-1}, the last wicket to fall.
Let this be x. - The other one is the only player who was “not out”, i.e, not present in P.
Let this be y.
One out of x and y has to be the last person in the order, i.e, at position N.
This person is always going to contribute N to the score.
Clearly, it’s thus better to choose the minimum among x and y to be placed there; since the other one can provide a higher score at earlier indices.
Let z = \max(x, y) be the player who isn’t chosen.
Notice that we now have a rather similar situation for who the (N-1)-th player is:
- It can be z, who isn’t out yet; or
- It can be P_{N-2}, the second-last player to get out.
Once again, it’s optimal to choose the minimum of them; and then we enter a similar state for the (N-2)-th player.
This greedy choice continues all the way to the first player, where we’ll have only one choice.
That is, our algorithm is as follows:
- We fix players in reverse order; i.e, iterate i from N to 2.
- Let x and y be the candidates for the current slot.
Initially, x = P_{N-1} and y is the player who doesn’t appear in P at all. - Place \min(x, y) at index i, then:
- Set x = \max(x, y), the unchosen player.
- Set y = P_{i-2}, the previous player who got out.
In the end, there will be a single candidate for i = 1 so place that player there.
Once the positions of all the players are fixed, computing the actual score is easy in \mathcal{O}(N) — you can even do this computation as you’re placing them.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
#ifdef ANI
#include "D:/DUSTBIN/local_inc.h"
#else
#define dbg(...) 0
#endif
/*
limits:
2 <= N <= 3e5
(size of input array is N-1)
*/
ll solution(vector<ll> b, vector<ll> a) {
ll n=a.size();
ll rem=n-1;
for(ll i=0;i<n-1;i++) {
rem^=i^(b[i]);
}
vector<ll> have={rem,-1};
ll ans=0;
for(ll i=n-2;i>=0;i--) {
have[have[1]==-1]=b[i];
ll take=(a[have[0]]<a[have[1]]?0:1);
ans+=max(a[i+1], a[have[take]]);
have[take]=-1;
}
ans+=(have[0]==-1?a[have[1]]:a[have[0]]);
return ans;
}
class Test{
public:
ll n; vector<ll> p; vector<ll> a; ll ans;
Test(vector<ll> p, vector<ll> a={}) {
ll n=p.size()+1;
if(a.empty()) {
a=vector<ll>(n,0);
iota(a.begin(),a.end(),1);
}
this->n=n;
this->p=p;
this->a=a;
this->ans=solution(p,a);
}
};
int main() {
ll t; cin>>t;
while(t--) {
ll n; cin>>n;
vector<ll> p(n-1);
for(ll i=0;i<n-1;i++) {
cin>>p[i];
p[i]--;
}
cout<<Test(p).ans<<"\n";
}
}
/*
1 2 3 4
4 1 2 3
*/
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
x = n*(n+1)//2 - sum(p)
ans, pos = 0, n
for y in reversed(p):
ans += max(min(x, y), pos)
x = max(x, y)
pos -= 1
ans += x
print(ans)