12715 - Watching the Kangaroo

[MPC1984]

Hi everybody!

I have TLE veredict with this problem, how can I improve the algorithm?

Here is the Java code:

Code: Select all

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader entrada = new BufferedReader(new InputStreamReader(System.in));
        BufferedOutputStream salida = new BufferedOutputStream(System.out);
        String[] datos;
        int i, j, k, numVentanas, numCanguros;
        ArrayList<Long> izquierdas = new ArrayList<Long>();
        ArrayList<Long> derechas = new ArrayList<Long>();
        ArrayList<Long> rangos = new ArrayList<Long>();
        long posicionCanguro, min1, min2;
        int numCasosPrueba = Integer.parseInt(entrada.readLine());
        for (i = 1; i <= numCasosPrueba; i++) {
            salida.write(("Case " + i + ":\n").getBytes());
            datos = entrada.readLine().split(" ");
            numVentanas = Integer.parseInt(datos[0]);
            numCanguros = Integer.parseInt(datos[1]);
            for (j = 0; j < numVentanas; j++) {
                datos = entrada.readLine().split(" ");
                izquierdas.add(Long.parseLong(datos[0]));
                derechas.add(Long.parseLong(datos[1]));
            }
            for (j = 0; j < numCanguros; j++) {
                posicionCanguro = Long.parseLong(entrada.readLine());
                for (k = 0; k < numVentanas; k++) {
                    min1 = posicionCanguro - izquierdas.get(k);
                    min2 = derechas.get(k) - posicionCanguro;
                    if (min1 < 0 || min2 < 0) {
                        rangos.add(0l);
                    } else {
                        if (min1 <= min2) {
                            rangos.add(min1);
                        } else {
                            rangos.add(min2);
                        }
                    }
                }
                Collections.sort(rangos);
                salida.write((rangos.get(rangos.size() - 1) + "\n").getBytes());
                rangos.clear();
            }
            izquierdas.clear();
            derechas.clear();
        }
        salida.flush();
        salida.close();
    }
}

Thanks in advance.

[brianfry713]

I got AC by first reading the entire input for a test case before printing any output.
Sort the screens in increasing L, in case of ties then decreasing R. Remove the screens that are covered by others.
Sort the positions by increasing x, keep track of what order they appeared in the input.
Initialize an iterator to the first screen.
Iterate through the positions in increasing x. While the current screen iterator's R is <= the current x, increment it. While the next screen iterator's coverage is > than the current one, increment the screen iterator. Now you can answer the coverage for the current position.
Report the coverage in the input order.
Total complexity for each test case is O(N log N + M log M).

[OneManArmy]

Need Help Getting Time Limit Exceeded
Here is my approach
First i sort the range in descending order according to range lenght [R-L] then for each item from top of the list add it to the newList then removed all items
which items conflicts with the top item and go on [may be here my algorithm/code is not efficient] Heres the code for only this part

Code: Select all

			ArrayList<Pair> newList = new ArrayList<Pair>();
			while(!list.isEmpty()){
				long left = list.get(0).x;
				long right = list.get(0).y;
				newList.add(list.remove(0));
				
				ArrayList<Pair> it = new ArrayList<Pair>();
				it.addAll(list);

				for(int c = 0;c<it.size();c++){
					Pair ch = it.get(c);
					if(ch.x>=left && ch.y<=right){
						list.remove(new Pair(ch.x,ch.y));
					}
				}
			}

Then for each query i search on total list and took the biggest value.
Heres the total source code

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
	public static FI k;
	public static FO z;
	public static void main(String [] args)throws IOException{
		k = new FI(System.in);
		z = new FO();
		
		int T = k.nextInt();
		int test = 1;
		while(T-->0){
			long range = k.nextLong();
			long query = k.nextLong();
			ArrayList<Pair> list = new ArrayList<Pair>();
			

			while(range-->0){
				long x = k.nextLong();
				long y = k.nextLong();
				list.add(new Pair(x,y));
			}
			
			Collections.sort(list);
			
			ArrayList<Pair> newList = new ArrayList<Pair>();
			while(!list.isEmpty()){
				long left = list.get(0).x;
				long right = list.get(0).y;
				newList.add(list.remove(0));
				
				ArrayList<Pair> it = new ArrayList<Pair>();
				it.addAll(list);

				for(int c = 0;c<it.size();c++){
					Pair ch = it.get(c);
					if(ch.x>=left && ch.y<=right){
						list.remove(new Pair(ch.x,ch.y));
					}
				}
			}
			

			z.println("Case "+(test++)+":");
			while(query-->0){
				long qq = k.nextLong();
				long max = 0;
				for(int c = 0;c<newList.size();c++){
					long x = newList.get(c).x;
					long y = newList.get(c).y;
					if(qq>=x && qq<=y){
						long m = Math.min(qq-x,y-qq);
						if(m>max){
							max = m;
						}
					}
				}
				z.println(max);
			}
	
		}
		z.flush();

	}
	

	public static class Pair implements Comparable<Pair>{
		long x,y,w;
		public Pair(long x,long y){
			this.x = x;
			this.y = y;
			w = y-x;
		}
		
		@Override
		public int compareTo(Pair o) {
			int x = ((Long)w).compareTo(((Pair)o).w);
			x *= (-1);
			return x;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;

			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
	}

	
	   public static class FI{
	        InputStream in; byte b; byte[] buf; int bi, bz;
	        FI(InputStream I) { in=I; buf=new byte[65536]; bi=bz=0; read(); }
	        void skip() { while (b >= 0 && b <= 32) read(); }
	        void read() {
	            if (bi==bz) {
	                bi=0; try { bz=in.read(buf); } catch(Exception e) { bz=-1; } }
	            b = bz == -1 ? -1 : buf[bi++];  }
	        // Optional methods
	        boolean hasNext() { skip(); return b >= 0; }
	        String next() {
	            StringBuilder sb = new StringBuilder();
	            for (skip(); b > 32; read()) sb.append((char)b);
	            return sb.length() == 0 ? null : sb.toString(); }
	        int nextInt() {
	            int i=0; boolean s=false; skip();
	            if (b == '-') { s=true; read(); }
	            for (; b > 32; read()) i = i*10 + b-48; return s ? -i : i; }
	        long nextLong() {
	            long i=0; boolean s=false; skip();
	            if (b == '-') { s=true; read(); }
	            for (; b > 32; read()) i = i*10 + b-48; return s ? -i : i; }
	        String nextLine() {
	            StringBuilder sb = new StringBuilder();
	            for (; b != 10 && b != 13; read()) sb.append((char)b);
	            while (b == 10 || b == 13) read(); return sb.toString(); }
	        String nextRealLine() {
	            StringBuilder sb = new StringBuilder();
	            for (; b != 10 && b != 13; read()) sb.append((char)b);
	            byte p = b; read();
	            if ((p == 10 && b == 13) || (p == 13 && b == 10)) read();
	            return sb.toString(); }
	    }
	   
	   
	    public static class FO extends PrintWriter {
	        FO() { super(new BufferedOutputStream(System.out)); }
	    }
}

[brianfry713]

Read this thread.