Shayan's blog

Codeforces Educational Round 171 — Video Tutorial
By Shayan, history, 2 months ago, In English

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
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

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.

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

    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.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

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

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

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

          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.

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

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

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

              Thank you, new knowledge has been acquired.

              → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply