11995 - I Can Guess the Data Structure!

dTanMan · Post by **dTanMan** » Sat Feb 01, 2014 6:59 am

I still got a WA. Help, please? And um I should clear the code after an AC, right?

Thanks, brianfry. :)

brianfry713 · Post by **brianfry713** » Mon Feb 03, 2014 11:36 pm

Input:

Code: Select all

AC output: impossible

Fujibayashi · Post by **Fujibayashi** » Mon Mar 10, 2014 1:45 am

Guys, can you help me please! I have wrong answer, but my computer tell to me that I`am right!

Here my JAVACode:

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;


public class I_Can_Guess_the_Data_Structure {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
         
        boolean is_queue, is_stack, is_p_queue;
        Queue<Integer> queue = new LinkedList<Integer>();
        PriorityQueue<Integer> priority = new PriorityQueue<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        StringBuilder out = new StringBuilder();
        
        int n = 0;
 
        do {
            try{
                n = Integer.parseInt(in.readLine());
            } catch (IOException | NumberFormatException e) {
                return;
            }

            is_queue = is_stack = is_p_queue = true;
            stack.clear();
            queue.clear();
            priority.clear();
 
            for (int i = 0; i < n; i++) {
                int com = sc.nextInt();
                int val = sc.nextInt();
                
                if (com == 1) {
                    stack.push(val);
                    queue.add(val);
                    priority.add(-val);
                } else {
                    if (is_stack) {
                        if (stack.isEmpty()) is_stack = false;
                        else {
                            if (stack.pop() != val) is_stack = false;
                        }
                    }
                    if (is_queue) {
                        if (queue.isEmpty()) is_queue = false;
                        else {
                            if (queue.poll() != val) is_queue = false;
                        }
                    }
                    if (is_p_queue) {
                        if (priority.isEmpty()) is_p_queue = false;
                        else {
                            if (-1 * priority.poll() != val) is_p_queue = false;
                        }
                    }
                }
            }
            if (!is_queue && !is_stack && !is_p_queue)
                out.append("impossible\n");
            else if (is_queue && !(is_stack || is_p_queue))
                out.append("queue\n");
            else if (is_stack && !(is_queue || is_p_queue))
                out.append("stack\n");
            else if (is_p_queue && !(is_stack || is_queue))
                out.append("priority queue\n");
            else
                out.append("not sure\n");
            
        } while (n > -1); 
        System.out.print(out);
    }
}

brianfry713 · Post by **brianfry713** » Mon Mar 10, 2014 8:18 pm

Use class Main

sun_kuet · Post by **sun_kuet** » Mon Mar 17, 2014 11:37 am

Where is the problem , I think All test cases successfully pass through with my code .
But where is the Bug .

Code: Select all

Removed After AC

brianfry713 · Post by **brianfry713** » Mon Mar 17, 2014 11:32 pm

Change line 75 to:
if(!flag || (!st && !qu && !pqu))

Mrsuit · Post by **Mrsuit** » Mon May 05, 2014 8:46 pm

Hey, could anyone help me with my code? i'm getting time limit even when i made some fixes in order to make my code faster.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;


public class Main {

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

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> v1 = new LinkedList<Integer>(); //  N Dentro
Queue<Integer> v2 = new LinkedList<Integer>(); // N Fuera
Queue<Integer> v3 = new LinkedList<Integer>(); // N Luego de llenar los otros
StringBuilder sb = new StringBuilder();

int i=0;
String line;
Set<Integer> t1 = new HashSet<Integer>(); //Conjunto dentro
Set<Integer> t2= new HashSet <Integer>();//Conjunto fuera

Set<Integer> result;


while ((line=bf.readLine())!=null&& !line.trim().equals("")){

i=Integer.parseInt(line);
String[] lista= new String [2];
Stack<Integer> s = new Stack<Integer>(); // Primero en entrar, ultimo en salir 
Queue<Integer> q = new LinkedList<Integer>(); // Primero en entrar, primero en salir
Queue<Integer> pp = new PriorityQueue<Integer>(i, Collections.reverseOrder()); //Sale el mayor
int [] lista1=new int[2];
int[] lista2=new int[i]; // Dentro o Fuera



for (int j = 0; j < i; j++) {
	line=bf.readLine();
	lista=line.split(" ");
	lista1[0]=Integer.parseInt(lista[0]);
	lista1[1]=Integer.parseInt(lista[1]);
	lista2[j]=Integer.parseInt(lista[0]);
	if (lista1[0]==1){ //Llenado dentro
		v1.add(lista1[1]);
		t1.add(lista1[1]);
			}
	if (lista1[0]==2){ //Llenado fuera
		v2.add(lista1[1]);
		t2.add(lista1[1]);
	}
	}

int z1=0;
int z2=0;
int z3=0;
boolean t=true; // stack
boolean f=true; //queue
boolean w=true; // pp
for (int  j= 0;  j< lista2.length; j++) {
	
	if(lista2[j]==1 & v1.size()>0){
		s.push(v1.peek());
		q.add(v1.peek());
		pp.add(v1.peek());
		v3.add(v1.peek());
		v1.poll();
	}
	if(lista2[j]==2){
		z1=s.pop();
		z2=q.poll();
		z3=pp.poll();
		if (z1!=v2.peek()){
			t=false;
		}
		if (z2!=v2.peek()){
			f=false;
		}
		if (z3!=v2.peek()){
			w=false;
		}
		v2.poll();
	
}

}
result = new HashSet<Integer>();
result.addAll(t1);
result.retainAll(t2);  // t1 INTERSECCION t2

if (result.size()==0) {
	
	sb.append("impossible" +"\n");
	
}
else if (t==true & f==false & w==false){
	
	sb.append("stack"+"\n");
}
	else if (t==false & f==true & w==false){
		
		sb.append("queue"+"\n");
}
	else if (t==false & f==false & w==true){
		
		sb.append("priority queue"+"\n");
		
		//Dobles true
}
	else if (t==true & f==true & w==false){
		sb.append("not sure"+"\n");
		
}
	else if (t==true & f==false & w==true){
		
		sb.append("not sure"+"\n");
}
	else if (t==true & f==true & w==true){
		
		sb.append("not sure"+"\n");
}
	t1.clear();
	t2.clear();
	result.clear();
	
}
System.out.println(sb);

}
}

brianfry713 · Post by **brianfry713** » Mon May 05, 2014 9:18 pm

Try using BufferedWriter

Mrsuit · Post by **Mrsuit** » Tue May 06, 2014 7:10 am

I was reading about BufferedWriter and this thread when i saw little improvements for the other codes, so i first tried to improve mine by little changes and if none of these would work, i would finally use BufferedWriter.
Here is the weird thing, i just added this simple line.
("i" is the first integer of the input)

Code: Select all

if (i==1){
	System.out.println("not sure");
	break;

And now i get WA, so, wtf?.

Edit: I fixed it, though i'm still getting time limit, should i use BufferedWriter now or try something like StringTokenizer instead of an array?.

brianfry713 · Post by **brianfry713** » Wed May 07, 2014 9:16 pm

brianfry713 wrote:Try using BufferedWriter

Post your updated code.

Mrsuit · Post by **Mrsuit** » Thu May 08, 2014 8:08 am

Like i said, i just made a little fix.
Indeed i just added this :

Code: Select all

if (i==1){
		
		if (Integer.parseInt(lista[0])==1){
			System.out.println("not sure");
			break;
		}
		else{
			System.out.println("impossible");
			break;
		
			}
		
	
	}

"i" is the number of test cases.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;


public class pptesting {

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

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> v1 = new LinkedList<Integer>(); //  N Dentro
Queue<Integer> v2 = new LinkedList<Integer>(); // N Fuera
Queue<Integer> v3 = new LinkedList<Integer>(); // N Luego de llenar los otros
StringBuilder sb = new StringBuilder();

int i=0;
String line;
Set<Integer> t1 = new HashSet<Integer>(); //Conjunto dentro
Set<Integer> t2= new HashSet <Integer>();//Conjunto fuera

Set<Integer> result;


while ((line=bf.readLine())!=null&& !line.trim().equals("")){

i=Integer.parseInt(line);
String[] lista= new String [2];
Stack<Integer> s = new Stack<Integer>(); // Primero en entrar, ultimo en salir 
Queue<Integer> q = new LinkedList<Integer>(); // Primero en entrar, primero en salir
Queue<Integer> pp = new PriorityQueue<Integer>(i, Collections.reverseOrder()); //Sale el mayor
int [] lista1=new int[2];
int[] lista2=new int[i]; // Dentro o Fuera



for (int j = 0; j < i; j++) {
	line=bf.readLine();
	lista=line.split(" ");
	lista1[0]=Integer.parseInt(lista[0]);
	lista1[1]=Integer.parseInt(lista[1]);
	lista2[j]=Integer.parseInt(lista[0]);
	System.out.println(lista[0]);
	if (i==1){
		
		if (Integer.parseInt(lista[0])==1){
			System.out.println("not sure");
			break;
		}
		else{
			System.out.println("impossible");
			break;
		
			}
		
	
	}
	if (lista1[0]==1){ //Llenado dentro
		v1.add(lista1[1]);
		t1.add(lista1[1]);
			}
	if (lista1[0]==2){ //Llenado fuera
		v2.add(lista1[1]);
		t2.add(lista1[1]);
	}
	}

int z1=0;
int z2=0;
int z3=0;
boolean t=true; // stack
boolean f=true; //queue
boolean w=true; // pp
for (int  j= 0;  j< lista2.length; j++) {
	
	if(lista2[j]==1 & v1.size()>0){
		s.push(v1.peek());
		q.add(v1.peek());
		pp.add(v1.peek());
		v3.add(v1.peek());
		v1.poll();
	}
	if(lista2[j]==2){
		z1=s.pop();
		z2=q.poll();
		z3=pp.poll();
		if (z1!=v2.peek()){
			t=false;
		}
		if (z2!=v2.peek()){
			f=false;
		}
		if (z3!=v2.peek()){
			w=false;
		}
		v2.poll();
	
}

}
result = new HashSet<Integer>();
result.addAll(t1);
result.retainAll(t2);  // t1 INTERSECCION t2

if (result.size()==0) {
	
	sb.append("impossible" +"\n");
	
}
else if (t==true & f==false & w==false){
	
	sb.append("stack"+"\n");
}
	else if (t==false & f==true & w==false){
		
		sb.append("queue"+"\n");
}
	else if (t==false & f==false & w==true){
		
		sb.append("priority queue"+"\n");
		
		//Dobles true
}
	else if (t==true & f==true & w==false){
		sb.append("not sure"+"\n");
		
}
	else if (t==true & f==false & w==true){
		
		sb.append("not sure"+"\n");
}
	else if (t==true & f==true & w==true){
		
		sb.append("not sure"+"\n");
}
	t1.clear();
	t2.clear();
	result.clear();
	
}
System.out.println(sb);

}
}

brianfry713 · Post by **brianfry713** » Thu May 08, 2014 7:30 pm

use class Main

Mrsuit · Post by **Mrsuit** » Sat May 17, 2014 9:00 pm

brianfry713 wrote:use class Main

Sorry, i just forgot to change the class here, but i tried with class Main and i got WA. Do you see any mistake on my code besides that class thing?. Thanks

brianfry713 · Post by **brianfry713** » Tue May 20, 2014 10:30 pm

Post the code you'd submit. On the sample input you're printing 1's and 2's.

Mrsuit · Post by **Mrsuit** » Wed May 21, 2014 5:59 am

brianfry713 wrote:Post the code you'd submit. On the sample input you're printing 1's and 2's.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;


public class Main {

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

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> v1 = new LinkedList<Integer>(); //  N Dentro
Queue<Integer> v2 = new LinkedList<Integer>(); // N Fuera
Queue<Integer> v3 = new LinkedList<Integer>(); // N Luego de llenar los otros
StringBuilder sb = new StringBuilder();

int i=0;
String line;
Set<Integer> t1 = new HashSet<Integer>(); //Conjunto dentro
Set<Integer> t2= new HashSet <Integer>();//Conjunto fuera

Set<Integer> result;


while ((line=bf.readLine())!=null&& !line.trim().equals("")){

i=Integer.parseInt(line);
String[] lista= new String [2];
Stack<Integer> s = new Stack<Integer>(); // Primero en entrar, ultimo en salir 
Queue<Integer> q = new LinkedList<Integer>(); // Primero en entrar, primero en salir
Queue<Integer> pp = new PriorityQueue<Integer>(i, Collections.reverseOrder()); //Sale el mayor
int [] lista1=new int[2];
int[] lista2=new int[i]; // Dentro o Fuera



for (int j = 0; j < i; j++) {
	line=bf.readLine();
	lista=line.split(" ");
	lista1[0]=Integer.parseInt(lista[0]);
	lista1[1]=Integer.parseInt(lista[1]);
	lista2[j]=Integer.parseInt(lista[0]);
	
	if (i==1){
		
		if (Integer.parseInt(lista[0])==1){
			sb.append("not sure"+"\n");
			break;
		}
		else{
			sb.append("impossible"+"\n");
			break;
		
			}
		
	
	}
	if (lista1[0]==1){ //Llenado dentro
		v1.add(lista1[1]);
		t1.add(lista1[1]);
			}
	if (lista1[0]==2){ //Llenado fuera
		v2.add(lista1[1]);
		t2.add(lista1[1]);
	}
	}

int z1=0;
int z2=0;
int z3=0;
boolean t=true; // stack
boolean f=true; //queue
boolean w=true; // pp
for (int  j= 0;  j< lista2.length; j++) {
	
	if(lista2[j]==1 & v1.size()>0){
		s.push(v1.peek());
		q.add(v1.peek());
		pp.add(v1.peek());
		v3.add(v1.peek());
		v1.poll();
	}
	if(lista2[j]==2){
		z1=s.pop();
		z2=q.poll();
		z3=pp.poll();
		if (z1!=v2.peek()){
			t=false;
		}
		if (z2!=v2.peek()){
			f=false;
		}
		if (z3!=v2.peek()){
			w=false;
		}
		v2.poll();
	
}

}
result = new HashSet<Integer>();
result.addAll(t1);
result.retainAll(t2);  // t1 INTERSECCION t2

if (result.size()==0) {
	
	sb.append("impossible" +"\n");
	
}
else if (t==true & f==false & w==false){
	
	sb.append("stack"+"\n");
}
	else if (t==false & f==true & w==false){
		
		sb.append("queue"+"\n");
}
	else if (t==false & f==false & w==true){
		
		sb.append("priority queue"+"\n");
		
		//Dobles true
}
	else if (t==true & f==true & w==false){
		sb.append("not sure"+"\n");
		
}
	else if (t==true & f==false & w==true){
		
		sb.append("not sure"+"\n");
}
	else if (t==true & f==true & w==true){
		
		sb.append("not sure"+"\n");
}
	t1.clear();
	t2.clear();
	result.clear();
	
}
System.out.println(sb);

}
}

Got time limit now

OJ Board

11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!

Re: 11995 - I Can Guess the Data Structure!