adaptatron's blog

By adaptatron, 3 months ago, In English

Given an array of positive integers, for each element, you can choose to multiply it by $$$-1$$$. Find the maximum number of negative elements at the end, such that the prefix sum of the final array contains strictly positive integers only.

I created a short blog that talks about how the obviously incorrect greedy strategy for some problems can actually be fine-tuned to be correct, by going back and altering our choices.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them here: https://codeforces.com/group/7Dn3ObOpau/contest/513385

https://cfstep.com/training/tutorials/general-techniques/time-travel-in-greedy-algorithms/

If you have an alternate solution for any of these problems, do let me know in the comments.

If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Problem You can add this one as well