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

Help with one question.
Автор anshusaurav, 13 лет назад, По-английски

Thanks for your response i have solved it successfully.


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

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think the greedy approach will work here .
You can sort all problems at first , and in each day take the smallest vi value problem and all other problems that are at least K points apart .
This can be done using brute force simulation in O(N2) .
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
This problem is from Interviewstreet, by the way.

I solved it using a minimum path cover on a DAG (directed acyclic graph), which can then be solved using bipartite matching. This works if you represent the problems as nodes and the problems you can solve after one another as edges.
There may be simpler solutions.

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
Did you delete the problem from the blog? why? no need to delete problem statement or link after solving,it can help other coders if you don't delete them.  But off course you should remove code (if you post any) after getting ac.
→ Ответить