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
link

Your code fails for same test case mentioned in my reply to another codechef user. Please check your allocation logic to see if it has the same issue i described in that post

Failed Test Case
1
17 7
8 10 8 10 4 3 3 8 8 8 8 4 3 3 8 8 8