Design and Analysis of Algorithms2019National University of SingaporeCS3230

Programming Assignment (Due Date: 7 Mar 2019)

For this programming assignment, you will not have to submit any written answers. Instead, you will submit all of them on CodeCrunch at https://codecrunch.comp.nus.edu.sg/. You will have to submit in Java or C++11 and the portal will stop accepting submissions after 7 Mar 2019 2359h so please start your assignment early.

Background Mr. Panda has started a new delivery company called Amazin which helps customers deliver pack-ages across very long distances. The company houses all its packages inside a warehouse where they are arranged neatly so that they can be located for delivery later. As the company grows, the number of packages it needs to manage in its warehouse has increased significantly and the human workers simply cannot keep up with the workload. Thus, the company has resorted to using automated robots to help them perform tasks around the warehouse. There are many different tasks to be done around the warehouse and efficiency is of utmost impor-tance in order to ensure the packages get delivered on time. Thus, Mr. Panda has hired you, his best programmer, to design and program the most efficient algorithms into the robots to perform several tasks around the warehouse. Programming Assignment (Due Date: 7 Mar 2019)2

The warehouse contains N charging points labelled 1 to N. These charging points can charge the robots almost instantly. Using this charging points as vertices, the warehouse can be modelled as an undirected, weighted graph with E edges between the charging points with weight equal to the amount of time taken to travel between them. Some pairs of charging points have no edge because of obstacles such as walls between them. The storage unit is at charging point 1 and delivery unit is at charging point N. You need to find a route for the robots to follow to transfer packages from storage to delivery. When following the route, the battery of the robot must be able to last at least as long as the highest weight edge along the path, since that is the maximum amount of time it has to travel without charging. You know you want the route to take at most T time units in total and charging time is negli-gible, however you do not need to choose the shortest path. Instead, you want to save costs by minimising how long the battery needs to last, since longer-lasting batteries are more expensive. Design an algorithm and write a program to calculate this minimum value. Input The first line of input will contain 3 integers, N, E and T as described above. The next E lines of input will each contain 3 integers, u, v and w representing an edge between vertices u and v with weight w. The edges in the input will be sorted in non-decreasing weight and the shortest path from 1 to N will be at most T time units. Output Your program simply needs to

output

one integer on a single line representing how long the battery needs to last in order to deliver the packages within T seconds.

Example Input

6 7 13 1 2 1 1 3 3 5 6 3 1 4 5 4 5 6 3 5 7 2 5 8 3

Example Output 7 Explanation In this example, we have a graph with 5 vertices and 7 edges. We want to find the minimum battery needed to deliver packages within 13 time units. There are 3 possible routes. The route 1, 4, 5, 6 is not feasible since the total length if 14 which is more than 13. This leaves 1, 3, 5, 6 and 1, 2, 5, 6, both of which have total length at most 13. The maximum edge along the routes are 7 and 8 respectively, of which the lowest value is 7 which is the answer. Limits 2   N   216; 1   E   217; 1   u < v   N; 1   w; T   109 Your algorithm should have a time complexity of O(E log2 E) and solve each test case within 3.0 seconds for Java and 1.0 seconds for C++. You should modify the template Battery.java and submit that file to CodeCrunch

Instead of sorting the packages by weight, you realise that the packages also have a unique ID from 1 to N and sorting by ID instead will make locating the packages much easier. Thus, you plan to use the robots to sort these packages in increasing ID instead of by weight.

The robots have the same constraints as described in the previous task and you want to also want to calculate, in this case, the minimum number of swaps needed where the boxes differ in weight by more than D grams.

Input

The first line of input will contain 2 integers, N and D as described above. The next line of input will contain N integers, representing the weight of the boxes in grams from left to right. The next line of input will contain N integers, IDs of the boxes from left to right. The IDs will form a permutation of the integers from 1 to N.

Output

Your program simply needs to output one integer on a single line representing the minimum num-ber of swaps needed where the boxes differ in weight by more than D grams.

Example Input

4 1

4 2 4 2

2 4 3 1

Example Output

3

Limits

1   N   216; 1   D; box weights   109

Your algorithm should have a time complexity of O(N log2 N) and solve each test case within 4.0 seconds for Java and 0.33 seconds for C++.

You should modify the template CountingSwaps.java to and submit that file to Code-Crunch