Блог пользователя lunchbox

Автор lunchbox, 3 месяца назад, По-английски

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!

  • Проголосовать: нравится
  • +251
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

lunchbox orz! nice blog :3

»
3 месяца назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

lunchbox how to be good as u at cp?

»
3 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

lunchbox orz, great tutorial

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I love this blog! lunchbox orz!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice blog!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please add this to the Catalog !!!