10576 - Y2K Accounting Bug
Problem asks to generate result from whatever data we have left after losing some data. The problem is difficult to understand at first, and after a few times for many people. But good news is that it is easy to come to solution once problem is understood.
I will be explaining all the conditions with the help of first test case given in question.
month profit last_5_month_reports 1 59 2 59 3 59 4 59 5 -237 59*4-237= -1 6 59 59*3-237+59= -1 7 59 59*2-237+59*2=-1 8 59 59*1-237+59*3=-1 9 59 -237+59*4= -1 10 -237 59*4-237 = -1 11 59 59*3-237+59= -1 12 59 59*2-237+59*2= -1 (all are negative so deficit was reported in all 8 reports.) total 116(have to maximize this)
To figure out a way we need to check all combination of 12 months (each month can have surplus or deficit) and out of them need to find the combination that maximizes the total amount as well as reports deficit(negative over last 5 months) in all 8 monthly reports. Since we have no better option we have to write a complete search/Recursive backtracking solution for this.
- Amount of deficit(d) is to be taken with negative sign.
- monthly report is about last 5 consecutive months (more precisely current month+last 4 months), so it starts from 5th month
resulting in total 12-5+1 = 8 reports in one year.
- However if you go on checking each and every solution(complete search), you may get time limit exceeded.
Read optimization section to be more efficient.
In order to prune our search space, leave any combination once it gives surplus report in any of 5th+ month. That is,if you find sum of (last 4+current) month's profit to be positive for any month after 4th (5,6,7...12th) you should leave that combination. Since it violates given condition and so it is of no use to continue with this.
59 237 375 743 200000 849694 2500000 8000000
116 28 300612 Deficit