PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ashish Kumar
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh
DIFFICULTY:
To be calculated
PREREQUISITES:
Observation, sorting or dictionaries/maps
PROBLEM:
Chefland consists of N towers, the i-th of which has height H_i. Pushpa can start at any tower, and in one step, jump to any other tower whose height is exactly one more than the current tower.
Each time Pushpa jumps, the height of every tower except the one he lands on increases by 1. What is the maximum height Pushpa can reach?
EXPLANATION:
Hint
Suppose Pushpa’s jumps follow the path i_1 \to i_2 \to \ldots \to i_k. What can you say about the initial values of H_{i_1}, H_{i_2}, \ldots, H_{i_k}?
Full solution
The main idea behind the solution is that Pushpa can follow the path i_1 \to i_2 \to \ldots \to i_k by jumping, if and only if initially, H_{i_1} = H_{i_2} = \ldots = H_{i_k}.
Proof
Let H_{i_1} = X. Then, for Pushpa to be able to jump to tower i_2, it must currently be at a height of X+1. However, notice that its height increased by 1 after Pushpa landed on i_1, which means initially we must have had H_{i_2} = X.
Now look at i_3. It is not possible for i_3 to equal i_1 or i_2 (in fact, it is impossible to jump on the same tower more than once; do you see why?), and it must currently be at a height of X+2, but its height increased by 2 which means that initially, H_{i_3} = X. Continuing in this fashion, we see that every tower in the sequence had height X at the start.
Conversely, given any set of towers all of the same height, it is easy to see that Pushpa can jump on all of them.
With this fact in hand, we have a relatively simple solution: if there are f_X towers of height X and Pushpa starts on one of them, the maximum height he can reach is X + f_X - 1 by jumping on each of these f_X towers once. So, the answer is the maximum value of X + f_X - 1 across all values X such that there is a tower of height X.
All that remains is to find f_X for every X. Doing this in \mathcal{O}(N) for each value of X using a linear scan is of course too slow, but there are several ways to do it faster — for example, by using a map
(C++) /TreeMap
or HashMap
(Java)/dict
(Python), or even by just sorting the array and using a two-pointer technique.
TIME COMPLEXITY:
\mathcal{O}(N\log N) or \mathcal{O}(N) per test.
CODE:
Author (C++, map)
#include <bits/stdc++.h>
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
int main()
{
//READ("1.in");
//WRITE("1.out");
int t;cin>>t;
assert(t>=1 and t<=10);
while(t--){
int n;cin>>n;
assert(n>=1 and n<=100000);
map<long,long>m;
for(int i=0;i<n;i++)
{
int x;cin>>x;
assert(x>=1 and x<=1000*1000*1000);
m[x]++;
}
long ans=0;
for(auto it:m)
{
ans=max(ans,it.first+it.second-1);
}
cout<<ans;
if(t)
cout<<endl;
}
}
Tester (C++, map)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
sort(begin(a), end(a));
int ans = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n and a[j] == a[i]) ++j;
ans = max(ans, a[i] + j - i - 1);
i = j;
}
cout << ans << '\n';
}
}
Editorialist (C++, sorting)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
sort(begin(a), end(a));
int ans = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n and a[j] == a[i]) ++j;
ans = max(ans, a[i] + j - i - 1);
i = j;
}
cout << ans << '\n';
}
}