LFEB14B - Editorial

editorial
, , , ,
1

Problem Link: contest, practice

Difficulty: Cakewalk

Pre-requisites: Implementation, Maths

Problem:

We are given array A[], that consists of N integers. We need to count the number of subsets of A[], whose arithmetical mean is maximal. Arithmetical mean of an empty subset is undefined.

Explanation:

Let’s define MAX-VALUE as the maximal number of A[].

The answer is two to the power NUM-MAX-VALUE minus one, where NUM-MAX-VALUE is the number of times MAX-VALUE appears in A[].

Let’s have a look why the previous statement is correct.

Arithmetic mean of a set of numbers is smaller than or equal to the maximal number. Then, any subset of A[], that contains only numbers that are equal to MAX-VALUE, is suitable and gives the maximal arithmetical mean, which equals to MAX-VALUE.

At the same time, if there is one number chosen, that is smaller than MAX-VALUE, then the arithmetical mean would be smaller than MAX-VALUE.

That’s why the answer is 2^NUM-MAX-VALUE - 1.

Why we should subtract 1? Because one of the subsets, that we have counted, is empty. We mustn’t consider it as a subset, that gives the the maximal arithmetical mean.

Setter’s Solution: link

Tester’s Solution: link

5 Likes
2

why is my solution not getting submitted for larger values of n, i.e, the 2nd and 3rd subtask

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,maxVal,maxCnt;
        cin>>n;
        int* arr=new int[n];
        for(int i=0;i<n;i++)
            cin>>arr[i];
        maxVal=arr[0];
        maxCnt=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==maxVal)
                maxCnt++;
            if(arr[i]>maxVal)
            {
                maxVal=arr[i];
                maxCnt=1;
            }
        }
        int mod=1000000007;
        int ans=1;
        for(int i=0;i<maxCnt;i++)
            ans*=2;
        if(ans>=mod)
            ans-=mod;
        ans--;
        cout<<ans<<endl;
    }
}
3

You use function pow() from math.h library. For this problem, it is unacceptable. You should either write your own function pow(), which can process all calculations modulo 100000007, or just use a loop for counting the answer.

4

Another one who doesn’t know the difference between C and C++. C has no iostream library, C++ has no math.h (it has cstdio instead).

5

@xellos0 I agree with your point that c has no iostream library but c++ has math.h library, check this link in C++11, C++ maintains backword compatibility for its library.

6

Forgive me for this noobish question … Why 2^(number of occurences)? Why not any other number instead of 2?

7

Because the number of different subsets of an N-element set is 2 to the N’th. The logic is that each element you can either include to the current subset or not include.

8

@kostya_by why did you say that i don’t know the difference between c and c++ ?
i have used the correct libraries as mentioned by @xellos0

9

@xellos0 why is it that the pow function cannot be used here? the question statement didn’t mention any such condition.

10

@xellos0 i have updated the code but it is still not working for case2 and case3

11

@kostya_by please tell me the answer…

12

@insaynasasin, the point is that in the current problem you are asked to do all the calculation modulo 10^9 + 7. As far as 32-bit integers cannot fit 2^100000 itself, we can’t just calculate 2^100000 by a loop and then find the reminder of dividing by 10^9 + 7. We need to go smarter. I.e. each time you twice your answer, make it modulo 1000000007.

13

I think the question was not explained properly…nor the test cases were enough for better understanding of the question…the statement of question clearly mentioned that we have to delete some(not all) elements of the array such that arithmetic mean of the REMAINING elements are as big as possible…instead it should be “we have to delete some (or none) elements of the array such that the arithmetic mean of the DELETED elements are as big as possible”…due to the statement not mentioned properly, I submitted 4 wrong solutions…finally submission was successful when I read the comments and modified my answer.

2 Likes
14

I’m not sure what do you mean, but I would say, and correct me if I’m wrong, that the statement was highly understandable.

There was no long legend, just a mathematical description of the problem. “Sereja wants to delete some(possible none, but not all) elements from the array, such that arithmetical mean of all remaining numbers will as big as possible.” It doesn’t seem clear for you? Why?

If you aren’t satisfied with this editorial, then, please, can you describe what exactly you don’t like? Maybe you would suggest some improvements?

2 Likes
15

The question said “Keeping the arithmetic mean maximal”, does that mean that the mean of the remaing elements should be equal to or greater than the mean of the original set? (sorry for noobish question again. I’m very new to all this …)

16

No, it should be as large as possible, even larger than the arithmetical mean of A[], if it’s possible.

17

Getting NZEC don’t know why ? help me

package practice;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.math.BigInteger;

class serejaandsum {

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	int t;

	t = Integer.parseInt(br.readLine());

	int n,occur=0,max=0;

	while((t--)!=0){

		n = Integer.parseInt(br.readLine());

		int[] a = new int[n];

		String input = br.readLine();

		String[] splitedinput = input.split(" ");

		for(int i=0;i<n;i++){

			a[i]=Integer.parseInt(splitedinput[i]);

			if(a[i]>max){

				max=a[i];

				occur=1;

			}

			else if(a[i]==max)

				occur++;

		}

		occur = 1000000;

		BigInteger occurBig = new BigInteger("2");

		BigInteger res = occurBig.pow(occur);

		res = res.subtract(new BigInteger("1"));

		res = res.mod(new BigInteger("1000000007"));

		System.out.println(res);

		occur=0;

		max=0;

	}

}

}

18 
#include
 
 inline int getn(){
int n=0,c=getchar();
while(c< '0'||c>'9')c= getchar();
while(c>='0'&& c<='9')
n = (n<<3)+(n<<1)+c-'0',c= getchar();
return n;
}
 
 
 
int main(){
     int t,n,a,sum=0,max=0,i,y,q=1,j;
    t=getn();
    for(i=0;i<t;i++){
                     n=getn();
                     for(y=0;ymax){
                                                max=a;
                                                sum=1;
                                                }
                                      else if(a==max){
                                           sum++;
                                           }
                                           }
                     
                     for(j=0;j<sum;j++){
                                        q=q*2;
                                        }
                     q--;
                     
                      printf("%d\n",q%1000000007);
                      sum=0; 
                      q=1;
                      max=0;                     
                                           }
   
    return 0;
}
19

i agree with @dhruvsinghal. I understood the problem only after reading comments from the contest page

1 Like
20

It Only SOlves Subtask One !! Don’t Know Whats Wrong ??

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

typedef long long int ll;
using namespace std;

int main()
{
    ll MOD =1000000007LL;
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll>a(n);
        for(vector<ll>::iterator i=a.begin();i<a.end();i++)
        {
            cin>>*i;
        }
        sort(a.begin(),a.end());
        pair<vector<ll>::iterator,vector<ll>::iterator>bounds;
        bounds = equal_range(a.begin(),a.end(),a[n-1]);
        cout<<((ll)pow(2,(bounds.second-bounds.first))-1)%MOD<<endl;
    }
}