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

Can we solve this problem without using Flow algorithms ?
Автор TiredOfLife, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

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

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.

→ Ответить