0
$\begingroup$

Two twins, James Johnson and Jonathan Johnson, work at a factory which produces bicycles. Their job is probably the most important one: James attaches the front wheel, and Jonathan does the same with the rear wheel. At the beginning of their working day, they receive construction kits, consisting of the front wheel, the rear wheel, and the rest of the bicycle. It is known that:

  • for the i-th construction kit, James will attach the front wheel in Ai seconds;
  • for the i-th construction kit, Jonathan will attach the rear wheel Bi in seconds;
  • James and Jonathan cannot work on the same bicycle simultaneously;
  • the front wheel must be attached earlier than the rear wheel.

James and Jonathan are very experienced in assembling bicycles. In fact, given the information about all construction kits, they act optimally, such that the last wheel is attached as early as possible. However, the new director of the factory is not yet that experienced, so she needs some help. Please write her a program which tells how fast the twins assemble all today's bicycles, and how exactly this could be done.

Input

The first line of the input file contains N, the number of bicycle construction kits.

The second line contains N integers, the i-th of them equals Ai. The third line also contains N integers, the i-th of them equals Bi. All Ai and Bi are positive and do not exceed 10^9.

Output

In the first line, output the minimum time needed to assemble all bicycles.

The second line must contain integers. Of them, the i-th integer denotes the moment of time James starts to assemble the i-th construction kit. The third line must contain integers, this time for Jonathan. If several optimal scenarios exist, output any of them.

Examples

input.txt 3

1 2 3

2 1 3

output.txt 8

0 4 1

1 7 4

My solution is a greedy approach, sorting the sequences of pair (Ai, Bi) and (Ai+1, Bi+1). If execute the sequence in order i+1 -> i takes less time that i -> i+1, then swap them. So far it passes 13 test cases and fails on a test case with quite close result. The expected output is 29 while my solution yields 31. If anybody can help please give me a hint, thank you in advance.

I use Java, I implement a class called Job which stores a pair of Ai, Bi and the original index.

static class Job implements Comparable<Job> {
    long a;
    long b;
    int index;

    public Job(long a, long b, int index) {
        this.a = a;
        this.b = b;
        this.index = index;
    }

    @Override
    public int compareTo(Job that) {
        long thisTime = this.a + Math.max(this.b, that.a) + that.b;
        long thatTime = that.a + Math.max(this.a, that.b) + this.b;

        return Long.compare(thisTime, thatTime);
    }

    @Override
    public String toString() {
        return "(" + a + "," + b + ") - " + index;
    }
}

public static void solve(long[] a, long[] b, int[] order) throws IOException {
    long[][] start = new long[2][a.length];
    int prev = -1;
    for (int i : order) {
        if (prev == -1) {
            start[0][i] = 0;
            start[1][i] = a[i];
        } else {
            start[0][i] = start[0][prev] + a[prev];
            start[1][i] = Math.max(start[1][prev] + b[prev], start[0][i] + a[i]);
        }

        prev = i;
    }

    long time = start[1][prev] + b[prev];
    bw.write(time + "\n");
    for (int i = 0; i < start.length; ++i) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < start[0].length; ++j)
            sb.append(start[i][j] + " ");
        bw.write(sb.toString().trim() + "\n");
    }
}
$\endgroup$
  • $\begingroup$ Please show the input that should produce the answer $29.$ Also, you had better show us your algorithm in more detail. $\endgroup$ – saulspatz Apr 26 at 12:17
  • $\begingroup$ It seems ambiguous whether all the parts for a bicycle must come from the same indexed construction kit or not. $\endgroup$ – DanielV Apr 26 at 12:21
  • $\begingroup$ @saulspatz it's just the hint from the judge, they don't show the actual input. $\endgroup$ – Loc Truong Apr 26 at 12:24
  • $\begingroup$ Sounds like an application test for a dev-job... $\endgroup$ – denklo Apr 26 at 12:28
  • $\begingroup$ @denklo no, I'm following an algorithm course of ITMO on edx.org $\endgroup$ – Loc Truong Apr 26 at 12:28
0
$\begingroup$

This is a job shop scheduling problem. We can view James and Jonathon as two machines, each of which performs a specific process. Each job requires two processes performed in the same order for every job.

Although job shop scheduling is NP-complete in general, the two-machine instance can be solved in polynomial time by Johnson's rule.

$\endgroup$
  • $\begingroup$ I've implemented the code as Johnson's algorithm but it got RE with a specific test cases. I've posted the code on code review. If can check my code here, I've written unit test with all kind of input but I couldn't regenerate the error. codereview.stackexchange.com/questions/219238/… $\endgroup$ – Loc Truong Apr 27 at 11:44
  • $\begingroup$ I'm afraid I don't know enough java to answer your question. Sorry. $\endgroup$ – saulspatz Apr 27 at 11:45
  • $\begingroup$ I've successfully fixed the problem, it is due to TimShort in Java Arrays.sort, quite a headache to figure it out, because I couldn't see the log, I need help from the judge system to get the error log. Anyway, thanks for reminding me about this algorithm. :D $\endgroup$ – Loc Truong Apr 27 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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