Showing WA for EQAVG

1

I was solving problem: EQAVG Problem - CodeChef but it’s showing WA, that means I might be missing some cases but I am not able to find such cases, can u tell?
My approach :

  1. Every (i)th element must be equal to (k+i)th element for each i < (n-k)
    my solution :
    CodeChef: Practical coding for everyone
2

actually i dont know the perfect answer, but i saw most of the accepted solution from not accepted one. say that you require either R or R+1 values to fill a k-jumping walk over the N elements. then if there are 2R of some number and R+1 of another

you want to use the R+1 one at 0, k, 2k, …, and the R ones at 1, k+1, … and 2, k+2, …
well, so, some number counts can be uniquely written as sums of R’s and R+1’s
but it’s not completely clear how to handle counts that are >= R*(R+1)
some DP or greedy with special-casing chunks that are >= R*(R+1) I guess

3

Look at this sol: CodeChef: Practical coding for everyone. I am even checking whether if all the averages are equal or not for each subarray of length k

5

Consider n%k=m (non-zero) and n//k=q, we need a strategy to decide which numbers needs to be selected to repeat (q+1) times versus those that needs to be selected for repeating q times. I got WA in my earlier submission; TC# 5 alone passed. My incorrect strategy was to take highest remaining frequency and greedily arrange them to (q+1) frequency positions. I wanted to tackle the q frequency positions after dealing with all (q+1) frequency positions. This didn’t work, and in below test case my strategy failed and gave an answer “NO”

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

In above test case n=17; k=7;m=3;q=2, we need to identify 3 sets of triples and 4 sets of doubles. We initially have 9 x 8’s, 4 x 3’s, 2 x 10’s, 2 x 4’s.

  1. My greedy strategy identified first triple as 3 no’s of 8’s (8 had maximum frequency of 9)
  2. My greedy strategy identified second triple as 3 no’s of 8’s (8 had maximum frequency of 6, after first allocation)
  3. My greedy strategy identified third triple as 3 no’s of 3’s (After second allocation; 3 had maximum frequency of 4, followed by 8 with 3)

Now my program failed as it didn’t know what to do with the remaining 1 no’s of 3 !! Realised my greedy strategy of arranging numbers to (q+1) frequency slot is flawed; and changed algorithm based on frequency value to determine optimal strategy to allocate to slot (either q or q+1). In above example; as there are 4 x 3’s, algorithm needs to necessarily spilt it as two doubles.

If your error is like mine above, check my editorial for how to arrive at the allocation strategy.

Hope above explanation helps.

1 Like
6

Spot on! We need to divide the numbers into groups of q and q+1. Actually earlier I was thinking to assign the array b in sequential manner which would have work on every case but just because I’m lazy, I generalized it to assign 1,k+1,2*k+1 …etc. thank you bro!