Link to pdf version on UVa OJ
Setting each problem has two parts, each part takes its time and second part of each problem is dependent on the completion of the first part. Given this constraint we want to find the minimum time required to finish all the problems.
What happened in my mind : After I read the problem statement, it was obvious that we need to find the best ordering. First I didn't see N <= 20, I accidentally saw 100 as the limit for N. Then I thought ok, we need to find the best ordering. Because if the ordering is fixed then calculating the time is trivial. (Just test some ordering from sample tests and try to calculate the time required to finish problems in that order, then you will see it's not that hard to calculate it.)
First I tried sorting by A and calculating, thanks to the test cases this was not good.
Then I tried sorting by B and calculating, again thanks to the test cases this was not optimal as well.
Then I thought to myself, we need to find an ordering, right? So if i-th problem comes before j-th problem, and j-th problem comes before k-th problem, it means i-th problem must come before k-th problem (transitive relation) and each two elements must be comparable (either i-th problem comes before j-th or j-th comes before i-th). This is the only way we can have an ordering. (Every two element must be comparable, otherwise it maybe "partially ordered set") I didn't go further on this, I assumed i <= j, j <= k means i <= k, but I know it can be proved.
In this way I reduced the problem to comparison of two elements, I wrote two elements and tried to find when i-th element comes before j-th element.
After defining function cost(i, j) it's easy to know the ordering, i-th element comes before j-th element if and only if cost(i, j) <= cost(j, i)
For more details please refer to my code on github
Setting each problem has two parts, each part takes its time and second part of each problem is dependent on the completion of the first part. Given this constraint we want to find the minimum time required to finish all the problems.
What happened in my mind : After I read the problem statement, it was obvious that we need to find the best ordering. First I didn't see N <= 20, I accidentally saw 100 as the limit for N. Then I thought ok, we need to find the best ordering. Because if the ordering is fixed then calculating the time is trivial. (Just test some ordering from sample tests and try to calculate the time required to finish problems in that order, then you will see it's not that hard to calculate it.)
First I tried sorting by A and calculating, thanks to the test cases this was not good.
Then I tried sorting by B and calculating, again thanks to the test cases this was not optimal as well.
Then I thought to myself, we need to find an ordering, right? So if i-th problem comes before j-th problem, and j-th problem comes before k-th problem, it means i-th problem must come before k-th problem (transitive relation) and each two elements must be comparable (either i-th problem comes before j-th or j-th comes before i-th). This is the only way we can have an ordering. (Every two element must be comparable, otherwise it maybe "partially ordered set") I didn't go further on this, I assumed i <= j, j <= k means i <= k, but I know it can be proved.
In this way I reduced the problem to comparison of two elements, I wrote two elements and tried to find when i-th element comes before j-th element.
After defining function cost(i, j) it's easy to know the ordering, i-th element comes before j-th element if and only if cost(i, j) <= cost(j, i)
For more details please refer to my code on github
No comments:
Post a Comment