lunchbox's blog

By lunchbox, 3 months ago, In English

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.

P4: 1799F - Halve or Subtract
Hint 1
Hint 2
P5: JOI 2022 Let's Win the Election
Hint 1
Hint 2
Solution

Hope you all found this helpful!

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

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

lunchbox orz! nice blog :3

»
3 months ago, # |
  Vote: I like it +27 Vote: I do not like it

lunchbox how to be good as u at cp?

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

lunchbox orz, great tutorial

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I actually used aliens to solve Programmers and Artists https://cses.fi/paste/484b20df3ff9e0aa4ada9e/ so nice to learn a real solution haha

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's aliens? is it kinda trick or something?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I love this blog! lunchbox orz!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Orz nice blog, (although I'm stuck at P4)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice blog!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please add this to the Catalog !!!