Pols_Agyi_Pols's blog

Invitation to CodeChef Starters 149(Rated upto 5 stars) — 28th August
By Pols_Agyi_Pols, 3 weeks ago, In English

We invite you to participate in CodeChef’s Starters149, this Wednesday, 28th August, rated upto 5 stars (i.e. for users with rating < 2200)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Note: Some problems may also have subtasks.

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

  • Vote: I like it
  • +44
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

contest about to start

→ Reply
»
2 weeks ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It could also be solved in $$$O(n)$$$ after sorting the enemy health using prefix sums and two pointers. Submission

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, just realized that and came here to comment that a segtree isn't needed in the approach I described above, since we are only changing the terminal element of a suffix and querying for subarray sum, which can be done in $$$O(n)$$$.

      Also, I fumbled on preventing the overflow of the product during the contest, planning to use int64_t and such, but later realized that temporarily setting k to min(k, max/curr + 1) also avoids any overflows.

      Update : I didn't have to worry about overflows, since the only indices possibilities for multiplication are $$$a[i] < 10^9$$$.

      → Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Problem link: link

→ Reply