Can someone please provide any interesting test cases for Problem C ? I am getting wrong answer.
Me too.. some test cases would help!Thanks
try long instead of integers
I have tried with both long and long long. Still getting wrong answer.
Has anyone come across timelimits?I found that sorting the trees in descending order and then assigning them in turn to the saw with the least load so far, yields a 4/3 approximation (which satisfies the at most 50% higher than optimal requirement) (http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture2.pdf). If I do not get it wrong, my program should have a time complexity of O(n log(n)), because the initial sorting takes O(n log(n)) and the n assignments take O(log(n)) each. Any suggestions?
Your approach works for me. If you are using a heap for the assignment step, my guess is you use a more expensive operation. Like make_heap instead of pop/push
To anyone who is also experiencing this: If you are on Java and using a sorted array list: removing the first element results in all elements being moved by one position, hence the runtime is O(n^2). That's what caused my timelimit.