lunchbox's blog

By lunchbox, 6 weeks ago,

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.

Solution
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$.

Solution
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$.

Solution

Now let's take a look at some non-standard problems.

Hint 1
Hint 2
P5: JOI 2022 Let's Win the Election
Hint 1
Hint 2
Solution

Hope you all found this helpful!

• +251

 » 6 weeks ago, # |   +16 lunchbox orz! nice blog :3
 » 6 weeks ago, # |   +27 lunchbox how to be good as u at cp?
 » 6 weeks ago, # |   +18 lunchbox orz, great tutorial
 » 6 weeks ago, # |   +10 I actually used aliens to solve Programmers and Artists https://cses.fi/paste/484b20df3ff9e0aa4ada9e/ so nice to learn a real solution haha
•  » » 5 weeks ago, # ^ |   0 What's aliens? is it kinda trick or something?
•  » » » 5 weeks ago, # ^ |   +3 Yep, Alien's Trick!
•  » » 5 weeks ago, # ^ |   +8 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.
 » 6 weeks ago, # |   +7 I love this blog! lunchbox orz!
 » 6 weeks ago, # |   0 Orz nice blog, (although I'm stuck at P4)
 » 6 weeks ago, # |   0 nice blog!
 » 5 weeks ago, # |   0 please add this to the Catalog !!!