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?

  • Welcome to Code Review! Hopefully you receive valuable input! – Sᴀᴍ Onᴇᴌᴀ Apr 16 at 16:16
  • Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Malachi Apr 16 at 16:52
  • 2
    Can you tell us where this problem/challenge/task was posted? e.g. textbook, website, etc. – Sᴀᴍ Onᴇᴌᴀ Apr 18 at 15:55
up vote 1 down vote accepted

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;
    }
  • What i'm doing is a "top-down parsing" approach. I see the first sub-problem fully and when i see the second I only see the difference in the last month then i see the third and only see the difference in the last two moths and so on... Wouldn't be the same as you are saying? or am I not seeing the concept of a sub-problem? – Flip Apr 17 at 9:08
  • @Flip - For each combination of remaining months and engine age, there's a solution that yields the maximum amount of money. It can be calculated as the cost of the first decision subtracted from the result of the associated sub-problem. Either problem(remaining, age) = problem(remaining - 1, age + 1) - maintenance(age) or problem(remaining, age) = problem(remaining - 1, 1) - replacement(age). Pick the larger one. – Rainer P. Apr 18 at 18:23

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

  • 1
    Thanks for the tip, it will decrease time indeed but that decrease wouldn't be much of a difference. – Flip Apr 16 at 16:46

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 )
  • I noticed that you silently adjusted the spacing around operators and parens to your personal convention. Why not make explicit note of that in the answer? It's just as valid a review :) – Vogel612 Apr 18 at 5:52
  • Thanks @Vogel612, I did notice only now! It isn't what it seems though, I did not sneakily adjusted anything, it was just that at the time I was working with a very poor screen resolution and wanted to besure that i have my syntax right. I am sure anyone can tell the code from the syntax style and make their own adjustments if choose to copy this chunk. – JohnPan Apr 18 at 6:43
  • This is really not what I would recommend. Magic values in the method call and no separation of the scanner from the method. No real added value. – RobAu Apr 18 at 7:06
  • @RobAu aggreed. It is not dry and has issues. I was wrong to support that it is reusable. But still, it is more readable and avoids repetition. – JohnPan Apr 18 at 7:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.