Fortune at El Dorado

From Progteam

Revision as of 03:23, 28 September 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.



Fortune at El Dorado
Problem Number 2899
Sorter: Uncategorized
Source: Tehran 2005
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2899



Fortune at El Dorado is problem number 2899 on the Peking University ACM site. The problem is to find, given some points in the x/y plane and a maximum area, the largest number of points which can be enclosed in a rectangle of the given area or less.


Contents

Underlying Concept

Figure 1: this searches over the entire plane

The basic idea is to do an exhaustive search over all possible rectangles and see what is the largest number of points ever contained in a single rectangle. One way to do this (Christian's Solution) is outlined in Figure 1. Every rectangle that is searched through is defined by three numbers, x1 (the left boundary), x2 (the right boundary), and y_top (the top boundary). The bottom boundary of the rectangle is then set to be the lowest possible such that the total area is still below the maximum. In this way, we can choose all possible combinations of x1, x2, and y_top to obtain every possible region with area less than the max. This is clearly n-cubed operations to find every rectangle, and then to count the number of points contained in that rectangle brings the complexity to n-to-the-forth, or around 1 trillion operations minimum. This could certainly do with some improvement, and it will have to be much more efficient to be accepted by the judges.

The goal is to strip out all redundant cases. For instance, the borders of the rectangle pictured in Figure 1 are not directly up against the points; there is room in between. If, say, x1 were moved slightly right, clearly no points would be gained or lost, so why reprocess the whole thing for that change? The key is to only move the borders to positions where the number of points can change. It can be shown that this will only happen at a border than contains a point. Processing any boundaries that don't contain a point would be wasteful, as they cannot possibly improve the count.

Figure 2: only rows and columns with points are considered

Data representation

The data should not be viewed as a continuous plane, but as discrete rows and columns, as shown in Figure 2. For each row, we need to record its y coordinate, and for each column, we record its x coordinate, and a list of all points in that column, sorted by row number. This way we can easily jump from column to column without worrying how much spaces exists between them. This will let us search every possible rectangle without wasting any computation on unnecessary boundary changes.

Algorithm

A graphical representation of the optimized solution

From here, the algorithm is fairly straightforward, if not a little bothersome. Again, we choose all possible x1 and x2, however, unlike last time they don't refer to x coordinates, but column numbers. For each (x1,x2) pair, we iterate through every possible y_top; y_top being one of the rows. Like before, this defines a rectangle by giving 3 of its sides and its area. For a given triplet (x1, x2, y_top), we want to find all points in columns between (inclusive) x1 and x2, which are below y_top, and above y_top+max_area/(coordinateOf(x2)-coordinateOf(x1)). So for every (x1, x2, y_top), we search down the lists for x1 through x2, looking for points that fit within the y constraints. This gives a solution which clocks in just barely under the judge's limit, but under nonetheless.

Solution

import java.util.*;

public class Main{

    public static Scanner in;
  
    static int numtrees,maxarea;

    static int[] xpos;  //This specifies the x coordinate of each of the columns
    static int[] ypos;  //This specifies the y coordinate of each of the columns
   
    //For each column, a sorted list of integers, one for
    //each point in the column.  The integers 
    //correspond to the y coordinate of these points.
    static List[] column;

    
    public static void main(String[] args){
        in=new Scanner(System.in);
   
        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();

        for(int i=0;i<N;i++){
            solve();   //Do this scenario
        }
    }

    public static void solve(){
        numtrees=in.nextInt(); //Get the number of trees
        maxarea=in.nextInt();  //and max area

        build();  //Build the data representation of the problem
    
        int maxcount=-1; 

        for(int x1=0;x1<xpos.length;x1++){
            for(int x2=x1;x2<xpos.length && xpos[x2]<=xpos[x1]+maxarea;x2++){
                //X1 is the leftmost column, X2 the rightmost column
                for(int ytop=0;ytop<ypos.length;ytop++){
                    //ytop goes through each of the rows
                    int count=0;
            
                    //Get the sum over all the coulmns
                    for(int x=x1;x<=x2;x++){
                        //Count up all the points in this column in range
                        for(Object o:column[x]){
                            int y=(Integer)o;
                
                            int width=(xpos[x2]-xpos[x1]);    

                            if(0==width)
                                width=1;
                
                            if(y>ypos[ytop]+maxarea/width)
                                break;
                
                            if(y>=ypos[ytop])
                                count++;
                
                        }
                    }
            
                    //See if it's the max
                    if(count>maxcount)
                        maxcount=count;
            
                }
            }
        }

        System.out.println(maxcount);
    }

    static void build(){
        List[] bin_x = new List[1001];

        boolean[] bin_y =new boolean[1001];

        int xcount=0,ycount=0;

        for(int i=0;i<numtrees;i++){
            int x=in.nextInt();
            int y=in.nextInt();

            if(null==bin_x[x]){
                bin_x[x]=new List();
                xcount++;
            }
        
            bin_x[x].insertSorted(y);

            if(!bin_y[y]){
                bin_y[y]=true;
                ycount++;
            }
        }

        xpos=new int[xcount];
        ypos=new int[ycount];

        column=new List[xcount];
        next_y=new List[xcount][ycount];

        int xi=0,yi=0;

        for(int i=0;i<1001;i++){
            if(null!=bin_x[i]){
                xpos[xi]=i;
                column[xi++]=bin_x[i];
            }

            if(bin_y[i]){
                ypos[yi++]=i;
            }
        }
    }
}

   
class List<T extends Comparable> implements Iterable<T>{

    /** Core stuff **/

    class Node{
        T el;
        Node next;
    }
    
    class Iter implements Iterator<T>{
        Node ptr;

        public boolean hasNext(){
            return ptr.next!=null;
        }
        public T next(){
            ptr=ptr.next;return ptr.el;
        }
        public void remove(){}

        /** Optional Methods **/

        /** A list containing all the unvisited elements including this one **/
        /** Note! The list returned by this cannot be modified! **/
        public List<T> getTail(){
            List<T> res=new List<T>();

            res.head=ptr;

            return res;
        }
    }

    Node head,tail;
    int size;

    public List(){
        head=new Node();
        tail=head;
        
        head.next=null;
        size=0;
    }

    public boolean add(T v){
     
        Node n=new Node();
        n.el=v;
        n.next=null;

        tail.next=n;
        tail=n;
        ++size;
        return true;
    }

    public Iter iterator(){
        Iter i=new Iter();
        i.ptr=head;
        return i;
    }

    /** Sorting Related Options **/

    /** Assuming the list is sorted, insert the item into sorted order **/
    public void insertSorted(T x){
        Node tmp=head;

        while(true){
            if(null==tmp.next){
                Node n=new Node();

                n.el=x;
                n.next=null;
                tmp.next=n;
                return;
            }

            if((tmp.next.el).compareTo(x)>=0){
                Node n=new Node();

                n.el=x;
                n.next=tmp.next;
                tmp.next=n;

                return;
            }

            tmp=tmp.next;
        }
    }
}
Personal tools