12715 - Watching the Kangaroo

All about problems in Volume 127. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
Location: Valladolid, Spain

Re: 12715 - Watching the Kangaroo

Post by MPC1984 » Fri Oct 17, 2014 3:33 pm

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. :wink:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12715 - Watching the Kangaroo

Post by brianfry713 » Fri Oct 17, 2014 11:48 pm

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).
Check input and AC output for thousands of problems on uDebug!

OneManArmy
New poster
Posts: 2
Joined: Wed Oct 08, 2014 7:16 am

Time Limit Exceeded: 12715 - Watching the Kangaroo

Post by OneManArmy » Fri Oct 31, 2014 1:23 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12715 - Watching the Kangaroo

Post by brianfry713 » Fri Oct 31, 2014 7:31 pm

Read this thread.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 127 (12700-12799)”