Calculating total maintenance costs of a car

Question

Introduction

I drive a white 2CV from home to work, and intend to keep that way until retirement. Once retired, I will sell the 2CV to buy a yacht and sail away. My home is far, far away from my work, so I put a lot of kms on the 2CV everyday. The 2CV is beautiful and nice but also an old car, so a lot of maintenance is required. Every month I’m facing this dilemma. Should I repair the 2CV engine or should I exchange it by a re-conditioned one? You see: as the engine gets old its maintenance cost increases, and at the same time its return value in the exchanging process decreases (the older the engine the more I have to spend to exchange it for a re-conditioned one). On the other hand, the older the engine the lowest the final sell price of the car. Obviously, at the end (i.e., at my retirement) I would like to have the maximum money possible for the yacht. This forces me to make the right decision each month, i.e., either maintain or exchange the engine.

Task

Write a program for computing the total minimum cost I’ll have to spend at the end of N months (the period from now till retirement) knowing the initial age of the engine I (in months), the series of maintenance costs for 2CV engines over the months, the price of motor exchange as function of its age (in months), and the selling prices of the 2CV as function of the age of its engine. I don’t want to count every cent so all the above values are integers. Notice that the mooshak timeout for this task is 1 second. That is, your code should output an answer in 1 second max. A Time Limit Exceeded or Run Time Error will be issued otherwise.

Input

The input consists of 5 lines. The first line has an integer N representing the number of months till retirement, 1 ≤ N ≤ 240. The second line has the integer I, the initial age of the motor in months, 0 ≤ I ≤ 100. The third line has a space separated sequence of integer maintenance costs C(i), for a one month period, of an engine with i months at the beginning of the current month, 0 ≤ i ≤ N + I - 1. The fourth line has a space separated sequence of integer exchange prices T(i) for an engine with i months, 1 ≤ i ≤ N + I - 1. The fifth line has a space separated sequence of integer selling prices S(i) of the 2CV equipped with an engine that just turned i months old at the end of the N months, 1 ≤ i ≤ N + I+1.

Output

The output line has an integer representing the maximum possible money for the given input.

Input example 1

1
3
10 50 100 350
18 75 170
5000 4980 4750 4000

Output example 1

4820

Input example 2

5
2
100 150 200 250 330 450 499
180 290 390 450 500 500
5000 4980 4750 4000 3950 3730 3000

Output example 2

3620

My solution

import java.util.Scanner;

public class Main {

static int[] maintenance;
static int[] exchange;
static int[] sell;
static int truemax = Integer.MIN_VALUE;

public static void main(String[] args)
{
    Scanner sc = new Scanner(System.in);
    int months = sc.nextInt();
    int engine = sc.nextInt();

    maintenance = new int[months+engine];
    exchange = new int[months+engine - 1];
    sell = new int[months+engine];

    for(int i = 0; i < months+engine; i++)
    {
        maintenance[i] = sc.nextInt();
    }

    for(int i = 0; i < months+engine- 1; i++)
    {
        exchange[i] = sc.nextInt();
    }

    for(int i = 0; i < months+engine; i++)
    {
        sell[i] = sc.nextInt();
    }
    sc.close();

    int routes = (int) Math.pow(2, months);
    int f = routes/2;
    route(0,f, engine,engine, 0, 0);

    System.out.println(truemax);
}
static int type;

public static int route(int curr, int per, int eng, int inv_eng, int z, int 
inv_z)
{
        type = Math.floorDiv(curr,per);

        if(type%2 == 0)
        {
            z += exchange[eng - 1] + maintenance[0];
            eng = 1;
            inv_z += maintenance[inv_eng];
            inv_eng++;
        }
        else
        {
            z += maintenance[eng];
            eng++;
            inv_z += exchange[inv_eng - 1] + maintenance[0];
            inv_eng = 1;
        }

        if(per != 1)
        {
            for(int i = 0; i < 2; i++)
            {
            curr = route(curr,per/2, eng,inv_eng, z, inv_z);
            }
        }
        else
        {
            z = sell[eng - 1] - z;
            inv_z = sell[inv_eng - 1] - inv_z;
            curr++;
            if(z > truemax || inv_z > truemax)
            {
                if(z > inv_z)
                {
                    truemax = z;
                }
                else
                {
                    truemax = inv_z;
                }
            }
        }
        return curr;
    }
}

My program is taking too long for bigger inputs. What can I change to decrease the time taking to execute for some inputs in less than 1 second?

Answer 1

This is a textbook example asking for dynamic programming. The time limit is chosen such that success is impossible without dynamic programming.

Dynamic programming can be applied to recursive problems. The idea is to store the results of all sub-problems in a table and if you encounter the same sub-problem again in another recursion path, you can return early.

Change your code to something like this:

public class Main {
    [...]
    static Hashtable optima;                // table to store results for re-use

    public static void main(String[] args)
    {
        optima = new HashTable();
        [...]                               // read input
        route(...)                          // call route
    }

    public static int route(...)
    {
        // if the optimum for the sub-problem is already known, fetch it
        Object optimum = optima.get(new Pair(remainingMonths, engineAge));
        if (optimum != null)
        {
            return (int)optimum;
        }

        // if not, calculate it normally using recursion
        [...]

        // store newly calculated result for re-use
        optima.put(new Pair(remainingMonths, engineAge), optimum);

        return optimum;
    }

Answer 2

You use months+engine a lot in your code; I think you should come up with a good name for that and create a variable with it (not sure that this would speed things up much, but it would be DRYer).

Answer 3

I did not check the whole code, but here is a small improvment for those three almost identical for. It will not make valuable difference in speed, but it is more readable and reusable.

So, this part:

for(int i = 0; i < months+engine; i++)
{
    maintenance[i] = sc.nextInt();
}

for(int i = 0; i < months+engine- 1; i++)
{
    exchange[i] = sc.nextInt();
}

for(int i = 0; i < months+engine; i++)
{
    sell[i] = sc.nextInt();
}

Could become smth like this:

public static void calcNext ( entity, addFactor ) {
    for(int i = 0; i < months + engine + addFactor; i++)
    {
        entity[i] = entity.nextInt();
    }
}

calcNext ( maintenance, 0 )
calcNext ( exchange, -1 )
calcNext ( sell, 0 )