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
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.
- My greedy strategy identified first triple as 3 no’s of 8’s (8 had maximum frequency of 9)
- My greedy strategy identified second triple as 3 no’s of 8’s (8 had maximum frequency of 6, after first allocation)
- 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.