in problem , parse input (integer) , simultaneously check if exists in data structure , if not add it.
input - 2 integers separated space of size >=1 , <= 1000000
i tried using hashmap , treemap (put() , containsvalue() method)- seems taking time. (5 out of 10 test cases exceeding time limit)
when using arraylist(add() , contains() method) - (4 out of 10 test cases exceeded time limit)
these operations performed inside 2nd loop , inside if condition.
iterations may varies follows : -
1st loop - 1 10
2nd loop - 1 100000
so guess higher order iteration in 2nd loop exceeds time limit.
is there other way perform task in lesser time .
problem :
a monk encounters n ponds , @ each pond fooditem(input 1) , pokemon(input 2) found .
the monk can feed item @ i'th pond pokemon @ pond if type matches. monk may have carry food items him before leaving feed pokemons. him find number of items must carry, to able pass through land safely.
explanation
at first pond gets item of type1 , feeds pokemon of type1.
at second pond gets item of type 2 , feeds pokemon of type2.
at third pond gets item of type 3 ,but pokemon of type4 . hence, has bring food item of type 4 him.
at fourth pond gets item of type 4. has item of type 3 , feeds pokemon.
at fifth pond gets items of type 2. has item of type 4 , feeds pokemon @ pond
class testclass { public static void main(string args[] ) throws exception { bufferedreader br = new bufferedreader(new inputstreamreader(system.in)); int t = integer.parseint(br.readline()); if(t<=10 && t>=1) { (int = 0; < t; i++) { int count=0; int numofponds = integer.parseint(br.readline()); if(numofponds<=100000 && numofponds>=1){ string[] str ; map m = new hashmap(); //list l = new arraylist(); for(int j=0 ; j< numofponds ;j++) { str = br.readline().split(" "); int foodtype = integer.parseint(str[0]); int poketype = integer.parseint(str[1]); if(foodtype<=1000000 && poketype<=1000000 && foodtype>=1 && poketype>=1 && foodtype != poketype){ m.put(j,foodtype); //l.add(foodtype); //if(!(l.contains(poketype))) if(!(m.containsvalue(poketype))) count++; //else if(l.contains(poketype)) else if(m.containsvalue(poketype)) { m.values().remove(poketype); // l.remove(integer.valueof(poketype)); } } } } system.out.println(count); } } } }
do not know trying other looking @ code. give quickest response . far finding value in hashset goes o(1) .
try below
import java.io.bufferedreader; import java.io.inputstreamreader; import java.util.hashset; import java.util.set; public class salestracking { public static void main(string args[] ) throws exception { bufferedreader br = new bufferedreader(new inputstreamreader(system.in)); int t = integer.parseint(br.readline()); if(t<=10 && t>=1) { (int = 0; < t; i++) { int count=0; int numofponds = integer.parseint(br.readline()); if(numofponds<=100000 && numofponds>=1){ string[] str ; //map m = new hashmap(); set m = new hashset(); for(int j=0 ; j< numofponds ;j++) { str = br.readline().split(" "); int foodtype = integer.parseint(str[0]); int poketype = integer.parseint(str[1]); if(foodtype<=1000000 && poketype<=1000000 && foodtype>=1 && poketype>=1 && foodtype != poketype){ m.add(foodtype); if(!(m.contains(poketype))) count++; else if(m.contains(poketype)) { m.remove(poketype); } } } } system.out.println(count); } } } } 
Comments
Post a Comment