HEIGHTS-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter:Tejas Pandey
Tester: Manan Grover, Abhinav Sharma
Editorialist: Devendra Singh

DIFFICULTY:

1390

PREREQUISITES:

None

PROBLEM:

Chef is teaching his class of N students at Hogwarts. He groups students with the same height together for an activity. Some of the students end up in a groups with only themselves and are saddened by this.

With the help of his magic wand, Chef can increase the height of any student to any value he likes. Now Chef wonders, what is the minimum number of students whose height needs to be increased so that there are no sad students?

EXPLANATION:

For all students we first need to find how many students are going to end up in a group with only themselves which is same as counting students with unique heights. Let K be the number of students which have a height H such that count of H in the array is 1.
Now there are four cases :

  • K=1 and H is not the maximum height of all the students: The answer is 1 in this case , just increase the height of this particular student to the maximum value of heights of all students.
  • K=1 and H is the maximum height of all students but there exists a group of at least 3 students grouped together: The answer is 1 in this case just pick any student from any group with at least 3 students and increase his/her height to the maximum height of all students.
  • K=1 and H is the maximum height of all students and all groups consist of 2 students only. In this case the answer cannot be less than 2 as increasing any students height to the maximum height still results in a student who has a unique height. Thus we need to increase the height of at least 2 students to the maximum height of all students in this case.
  • K>1 : The answer is ceil((K+1)/2) in this case. If K is even we can form K/2 pairs by increasing the height of students.(Sort the students according to height, increase the height of first student to make it equal to second students height and so on from the third student). If K is odd form (K-3)/2 pairs and perform 2 operations to a make of group 3 students (Sort the students according to height, increase the height of first and second student to make it equal to third student’s height and then follow the same method for even case).

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    //freopen("inp7.in", "r", stdin);
    //freopen("out7.out", "w", stdout);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        map<int, int> cnt;
        int a[n], mx = 0;
        for(int i = 0; i < n; i++) cin >> a[i], mx = max(mx, a[i]), cnt[a[i]]++;
        int bad = 0, g2 = 0, largest = 0;
        for(int i = 0; i < n; i++) {
            if(cnt[a[i]] == 1) {
                bad++;
                if(mx == a[i]) largest = 1;
            }
            else if(cnt[a[i]] > 2) g2++;
        }
        if(bad == 1) {
            if(g2 || !largest) cout << 1 << "\n";
            else cout << 2 << "\n";
        } else cout << (bad + 1)/2 << "\n";
    }
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n, cnt = 0, gp3 = 0;
    cin >> n;
    map<int, int> mp;
    vll v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        mp[v[i]]++;
    }
    sort(all(v));
    for (auto x : mp)
    {
        if (x.S == 1)
            cnt++;
        if (x.S > 2)
            gp3++;
    }
    if (cnt ==1 && !gp3 && mp[v.back()]==1)
    {
      cout<<2<<'\n';
      return ;
    }
    cout << (cnt + 1) / 2 << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

2 Likes

The reason why a lot of people might have got WA’s in the start , is they neglected “increase” word in the problem statement and hence missing out on the edge case of K = 1 that only person having the maximum height. Can be quite annoying at times when you miss out such simple yet so crucial thing.

5 Likes

1 missed the 3 rd case (group three count)

According to the right answers, the test case of with n = 9 and if the array is 1 2 1 2 5 6 7 8 9 it gives 4 but it should 3, so, Please all check the problem, and help me.

The According to the right answer the tester is wrong then, if the size of the array is 9 and
the array is 1 2 1 2 5 6 7 8 9 the ans might 3 because change the height 5 to 6 and 7 and 8 to 9 but
in the right answer according to codechef, that comes 4 so i think it is a wrong qs
or say due to lack of attention by the tester


Can some please explain me this test case.

On test case 5 2 2 2 2 my code gives the answer 2. It’s supposed to be 1 though and my code got an AC in the contest.

@c_adept - the problem asks us to increase the height.
In this case - ‘2’ is the only student who is alone
We can take 1 student whose height is ‘1’ and make it ‘2’. The new heights will be 1 1 1 1 2 2 which will make all students happy.

yup, the test cases are incomplete…this same problem happened to me

How to see the failed test cases??

i didnt understand the last case , for odd numbers

Can you someone let me know what is test case number 5? Because I have all other test cases accepted, and I don’t know why test case 5 is failing.

Hey - @soniic99 - run your submission and when you get WA - click on ‘debug my code’ you will realize which test case your code failed on in this problem

Only one test Case is failing. Not getting what I have missed.

Problem Link :- CodeChef

{
	ll n;
	cin >> n;

	vector<ll> v(n);

	unordered_map<ll, ll> mp;

	for ( ll i = 0 ; i < n ; i++)
	{
		cin >> v[i];
		mp[v[i]]++;
	}

	debug(mp);

	vector<ll> x;

	for (auto it : mp)
	{
		if ( it.second == 1)
		{
			x.push_back(it.first);
		}
	}

	int ans = 0;

	if (x.size() == 0)
	{
		ans = 0;

	}
	else if ( x.size() == 1  )
	{
		ans = 1;
	}

	else if ( x.size() >= 4)
	{
		if ( x.size() % 2 == 0)
		{
			ans =  x.size() / 2 ;
		}
		else
		{
			ans = ((x.size() +1) / 2) ;
		}
	}
	else
	{
		ans =  x.size() - 1 ;
	}


	cout << ans << "\n";
}
2 Likes

There is a special case when there is only one person with unique height, and if u see it was mentioned in the problem statement that we can only “increase” the height so we cannot change it to some lower value.

Consider the example n = 3 , A = [2 , 2 , 3]
Your code will output 1
correct answer is 2

I tried to do changes in my code according to your test case but still giving me wrong ans can u plz what changes should i do . and can u give me your discord or linkedin id


Can some one help me to know this test case
I think my answer is right.

n = 6, A = [1 1 1 1 1 2]
Your Answer:
5
Correct Answer:
1

Reason: [1 1 1 1 2 2] is valid.

can u plz tell me what changes should i do in my code