# Editorial - EQAVG - Unofficial

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, 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

The above table can be written as solution array [B1,B2,…,Bm,C1,C2,…Ck-m] - repeat “q” times followed by [B1,B2,…,Bm] once

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 form above table, so answer is “NO”
• For each Fp, find x1 x2 x3 such that Fp = x1 (q+1) + x2 (q+1)(q) + x3 (q). As multiple solution exists, we find x such that we have minimum x1and x3 and maximum x2
• Each Dp has to be placed in exactly x1 rows from 1 to m i.e., rows having B’s in table
• Each Dp has to be placed in exactly 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 above point, we can solve the problem by filling missing rows of B’s and C’s

My solution: Refer the link. Hope this helps.

1 Like

here is my approach I am getting wrong answer can someone give me guidelines what is wrong in the solution