Regarding ALEXROSE - DEC'16 long

Since the editorial isn’t out yet, I’d like to know how to solve ALEXROSE from DEC long?

This problem can be solved by several observations :

OBSERVATION 1 :- Only the frequency of each element of the array matters .
Thus we can sort the array , and maintain frequency array only.

OBSERVATION 2 :- Any frequency which is above k can be first grouped into k elements till freq becomes less than k . In other words , we can do (freq % k) if freq>=k .

OBSERVATION 3 : To minimise answer , we need more to bunch higher frequencies together . To do this, we can maintain a MAX HEAP or PRIORITY QUEUE of frequencies.

We can remove the top element of queue (i.e k - queue.top and add it to ans) to once the total sum exceeds j*k where j=0,1,2,… and so on.

Here is my submission : CodeChef: Practical coding for everyone

1 Like

Hello avi224,please find my algo below
Algorithm:-
maintain a table data structure to store the data of height and number of flowers of that height
Now maintain a array list of counts in increasing order of heights

ALL COUNTS are MODULUS of K

perform below steps
step1:- get the maximum height flowers in hand(pool) all these must be cut by the end of the algorithm
step2:- required cuts=K-count
get the next Maximum height count,if that count is LESS THAN K/2 then Dont make bouquet with them instead add them in to pool ,take in to hand
if count is GREATER THAN OR Equal K/2 then form a bouquet if the free pool size is enough to full fill the requiremet else add that count in to free pool
step3:-once complete list consumed print the cutts

and my solution

https://www.codechef.com/viewplaintext/12262826

please let me know my mistake

Regards
Samuel