## 11995 - I Can Guess the Data Structure!

Moderator: Board moderators

dTanMan
New poster
Posts: 5
Joined: Sat Feb 01, 2014 5:22 am

### Re: 11995 - I Can Guess the Data Structure!

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

Code: Select all

``````Thanks, brianfry. :)
``````
Last edited by dTanMan on Sun Aug 03, 2014 4:04 pm, edited 1 time in total.

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

### Re: 11995 - I Can Guess the Data Structure!

Input:

Code: Select all

``````3
1 1
2 1
2 1
``````
AC output: impossible
Check input and AC output for thousands of problems on uDebug!

Fujibayashi
New poster
Posts: 1
Joined: Mon Mar 10, 2014 1:42 am

### Re: 11995 - I Can Guess the Data Structure!

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.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);

boolean is_queue, is_stack, is_p_queue;
PriorityQueue<Integer> priority = new PriorityQueue<Integer>();
Stack<Integer> stack = new Stack<Integer>();
StringBuilder out = new StringBuilder();

int n = 0;

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

### Re: 11995 - I Can Guess the Data Structure!

Use class Main
Check input and AC output for thousands of problems on uDebug!

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

### 11995 - I Can Guess the Data Structure!

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
``````
Last edited by sun_kuet on Tue Mar 18, 2014 8:14 pm, edited 1 time in total.

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

### Re: 11995 - I Can Guess the Data Structure!

Change line 75 to:
if(!flag || (!st && !qu && !pqu))
Check input and AC output for thousands of problems on uDebug!

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

### Re: 11995 - I Can Guess the Data Structure!

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.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
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 {

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;

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++) {
lista=line.split(" ");
lista1[0]=Integer.parseInt(lista[0]);
lista1[1]=Integer.parseInt(lista[1]);
lista2[j]=Integer.parseInt(lista[0]);
}
}
}

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

### Re: 11995 - I Can Guess the Data Structure!

Try using BufferedWriter
Check input and AC output for thousands of problems on uDebug!

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

brianfry713 wrote:Try using BufferedWriter
Check input and AC output for thousands of problems on uDebug!

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

### Re: 11995 - I Can Guess the Data Structure!

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.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
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 {

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;

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++) {
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;

}

}
}
}
}

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

### Re: 11995 - I Can Guess the Data Structure!

use class Main
Check input and AC output for thousands of problems on uDebug!

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

Post the code you'd submit. On the sample input you're printing 1's and 2's.
Check input and AC output for thousands of problems on uDebug!

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

### Re: 11995 - I Can Guess the Data Structure!

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.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
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 {

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;

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++) {
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;

}

}
}
}
}

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());
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.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