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

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

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

»
4 недели назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 недели назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        You can solve E by modelling it as a max flow question!

        • »
          »
          »
          »
          »
          4 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 недели назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Try applying the Project Selection Problem with projects are array elements and machines are the 2-powers of their 1-bits.

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

Can anyone drop some good problems related to flows for practice. E seemed very doable after the flow thing