Hacker Cup Round 1 Recap

Oh so your total points on the scoreboard aren't reflecting the fact that the submission went through. We have a script running to update those, but it might take several hours to complete.

Yours should be updated now

Nobody is registered for round 2 yet. You'll be automatically registered before round 2 begins.

Thank you very much for your comment. Without seeing it I'd have missed round 2 because I thought I didn't qualify for it and deactivated my FB account.

I wish they send emails to remind participants.

Can you explain the checker function because i had same logic but for checker function i used priority queue

I also used a max heap. Suppose we want to check if first k groups can be assigned or not. Here $$$groups[i]$$$ denotes the frequency of the i-th largest score in $$$A$$$. Calculate prefix sum of the groups array, so $$$groups[1 \dots k]$$$ will be increasing. Insert the count of all the prizes in a max heap. Now, we want to iterate from i = k to i = 1 and compare $$$groups[i]$$$ with the max in heap.

1. If the heap is empty: not possible
2. If the max in the heap >= groups[i]: possible for i, remove the max value from the heap as even if we may not use all the prizes of that kind, we cannot reuse it for anything else
3. Otherwise, keep popping from the heap until the sum of the popped prize counts becomes >= groups[i]. Here more than one kind of prize is assigned. But, if the $$$sum \gt groups[i]$$$ then we can reuse the leftover items. So, insert $$$sum - groups[i]$$$ back into the heap.

If the assignment was done for all i from k to 1 then it is possible.

Sure , the idea behind it is just sort the Ai array , now construct another array which will just store the frequency of same elements ( e.g A = [7,6,6,5,2,1] => new array will be [1,2,1,1,1] "tmp array" ) now you can only assign merchandise in decreasing order so most optimised would be , if we consider first k of them => k , k-1, k-2 ... 1 , now your job is to calculate how many of merchandise you need which can be easily done as you move over your "tmp array" , now comes the main thing you need to calculate how many merchandise you have , so for that you can just sort the b array and make sure which ever values are above k => should be taken as k only (which can be easily done using binary search) . but make sure size of B array should be >= k . so overall you only need for loop and BS

Ok so first let us make a frequency map of the scores of the competitors. Let a be the array such that the ith element of a denotes the number of contestants with the ith lowest score. Notice that the actual scores don't matter. Let s denote the total number of prizes

We will find j such that all contestants having the jth highest score or higher receive a prize. The main challenge is to find such an allocation of prizes to all such contestants.

Observation-1 Notice that it is optimal to give 1 prize to contestants having the jth highest score, 2 to the ones having (j+1) th highest score and so on.

Let x be the number of prizes which the highest scoring contestants should receive. Let y denote the number of participants who got the highest score.

We would like to have an array of the form [x,x,x,...y terms]. Such an arrangement would ensure that the highest scoring participants are also satisfied. Of course, you could have terms higher than x as well.

Observation-2 Let q be the number of prizes given to all participants except the highest scoring ones. Then two conditions should hold:- i) The initial y highest values of b should each be greater than or equal to x ii) q<=s-x*y

We just need to check these two conditions. I think they are sufficient but I don't know how to prove them rigorously.

We just have to binary search the answer for such a j now.

PS Maybe one way to think is that in the first glance, it may seem that condition 2 is sufficient, but we find a counterexample when a single type has a lot of units. Hence the first condition is also required.

Apologies for the bad formatting though.

My solution reports 5.

5

You can simply maintain the prefix sum of the frequency array of $$$B$$$, and store the prefix sum with a multiset, which will be helpful for doing range updates.

E.g. if $$$B = [1, 1, 2, 2, 2, 3, 4, 4]$$$, we have frequency array (starting at $$$0$$$), $$$freq = [0, 2, 3, 1, 2]$$$ (i.e. $$$freq[i] = $$$ count of $$$i$$$ in $$$B$$$). Now, let's store the prefix sum of $$$freq$$$ into a multiset called $$$ps$$$, i.e. $$$ps = $$$ {$$$0, 2, 5, 6, 8$$$}.

Notice that in most cases, performing "range -1" opeartions on the largest $$$k$$$ elements in $$$B$$$ is just as simple as deleting an element in our prefix sum multiset $$$ps$$$.

E.g. Let $$$k=3$$$, then, doing "range -1" the $$$k$$$ largest elements in $$$B$$$ would be changing $$$3, 4, 4$$$ into $$$2, 3, 3$$$, making $$$B = [1, 1, 2, 2, 2, 2, 3, 3]$$$, and $$$freq = [0, 2, 4, 2, 0]$$$. Now, our updated $$$ps$$$ should be {$$$0, 2, 6, 8$$$}, which is just removing $$$5$$$ from our previous $$$ps$$$!

Determining wether there are $$$\geq{k}$$$ positive integers in $$$B$$$ at each step is easy too! Since *prev(ps.end()) would be how many elements in $$$B$$$, and *(ps.begin()) refers to how many zeros are there in $$$B$$$ right now.

There is also a case where $$$k$$$ doesn't cover a full block of numbers, like when $$$k=5$$$, we are changing $$$B = [1, 1, 2, 2, 2, 3, 4, 4]$$$ into $$$[1, 1, 2, 1, 1, 2, 3, 3]$$$, making $$$freq = [0, 4, 2, 2]$$$ and $$$ps = $$$ {$$$0, 4, 6, 8$$$}, which is just an additional step of changing $$$2$$$ to $$$4$$$ first, before going back to our previous case of simply deleting $$$5$$$. (i.e. {$$$0, 2, 5, 6, 8$$$} $$$\rightarrow$$$ {$$$0, 4, 5, 6, 8$$$} $$$\rightarrow$$$ {$$$0, 4, 6, 8$$$})

tbh they had almost the same score so it made sense to read them both

In case it wasn't clear, dp[i][mask]=number of ways to add i more digits at the end with the current mask of prefix sums(rotated such that the current one is the 0th bit, and also not included in the actual variable), i has nothing to do with number of bits in mask(other than that their sum is <=k)

You don't need any other parameters, for each k you only calculate the dp once, then for all i in 1..length(r)-1 you add dp[i][0] to the answer, and you can also easily keep track of the current prefix sums used and how many more digits you have to add and add the corresponding precomputed dp state to the answer when going through the digits of r one by one.

you are in for a treat

congats bud ^_^

Congrats!
I was at 2059 when contest ended, jumped to 2032 in a week and now at 2005. Just a few more cheaters MHC team, please orz
But also advocating for Tasky's survival — everyone who actually solved AB deserves a T-Shirt!