SPOJ STPAR

From Algorithmist
Jump to navigation Jump to search

95 - Street Parade[edit]

Summary[edit]

This problem requires us to re-order a given sequence of trucks with the use of a "temporary" side street. Since the trucks can move "one-way" to either the side street, or to the destination street - it essentially limits it to a simulation-based problem. The restrictions the problem places upon us should immediately alarm to a straightforward stack (side-street) and queue-based (destination street) solution.

Explanation[edit]

The heart of this problem relies on us to identify conditions when a particular sequence of trucks (taking into account of the side street stack as well) is invalid. If it's invalid, we can immediately return a "no" otherwise we continue to simulate until we reach the end of the input sequence. To identify when a particular combination is invalid we can note that if the next truck to move has a value greater than the top of the side-street stack then it's invalid. This is due to the fact that if we want to ultimately order it from smallest to largest - then the stack itself must be ordered (with the top having the smallest element) since you can't "drive back" to the input to re-arrange the stack itself. Now we have identified the invalid scenario, we must also know how we will simulate the trucks, as in how do we decide where the next truck goes (side-street stack or destination street) and whether to move the trucks in the stack or not. Note that since the trucks are labeled from 1 to n, this also means that the order we want is a contiguous sequence from 1 to n, hence we can identify at any given time the "value" of the truck we want in the destination street. If the value doesn't match we try to place it in the stack if we can (obviously if we can't then it's invalid).

As an example, given the combination 5, 1, 2, 4, 3. The first truck we want is value "1" because the destination is empty. However, our first truck has a value of 5, we check if we can place it in the stack which we can since it's empty. Then the next truck has a value of 1, exactly what we want - so we immediately place it into the destination. Since we already have one truck, our next desired value truck is 2 - which is exactly the next truck we see in our input. This gets sent to the destination immediately as well. The next truck is a truck of 4 which isn't the value we want in our destination as of yet, we check if the stack has this truck because if it does we move the stack first. Since this isn't the case, we check if 4 is smaller than the top element of the stack which it is. Then the next and last input is a truck value of 3, which we wanted next. Then we want a truck of value 4 - since our input is depleted we check the stack for it - and find it. The last element (5) gets placed into the destination afterwards as desired. This is a lengthy explanation of the diagrams present in the problem but in terms of our intended algorithm.

Some notes to take note of: if our input has depleted - we can already validate the sequence because at each step we ensure the consistency of the stack. Also we must take note that we must always check whether the stack has the truck value we are looking.

Implementations[edit]

A C++ implementation of the mentioned algorithm is detailed below:

stack<int> lane; int need = 1;
bool state = true;
for (int i = 0; i < order.size(); i++) {
	while (!lane.empty() && lane.top() == need) {
		need++;
		lane.pop();
	}
	if (order[i] == need) {
		need++;
	} else if (!lane.empty() && lane.top() < order[i]) {
		state = false;
		break;
	} else {
		lane.push(order[i]);
	}
}
if (state) cout << "yes" << "\n";
else cout << "no" << "\n";

Input[edit]

5
5 1 2 4 3 
0

Output[edit]

yes