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

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

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
  • Проголосовать: не нравится

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

USACO.Guide is excited to announce the 2024 USACO.Guide Informatics Tournament!

It will take place on March 2nd, from 10am to 1pm (PDT). The contest will be 3 hours, 8 problems, and individual. There will be two divisions:

  • Standard for students in USACO Bronze/Silver and under 1600 rating on Codeforces.
  • Advanced for students in USACO Gold+ or 1600+ in Codeforces rating.

Only pre-college students will be eligible for prizes. The prizes for each division will be:

Advanced:

  1. $300
  2. $200
  3. $100
  4. through 8. $15

Standard:

  1. $150
  2. $100
  3. $50
  4. through 8. $15

A huge thanks to our problemsetting team: Hori, lunchbox, kondasujay2, stefdasca, Rocky_dp, lime, Segni, StanleyTung, and Randomtest. In addition, thanks to our testers for providing invaluable feedback: amoeba3, Ritwin, willy108, popkarsd, tgp07, and kevinator.

The contest will be conducted on Codeforces. For more information, visit joincpi.org/tournament or join our Discord server.

Sign up here!

Полный текст и комментарии »

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