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 : https://www.codechef.com/viewsolution/12268166
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