PUSH7PA - Editorial

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';
	}
}

Below is my code for PUSH7PA.
All Test Cases have passed only last Test Case of my code is failing.
What could be the reason? I am unable to get it.

#include<stdio.h>
#include<stdlib.h>
int cmpfunc (const void * a, const void * b) {
return ( (long int)b - (long int)a );
}
int main()
{
int t;
scanf("%d",&t);
long int result[t];
for(int i=0;i<t;i++)
{
long int n;
scanf("%ld",&n);
long int a[n];
long int freq[n];
long int ele[n];
for(long int j=0;j<n;j++)
{
freq[j]=0;
scanf("%ld",&a[j]);
}
qsort(a, n, sizeof(long int), cmpfunc);
long int k=0;
for(long int j=0;j<n;j++)
{
if(j==0)
{
ele[k]=a[j];
freq[k]++;
}
else
{
if(a[j]==a[j-1])
{
freq[k]++;
}
else
{
k++;
ele[k]=a[j];
freq[k]=freq[k]++;
}
}
}
long int r=ele[0]+freq[0]-1;
for(long int l=1;l<=k;l++)
{
if(r<(ele[l]+freq[l]-1))
{
r=ele[l]+freq[l]-1;
}
}
result[i]=r;
}
for(int i=0;i<t;i++)
{
printf("%ld\n",result[i]);
}
return 0;
}

Your code has undefined behavior, specifically, the line freq[k] = freq[k]++; (see here for why).

Replace that line with freq[k] = 1; and your code passes all cases.

In the future, please do try to not abuse the ++ and -- operators like that, there’s a lot of scope for undefined behavior there. Use += 1 and -= 1 instead, those are far safer, and writing safe code makes it easy for you to debug it.

Also, next time please just include a link to your submission when asking for help, rather than posting the code in the comments. As you can see, the formatting and indentation messed up when you pasted it, making it extremely hard to read.

2 Likes

Thank you so much.

I will keep in mind all the points mentioned by you.