# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Ashish Kumar

*Satyam, Abhinav Sharma*

**Testers:***Nishank Suresh*

**Editorialist:**# 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';
}
}
```