Can anyone post a short editorial for EQAVG from August Lunchtime?
Idea is that the required array is always a repetition of a smaller array.
-we count the occurence of every distinct element in input array.
-if no of distinct elements > k, it is not possible to create required array.
-occurence of every element should be >=n/k, else it is still not possible.
-if above conditions satisfied then it is possible to create array.
-make new array B of only distict elements of A.
-sort B according to desc. occurences.
-create a Rep array which is to be repeated for the required ans.
-for every elemnt in B the no. of times it should appear in Rep = x
and x = (k*occurences[B[i]])/n;
-now just repeat the array uptil size N.
Here is my code and it runs on most cases.
But I still got WA.
Here is my code:
#include<bits/stdc++.h>
using namespace std;
map<int ,int>occ;
bool cmp(int a, int b){
return (occ[a]>occ[b]);
}
int main()
{
int t ;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
vector b;
for(int &i:a){cin>>i;occ[i]=0;}
for(int &i:a)if(occ[i]++==0)b.emplace_back(i);
bool yes = true;
int m = b.size();
if(m>k)yes = false;
for(int i = 0; i<m && yes; i++)if(occ[b[i]]<(n/k))yes = false;
if(!yes){cout<<"NO\n";continue;}
sort(b.begin(),b.end(),cmp);
int rep[k];
int kk = 0;
for(int i = 0; i<m; i++)
{
int x = max((k*occ[b[i]])/n,1);
while(x--)rep[kk++]=b[i];
}
for(int i = 0; i<n; i++)a[i] = rep[i%k];
cout<<"YES\n";
for(int i = 0; i<n; i++)cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}
Can anyone tell me what’s wrong with my code.
I used pretty much the same idea in my solution, and got WA. One possible explanation for that, is if the author meant a different definition for arithmetic mean. I asked this question during the contest, and got no answer.
I believe this problem has incomplete and underspecified/underdefined statement. There are at least two possible definitions of what is meant by ‘arithmetic mean’, and they lead to two different semantics and therefore solutions:
- the mathematical definition, which usually produces a real value;
- the definition that uses computer arithmetic, it always produces an integer value.
I would kindly request for CodeChef admins to consider removing this problem from the contest and the ratings. The problem statement should be prepared in a manner that leaves no doubt whatsoever of what the author meant.
Friend, I think it is specified that mean ‘m’ is a real value;
@hungrykoala they have mentioned in the question to choose a real number “m” so i think they meant the mathematical definition only. Regardless, tbh i used pretty much the same logic as above(i know a friend of mine who did the same as well), yet we landed with AC on the last test case and WA on everything else 
Hm, I think you are right, thank you.
However, I can only treat that as a slight evidence of what the author meant. I am still disappointed that these definitions were not explicitly given and stated. Problem setters should do better job in phrasing out their wording and statements, and make sure everything is completely unambiguous.
After all, in mathematics every integer number is also a real number, isn’t it? It is also a complex number, as well as a quaternion. We can go on with this forever, don’t even get me started.
I expected better problem statements.
However, for the sake of being objective, issues like this one are very rare. In the vast majority of the cases, CodeChef problems are fine and well defined.
Another example of a broken problem statement: AND - Editorial - #16 by hungrykoala
It’s funny how this has been there for years, and no-one has spotted that before.
Your logic is wrong.
Here’s a TC on which your algorithm fails
1
10 4
3 3 3 3 1 1 1 2 2 2
I just have a hunch that:
if number of distinct elements = N
N | K
Managed to solve this problem, after a while. Have marked some comments in code, but it might require better articulation for others to understand. Shall update comments later, when time permits, if official editorial gets delayed. For now, my code solution in link
Problem Statement: Refer Equal Average
Problem Analysis:
Given a sequence A1, A2, …, AN. Let, m=N%K; q= N//K i.e., N = q*K + m.
If following arrangement (refer table) exist, we solution exist and answer “YES”, otherwise “NO”
| row # | col 1 | col 2 | …… | col q | col (q+1) |
|---|---|---|---|---|---|
| 1 | B1 | B1 | B1 | B1 | B1 |
| 2 | B2 | B2 | B2 | B2 | B2 |
| . | . | . | . | . | . |
| m | Bm | Bm | Bm | Bm | Bm |
| m+1 | C1 | C1 | C1 | C1 | |
| m+2 | C2 | C2 | C2 | C2 | |
| . | |||||
| k | Ck-m | Ck-m | Ck-m | Ck-m |
Each Bi (i ranges from 1 to m), has to have a frequency of (q+1). Each Cj (j ranges from 1 to (k-m)), has to have a frequency of (q)
- From given array A, make a frequency table. I used Counter in itertools to make the same
- Let’s say every distinct number Dp exist Fp number of times
- If distinct numbers (Dp) is more than k, i.e., p>k, we cannot make form above table. So answer would be “NO”
- For each Fp, find x1 x2 x3 such that Fp = x1 (q+1) + x2 (q+1)(q) + x3 (q). As multiple solution can exist, we need to find x such that we have minimum x1and x2 and maximum x3
- Each Dp has to be placed in x1 rows from 1 to m i.e., rows having B’s in table
- Each Dp has to be placed in x3 rows from (m+1) to k i.e., rows having C’s in table
- Now we have additional flexibility to
- Either place x2 (q+1) rows of C’s (or)
- Either place x2 (q) rows of B’s (or)
- Subdivide x2 = x4 + x5 and keep x4 (q+1) C’s and x5 (q) B’s
- Using point (e), solve the problem
My solution: Refer the link. Hope this helps.
Publish the same in separate blog on discuss, it would be helpful and put lunchtime tag, so it will come under editorial section. thanks for editorial.
Yes, i did the same. Thanks