Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.
2026A — Perpendicular Segments
Video
2026B — Black Cells
Video
2026C — Action Figures
Video
2026D — Sums of Segments
Video
2026E — Best Subsequence
Video
Are there any ways to solve problem E with dp? I tried to solve it with dp but get WA.
Let dp[i][j] represent the value of mask such that the number of 1-bits in mask is minimized when constructing a subsequence of length j with i as the last element of the sequence.
I think we can combine with some greedy tactics, such as save more than one mask for each dp[i][j] at a time. Sorry for my bad English.
For your solution to passed, you have to store EVERY mask which satisfied your dp[i][j]. And since a[i] has at most 60 bits, i don't see how you will pass using this dp.
Because we have to store EVERY mask which satisfied dp[i][j], so i am curios that there are any ways to solve with probability/greedy?
The first thing comes to my mind is dp[i][j] will save more than one mask at a time, we will limit the numbers of candidate about 10-20 candidates.
You can solve E by modelling it as a max flow question!
Can you explain how to model this problem into a maximum flow question? I see a lot of submissions getting AC with a maximum flow solution, but I don't understand how they convert the problem into maximum flow.
Try applying the Project Selection Problem with projects are array elements and machines are the 2-powers of their 1-bits.
Thank you, new knowledge has been acquired.
Can anyone drop some good problems related to flows for practice. E seemed very doable after the flow thing
There are 4 problems on cses in the graphs section which can be solved by network flows,
https://cses.fi/problemset/task/1694 https://cses.fi/problemset/task/1711 https://cses.fi/problemset/task/1695 https://cses.fi/problemset/task/1696