JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match Beta
Problem: CostlySorting

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

    
Class:CostlySorting
Method:initialize
Parameters:String[]
Returns:int[]
Method signature:int[] initialize(String[] cost)
 
Method:query
Parameters:boolean
Returns:int[]
Method signature:int[] query(boolean lessThan)
(be sure your methods are public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.