The-2024ECPCwinner's blog

Need help in this repeated subproblem
By The-2024ECPCwinner, history, 2 years ago, In English
  • I met this problem as a subproblem many times and tried to find a solution for it but failed ,So I make an elegent statement for the problem asking for someone's help :
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Could you give a publicly available link instead of screenshots? Or at least tell where the problem is from? This looks fishy.

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

    Edited , Bro

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      The reason why I asked for a link ia to prevent cheating, but considering the statement you sent doesn't even have a bound on the sum of $$$k_i$$$ i will assume youre not.

      This is the maximum bipartite matching problem, you can read about it here https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html

      However, this is an advanced topic and you should probably worry about other things more. If you're encountering this problem a lot youre probably making the wrong reductions.

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

        I understood the topic , but can't it be solved in time complexity less than O(n*m) time , if we don't need the number of matchings, just need whether or not the solution exists

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it +1 Vote: I do not like it

          Kuhn is faster than $$$O(nm)$$$ in practice with the heuristics they talk about there. There is also a $$$O(n\sqrt{n})$$$ that as far as i know is hard to distinguish from kuhn. Asking if there is a perfect matching doesn't help in this problem.

          Also, if you are thinking on how to solve a specific problem, send that specific problem instead. A lot of times when beginners ask for help they make wrong reductions and leave out important information, that's probably what is happening here.

          → Reply