I have used a brute force approach to solve the Watching CPL problem. Here are the steps:
- I created 2 vectors, say A and B, and two sums, say sum1 and sum2.
- Then I sorted the given array in descending order.
- Now I stored the array elements in the vectors A and B alternatively. So, H goes into A, H into B, H into A, and so on. As the values were stored I calculated the sums, sum1=H+H… and sum2=H+H…
- This loop goes on until the elements aren’t over, or until sum1 doesn’t become >=K. There was no condition for sum2, as sum2 will always be less than sum1.
- Now I inserted all the left out elements(if any) in B.
- Now, I checked whether any element in B could be replaced with any element in A such that sum1>=K after replacing and element in B<element in A.
- As the replacement took place, I calculated the new sums sum1 and sum2. When sum2>=K, then break.
My problem is that with this approach I passed the 1st subtask and most of the 2nd subtask. I passed all the subtasks when rather than calculating sum2 in step 3, I calculated it in step 7.
Here is the solution that passed 1 subtask: Solution: 41349394 | CodeChef
And here’s the one that was correct: Solution: 41350897 | CodeChef
I just want to know the difference between the 2, and why the 2nd one passed. It will be helpful if someone can point out the faults in my thinking(I know there might be many)