anshusaurav's blog

Help with one question.
By anshusaurav, 12 years ago, In English

Thanks for your response i have solved it successfully.


  • Vote: I like it
  • -3
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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) .
→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it
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.

→ Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it
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.
→ Reply