Hi!
You might have seen problems where you're tasked to find something along the lines of "choosing some subsets that maximize the sum of something". In this post, I'll be discussing some ideas that solve those type of problems. As I'm not sure of a formal definition, I'll call this the Subset Assignment Problem.
P1
You're given an array $$$a$$$ ($$$1\leq a_i\leq 10^9$$$) of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find a subset of size $$$k$$$ ($$$0\leq k\leq n$$$) that maximizes the sum.
P2
You're given two arrays $$$a$$$ and $$$b$$$ ($$$1\leq a_i, b_i\leq 10^9$$$), both of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find two disjoint subsets $$$S$$$ and $$$T$$$ of sizes $$$k_1$$$ an $$$k_2$$$ ($$$0\leq k_1, k_2\leq n$$$, $$$k_1 + k_2 = n$$$) respectively that maximizes $$$\sum_{i\in S}a_i + \sum_{i\in T}b_i$$$.
P3: CSES Programmers and Artists
You're given two arrays $$$a$$$ and $$$b$$$ ($$$1\leq a_i, b_i\leq 10^9$$$), both of size $$$n$$$ ($$$1\leq n\leq 10^5$$$). Find two disjoint subsets $$$S$$$ and $$$T$$$ of sizes $$$k_1$$$ an $$$k_2$$$ ($$$0\leq k_1, k_2\leq n$$$) respectively that maximizes $$$\sum_{i\in S}a_i + \sum_{i\in T}b_i$$$.
Now let's take a look at some non-standard problems.
P4: 1799F - Halve or Subtract
P5: JOI 2022 Let's Win the Election
Hope you all found this helpful!
lunchbox orz! nice blog :3
lunchbox how to be good as u at cp?
lunchbox orz, great tutorial
I actually used aliens to solve Programmers and Artists https://cses.fi/paste/484b20df3ff9e0aa4ada9e/ so nice to learn a real solution haha
What's aliens? is it kinda trick or something?
Yep, Alien's Trick!
That's really cool! A friend also showed me this. I think it probably also generalizes to higher dimensions: solving the problem for $$$m$$$ disjoint subsets in $$$O(n\cdot (\log a)^m$$$) time.
I love this blog! lunchbox orz!
Orz nice blog, (although I'm stuck at P4)
nice blog!
please add this to the Catalog !!!