UVa 10576

From Algorithmist
Jump to navigation Jump to search

10576 - Y2K Accounting Bug[edit]

Summary[edit]

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.

Explanation[edit]

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.

Gotchas[edit]

  • 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.

Notes[edit]

  • 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.

Implementations[edit]

Java Implementation:

Optimizations[edit]

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.

Input[edit]

59 237
375 743
200000 849694
2500000 8000000

Output[edit]

116
28
300612
Deficit