Problem Statement | ||||||||||||||||||||||||
| We have a group of N items (represented by integers from 1 to N), and we know
that there is some total order
defined for these items. You may assume that no two elements will be equal (for all a, b: a<b or b<a). However, it is expensive to compare two items. Your
task is to make a number of comparisons, and then output the sorted order. The
cost of determining if a < b is given by the bth integer of
element a of costs (space delimited), which is the same as the ath integer of element b. Naturally, you will be judged on the total cost of
the comparisons you make before outputting the sorted order. If your order is
incorrect, you will receive a 0. Otherwise, your score will be opt/cost, where
opt is the best cost anyone has achieved and cost is the total cost of the
comparisons you make (so your score for a test case will be between 0 and 1).
Your score for the problem will simply be the sum of your scores for the
individual test cases.
The cost for a single comparison will be an integer in [0,999]. Each test case will contain between 10 and 99 items. The number of elements, the true order, as well as all the costs are randomly generated. That is, all orderings are equally likely, and the costs are drawn uniformly at random. Your class should implement two methods. The first, initialize, will take a String[], cost, giving the costs of the comparisons as defined above, and return a int[] {a,b}, representing your first query: is a < b. The second method, query, will take a boolean, which will specify if a < b or not for your previous query. The method should return either (a) a int[] {a,b} representing the next query you wish to make, or (b) the sorted order. Your query method will be called until you (a) issue an invalid query or one you've already made ({a,b} is considered the same as {b,a}), (b) exceed the time or memory limit, (c) cause a runtime error, or (d) return a int[] with N elements. The memory limit will be 64 megabytes. You will be allowed a total of 60 seconds of execution time over all calls to your methods. For example, consider the case where N = 4 and you make 3 queries: {1,2}, {2,4}, {4,3}. If all of the queries return true, then the sorted order must be {1,2,4,3}, so that is what you would then return. To help you get started, here is an extremely poor solution (in terms of cost) that always gets the correct order:
public class CostlySorting{
int N;
int i, j;
int[] order;
/*
* Only uses the costs to figure out the number of elements.
* After that, does bubble sort.
*/
public int[] initialize(String[] costs){
N = costs.length;
order = new int[N];
for(int i = 0; i<order.length; i++){
order[i] = i+1;
}
i = 1; j = 1;
//First query asks: is item 2 less than item 1
//global variable i will hold the number of sorted items
//j will hold the index of the item currently being bubbled
//up towards the front of the order
return new int[]{2,1};
}
public int[] query(boolean result){
if(result){//order[j] < order[j-1]
int tmp = order[j];
order[j] = order[j-1];
order[j-1] = tmp;
if(j == 1){
//reached the beginning, bubble up the next thing
i++;
j = i;
}else{
//moved item forward 1 step, decrement j
j--;
}
}else{//order[j] > order[j-1]
i++;
j = i;
}
if(i == N){
//all done
return order;
}else{
//need to make another query
return new int[]{order[j],order[j-1]};
}
}
}
| ||||||||||||||||||||||||
Definition | ||||||||||||||||||||||||
| ||||||||||||||||||||||||