TiredOfLife's blog

Can we solve this problem without using Flow algorithms ?
By TiredOfLife, history, 4 years ago, In English

I was solving Problem B from Bubble cup 13 Div 1 [Because it is rated as 1900 :( ] . I tried simple BFS + Binary search but later found that it was wrong . After that I saw a lot of solution in standings and all of them are either using Flow algorithm or some matching algorithm and I don't know any of them :) . So I thought maybe they had templates for those algorithms so they used it . But I am thinking can we solve it without using those algorithms or it's time to learn some new algorithms ?
Here is the link to the problem

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I too can't think of any solution other than binary search + bipartite matching. Although, the lower rating may be in part due to weak tests that let some greedy solutions pass, as seems evident from the discussions on the announcement page. A test case was added after the contest, which failed many ACs, but the solutions were not rejudged.

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

    So I am gonna learn flows now :)
    Yes I saw those solution ran only on 20 test cases while mine failed on 23rd . Maybe that's why rating is low .
    Thanks .

    → Reply