Hope to cross 2100 after this contest. Expecting some quality problems like last codechef starters.

contest about to start

Hints for Kill Monsters (Easy and Hard Version)

Update : I created video editorial for this problem.

First, come up with an $$$O(n^2)$$$ solution for the easy version.

It might look optimal to always multiply by $$$k$$$ at the start. After all, $$$x$$$ will only decrease in future, hence the product will be even smaller. But if you look at the second test case, you will realise that we multiply at a later stage in order to take more than 1 copy of some elements we have already taken.

But this also makes it clear that you can make 2 trips at most. Hence, you can only take a maximum of copies per element. Let's create a frequency array containing $$$0$$$, $$$1$$$ or $$$2$$$. Notice that the number of unique elements is around $$$5000$$$. Hence, an $$$O(n^2)$$$ algorithm is acceptable, where $$$n$$$ now denotes the number of unique elements.

Sort the unique elements, and start traversing from right to left, taking one copy of each element, and updating the alive array. Then, when you decide to do an operation, you need the count of alive elements to the right of current index but to the left $$$a[now]*k$$$. This can be easily computed by iterating over the alive array and computing its sum. Hence, you know the answer when you perform the operation at each index.

For the hard version, just use a segtree to query range sum, and take care of overflows in the key that you use for lower_bound.

• Naive
• Segment Tree
• Suffix Sum

Can someone point out the mistake in my code (for kill monsters easy hersion) which leads to TLE. Submission: link

Problem link: link