Мне кажется давать совсем случайным участникам странно. Я бы понял, если

Случайные 5 участников (не топ-50, сделали хотя бы одну успешную попытку): футболка с логотипом

I think it's a matter of the companies which hold contests on CF , not CF itself.

why so much hate on this comment lol..everyone knows he will win, and I guess everyone loves tourist — the beast

Побочный эффект от печатания на С++ с детских лет

Maybe "multiset" XD

Yes, because they reset the registration.

would be fantastic, no newbies got a tshirt before.

Although I totally love the idea and also love to get a T-shirt, but I think keeping it for the first 50 is better. To encourage low-rate participants to do better and EARN the T-shirt.

Great idea, thanks! Playrix will give 5 additional prizes to random participants not included in the top 50. I hope CF will help us with fair random algorithms )

Best Regards, Trushkov Aleksey Playrix

Given that Playrix is a games development company?

What's her name :D ?

and a very long right hand

Me too XD

"не топ-50, сделали хотя бы одну попытку". Значит после

I have same problem :(

"An error has occurred There was a problem adding the item to Chrome. Please refresh the page and try again."

Well considering that 4500 ppl will participate in this round 50 for them will get prizes for sure that leaves 4450 the probability that one will get a prize is 0.0011235955.

Your luck is not poor it's just math.

:)

PS: if you work hard enough you won't need luck cause your probability will be 1.

I wonder if the T-shirts in this contest will be distributed based on an adaption of the formula from the problem in the previous contest 807B - Охота на футболки ...

5 minutes before the contest: we're still waiting for more info

photoshopFAIL

Но классные))

Did you spend the last ten minutes of the contest making this meme?

Dp[h][w] in map

Notice that for ai >= 3, you will need maximum of 11 items to increase alength from 1 to over 10**5. So you can brute over min(22, n) largest items to divide them into either Length/width. Incase the length is still less, then find how many no of 2's will satisfy Maintain a count of actual length increments done and find the minimum answer.

Complexity: O(2**22 * 20)

I thought this should pass. But this was very close to tle. 940ms first time for me. But after doing some bad optimizations, it passes pretest ins 499ms. (I lost around 400 points on this :|)

if you sort in non-increasing order, you should not to skip some extension, answer is some prefix, so you can use dp[idx][pair(curW, curH)] with map 27034588

Taking fountain with diamond + coin is easy. Then use two pointers\bin search for coin + coin, diamond + diamond pair.

I used segment tree range maximum query to find the best pair

Observe that you can either pay with coins only, diamonds only or both.

Sort by Coins or Diamonds whatever the case and have a dp array such that dp[i] is the fountain with biggest beauty in the range [0..i].

We can use binary search for any of the cases.

In the last case, iterate through the coin array and use binary search on the corresponding Diamond array.

I think all three cases should produce a best value.

There are three ways of purchasing two fountains:

• one of each type;
• two of the first type;
• two of the second type.

In the first case, just consider, for every type, the maximum beauty among the fountains whose price is lower or equal to the number of coins of this type. Then, the maximum beauty is the sum of these two.

Then, sort fountains separately according to their price, and precompute for every fountain the maximum beauty with a fountain whose price is lower of equal than this fountain. Then move from most expensive fountain to cheapest one and update the answer if you can.

Complexity in O(nlog(n)).

I did not solve it but those who find segtree easier than bin search can try this for the cases coin+coin and diamond+diamond. For every cost x, maintain two values, the two maximum beauty available and call them b1 and b2. If there is only one, set b1 to -inf and if there is none, set b1 and b2 both to -inf. Now build a segtree over the costs and every leaf node stores the maximum beauty possible with the given cost. If you select a fountain with cost x, replace in segtree with the second maximum beauty and query the segtree. Repeat this for every possible cost.

No binary search needed. Since the maximum possible price is not that big, it can be solved as follows.

Let's compute fc[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i coins, and id2 is the index of the second most beautiful fountains with the cost at most i coins.

Similarly, fd[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i diamonds, and id2 is the index of the second most beautiful fountains with the cost at most i diamonds.

These two tables can be easily computed in O(n) starting from i = 1 (or O(n*log(n)) if someone is lazy) if you have fountains grouped initially by an exact price.

After that, the only thing to do is to combine the results considering all the cases: you pay only with coins for both, you pay only with diamonds for both, you pay with coins for one and with diamonds for the other.

Since 2^18 > 1e5, you only need something like 60 items with best cost.

What is 4th testcase bro ? (for C question)

Sort the array a, and then try all possibilities by having last k elements in use? I used multiset array to store variantions of h and w, for some k and then go thru all of them in (k-1) array and try to multiply. As the multiplicator is at least 2 the multisets size might not explode :D

C was easy to code using BIT. Not at all tedious. code

solved

you use number_of_participants_with_positive_score while in announcement tshirt is for those who have at least one submission

Why do you use seed from the next contest?

So winner score is 8876 and number_of_participants_made_at_least_one_submission is 3465,

I get these five numbers: 903 935 1552 1591 2272

The seed is 8876, the number_of_participants_made_at_least_one_submission is 3465. So the winners are

Congratulations!

Hint: Note that bi >= 2. So you need at most 17 elements to make their product > 10^5.
Hint2: Suppose you are kinking K numbers. You will sort them in descending order and pick the first K numbers.

We know he is a legend :) But he solved E after 41 minutes while you solved A after 22 minutes.

Why people vote this comment ://////

systesting started fairly fast...guess rating change is going to be a bitch.

I removed cheaters and recalculated the ratings.

Usually the problems will be added to the problemset, you can upsolve them there

After system test finishes

You can upsolve after system testing.

TLE and MLE Unless you did one hell of an optimization.

there are 3 choices :

1) 1 cois + 1 diamond

2) 2 coins

3) 2 diamonds

the first is easy , the second and the third are the same

you have a vector of pair for each type { price , beauty } sorted in ascending order

try the first fountain to be v[i] with price p1 and you have coins-p1 left

the second one will be from range [ 0 , min(i-1, upper_bound(coins-p1)-1 ) ]

now take the one with max beauty ( precalculation )

something like that ...

Well, it doesn't make a difference, does it? He/She cannot resubmit his/her solution. And it was more or less obvious from the constraints that an O(n^2) solution would time out, so he didn't necessarily have to look at an optimal solution to figure that out.