- Practice
- Data Structures
- Stacks
- Waiter
- Discussions

# Waiter

# Waiter

pflau + 13 comments What makes this problem "difficult" is that the problem description is impossible to understand.

hhhung + 0 comments I agree with you on that :v

atamishali + 1 comment Exactly... :D

manojkumarsmks + 1 comment Exact thought when I read it.

nitinkumar154 + 1 comment i have read 4-5 times still nothing ...

amitrajitbose9 + 7 comments Don't you guys think that in Sample Case 2 A1 should be [9,3,3] instead of [3,3,9]

Please reply

shashisuman + 0 comments Yeah son

amirahbg + 0 comments yes exactly

quachtridat + 0 comments [deleted]elephantscabin + 0 comments yes!

sudipto_roy_1985 + 0 comments Exactly. I was trying to reason with that and was not able to understand the logic behind the stack contents.Poorly documented.

prz_marlewski + 0 comments I thought the same, I looked at the comments section to see if there is something about this sample case.

patelujjval2206 + 0 comments Totally agreed.

devl1n + 0 comments touchÃ©

Shailjakant + 0 comments hmm

john_canessa + 1 comment I agree that the description is very poor. Someone very smart said: If you are not able to describe it; you do not understand it. Perhaps this is a language issue.

rohanshenoy96 + 0 comments True, very poorly constructed description.

jsqihui + 0 comments True, I simply skip this one, avoid wasting more time

iamtodor + 2 comments 7 monthes had passed and nothing changed. Still can't understand.

john_canessa + 2 comments Perhaps the following might be of help:

macnis + 0 comments this was helpful Thanks

joydas1996 + 0 comments Thank you sir for the link. Now it's clear to me.

techniker + 0 comments haha

pacific1992 + 0 comments thanks a lot guys. I felt that I was dumb not to understand.

thebick + 0 comments Please see codeharrier's explanation in this discussion

techniker + 0 comments I've rated the problem 1 star

CliffyMk + 0 comments I just came to see who wrote this. or else i should.

ipg_2016069 + 1 comment [deleted]ipg_2016069 + 0 comments `#include

using namespace std;

int arr[1200]; void prime_no() {

`int count=1; for(int i=2; i<=10000; i++) { /* int i; cin>>i; */ if(i==2||i==3) { //cout<<i<<" "; arr[count++]=i; //count++; } else { int flag=1; for(int j=2; j<=sqrt(i); j++) { if(i%j==0) { flag=0; break; } } if(flag) { // cout<<i<<" "; arr[count++]=i; //count++; } //else //cout<<"Not prime"<<endl; }`

}

}

int main() { prime_no();

`int n,q; cin>>n>>q; int arr1[100000]; int top1=-1; for(int i=0; i<n; i++) cin>>arr1[++top1]; int arr2[100000]; int top2=-1; int arr3[100000]; int top3=-1; int arr4[100000]; int top4=-1; for(int i=1; i<=q; i++) { while(top1>=0) { int temp=arr1[top1--]; //cout<<"temp= "<<temp<<endl; if(temp%arr[i]==0) arr2[++top2]=temp; else arr3[++top3]=temp; } for(int i=top2; i>=0; i--) { // int temp=arr2[top2--]; arr4[++top4]=arr2[i]; } top2=-1; for(int i=0; i<=top3; i++) { int temp=arr3[i]; arr1[++top1]=temp; } top3=-1; }`

//cout<<"output= "<

// cout<<"2nd list"<=0; i--) cout<

}`

superwwt + 0 comments glad to know I'm not the only one thinking this

abhiramkaushik + 0 comments To the people who set questions like these, it is a humble request from many of us(I think) that you give atleast 2 sample test cases clearly pointing out the stuff which you might have left in the problem description so that we don't have to overthink a solution for a problem this simple. Thank you :D

codeharrier + 5 comments Hints:

- As you're reading the input, you're building the initial stack.

- Then you start taking plates off that to build the next two stacks. In each step you're turning just one stack into two new stacks.

- When printing a stack you print from top to bottom, like you're feeding the plates into the printer.

- Ignore the part about how many stacks (Q or Q+1) you end up with. If none of the numbers is divisible by a particular prime, that leaves a stack out. If all of the numbers remaining are divisible by the next prime, it ends the process early. So the Q or Q+1 claim is generally wrong.

- Google "free-online-calculator-use prime-number-generator" for an easy form-based way to generate the first 1200 primes (it starts with 2, so you just need to tell it 1200) with commas and spaces so you can just paste it into an initializer.

- The hard part of this problem is understanding the problem statement. After that it's straighforward popping and pushing (and some allocation/deallocation or juggling of the stacks, if you don't want to generate 1200 stacks before you print the first -- it won't make a difference in memory, since when you pop from one stack and push in another the total number of plates stays constant). If it had been presented better it would be an easy problem, except for the prime numbers, which aren't the point of the problem. It doesn't even have unreasonable time constraints that would force hacking around slow standard-library stack classes. It would have had way more than a 60% success rate if it were more clear.SnehaParekh + 1 comment Can you illustrate the problem statement using input/output example for Q > 2

codeharrier + 8 comments For Q = 2, you will have two prime numbers, 2 and 3. Let's say there are 10 plates, numbered randomly.

1 8 11 23 18 2 15 30 4 5

After the first step, you will have split this pile into two piles (shown from top to bottom, since they are pushdown stacks), the first containing all the plates with numbers divisible by 2 (the first prime number).

4 30 2 18 8

5 15 23 11 1Then the second pile is split into two piles based on whether they are divsible by 3 (the second prime number) and the three piles look like

4 30 2 18 8

15

1 11 23 5You print these top to bottom, first to last, and the printout looks like

4 30 2 18 8 15 1 11 23 5

SnehaParekh + 0 comments Thank you so much! :)

rajkan + 1 comment I feel that this example condradicts the example on the problem page.

if we follow the explanation as stated above then the sample problem provided along with the question should be as follows

5 1 3 4 7 6 5

Step1

6 4 3 7 5

Result

6 4 3 7 5

or am I missing something here. Please clarify. Thanks in advance.

codeharrier + 0 comments You are correct. I forgot about this: In the input data, "The leftmost value represents the bottom plate of the pile".

Which means that you have to read the data and push them into a stack first, reversing the input order. Then you start dividing them into smaller stacks.

manisha_9801 + 0 comments thanks sir....its very helpful indeed to understand this problem

gajendra1237 + 0 comments Sorry but your output should be. 8,18,2,30,4,15,5,23,11,1 Bcz it says top to bottom i.e form right to left(for stack).

gajendra1237 + 0 comments Indeed your explaination helped a lot to understand problem. Thank you.

mitsy_24 + 0 comments i think this is wrong interpretation!

tdvkiran + 0 comments *4 30 2 18 8 5 15 23 11 1

Then the second pile is split into two piles based on whether they are divsible by 3 (the second prime number) and the three piles look like

4 30 2 18 8 15 1 11 23 5

You print these top to bottom, first to last, and the printout looks like

4 30 2 18 8 15 1 11 23 5*

**i think output should be "4,30,2,18,8,15,5,23,11,1 "**if not please correct me!!thnaks in advance

svipul95_vs1 + 0 comments very well explained, thanks.

abhash_2610 + 3 comments Keeping 1200 primes ready helped me pass all the test cases.

nbkhope + 0 comments Yeah, I also needed that comma-separated list of the first 1200 primes.

rameshc10695 + 0 comments you can use seive algo to generate prime number which is quite efficient too.

lolapriego + 0 comments Same here, they should provide it. I found them here https://www.miniwebtool.com/list-of-prime-numbers/?to=10000

john_canessa + 0 comments Your description made it possible to understand the problem. Thanks a lot.

sruthiramani + 0 comments Although the problem demands a stack to achieve this, I was able to use only the concept of stack without actually juggling the numbers between stacks. I used a boolean array to keep track of numbers that are already printed and a flag to toggle the direction that I traverse the array every time - this helped me achieve the push/pop order. I could visualize this problem as eliminating all numbers divisible by ith prime in iteration i.

ranjithvj + 0 comments Thank you so much for the explanation. I wouldn't have solved it without your help !

taieddie8 + 1 comment Explanation 1 is wrong. After the first iteration, A1 should = [9,3,3] <- top because 9 is original on top of the A0 stack. I was able to pass all test cases but can't tell whether my solution was actually good or not.

thebickAsked to answer + 0 comments You are not the first to notice this. The problem setter has yet to correct the error.

ahmetb + 0 comments English please:

The plates that are not divisible by the Qth prime (which is our last iteration), from the last pile of plates.

imaginationsuper + 1 comment Java solution

import java.io.*; import java.util.*; public class Solution { private static Stack<Integer> data; private static Stack<Integer> div_stack; private static Stack<Integer> non_div_stack; public Solution(int[] raw_data){ data = new Stack<Integer>(); div_stack = new Stack<Integer>(); non_div_stack = new Stack<Integer>(); for (int i=0; i<raw_data.length; i++) data.push(raw_data[i]); } public void process_division(int Q){ int iter_num = Q; int curNum, prime=2; while (iter_num-->0){ non_div_stack.clear(); while (!data.isEmpty()){ curNum = data.pop(); if (curNum % prime == 0) div_stack.push(curNum); else non_div_stack.push(curNum); } prime = next_prime(prime); print_divisible(); data = (Stack<Integer>) non_div_stack.clone(); } while (!non_div_stack.isEmpty()) System.out.println(non_div_stack.pop()+""); } private int next_prime(int current_prime){ int prime = current_prime; boolean isPrime = false; while (!isPrime){ prime++; isPrime = true; for (int i=2; i<prime; i++){ if (prime % i == 0){ isPrime = false; break; } } } return prime; } private void print_divisible(){ while (!div_stack.isEmpty()){ System.out.println(div_stack.pop()+""); } } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); int[] data = new int[N]; for (int i=0; i<N; i++) data[i] = sc.nextInt(); Solution solution = new Solution(data); solution.process_division(Q); } }

taruna_kukreja + 0 comments Brilliant solution. I was close but was not able to figure out how to reassign values in data stack, your solution's non_div_stack.clone() method helped me. Thanks

hbzahid + 1 comment The problem says that M is either Q or Q+1. Isn't this incorrect? I think M is at most Q+1, but may not be exactly equal to Q+1 (or Q). Or maybe I incorrectly interpreted the question?

ks_apsAsked to answer + 1 comment The problem is correct. If you start with one stack and keep dividing by PâˆˆQ. After each division, you are left with either 1 stack (in case all the elements in the stack are either divisible by P or all the elements are not divisible by P), or 2 (in case some elements are divisible and some other are not).

99ashish + 0 comments if all the elements in the stack is prime number then we have more than 2 stack even , Am i correct??

mwj363 + 0 comments Easy to understand python solution

#!/bin/python3 import sys n, q = input().strip().split(' ') n, q = [int(n), int(q)] number = list(map(int, input().strip().split(' '))) # get the prime numbers lower = 2 upper = 10000 prime = [i for i in range(lower, upper + 1) if all(i % j != 0 for j in range(2, i))] # set Two-dimensional array A = [[] for i in range(q + 1)] B = [[] for i in range(q + 1)] A[0] = number # pick up plates from A stack for i in range(q): for j in range(len(A[i])): n = A[i].pop() if n % prime[i] == 0: B[i].append(n) else : A[i+1].append(n) # print plates in B for i in range(len(B)): while B[i] != []: print(B[i].pop(),) # print plates in A for i in range(len(A)): while A[i] != []: print(A[i].pop(),)

Jim10 + 0 comments Just solved it. I think that Explanation 1 has a flaw. After 1st iteration, A1 should be [9, 3, 3] and not [3, 3, 9].

yli131 + 0 comments public class Solution {

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); int[] primes = generate_prime_array(Q); Stack<Integer> stt = new Stack<>(); ArrayList<Integer> st = new ArrayList<>(); for(int i = 0; i < N; i++){ int x = sc.nextInt(); if(x % 2 == 0) st.add(x); else stt.push(x); } for(int j = 1; j < Q; j++){ ArrayList<Integer> ax = new ArrayList<>(); while(!stt.isEmpty()) ax.add(stt.pop()); for(int i = 0; i < ax.size(); i++){ if(ax.get(i) % primes[j] == 0) st.add(ax.get(i)); else stt.push(ax.get(i)); } } for(int c : st) System.out.println(c+ " "); ArrayList<Integer> sb = new ArrayList<>(); while(!stt.isEmpty()) sb.add(0,stt.pop()); for(int c : sb) System.out.println(c+ " "); } private static int[] generate_prime_array(int Q){ int[] result = new int[Q]; ArrayList<Integer> a = new ArrayList<>(); int status = 1; int num = 3; for ( int i = 2; i <=Q;){ for ( int j = 2 ; j <= Math.sqrt(num) ; j++ ){ if ( num%j == 0 ){status = 0;break;} } if (status != 0 ){ a.add(num); i++; } status = 1; num++; } a.add(0,2); for(int i = 0; i < Q; i++) result[i] = a.get(i); return result;`

} }

Sort 133 Discussions, By:

Please Login in order to post a comment