Official Analysis (C++)

Alternate Solution - Binary Search

We can binary search for the longest possible prefix. A prefix of length $i-1$ is just a prefix of length $i$ without a plate; if is it possible to wash all plates of prefix $i$ then it must also be possible to wash a prefix of $i-1$. Now we only need to simulate the stacking and washing. As the official analysis outlines, if plate $A$ is on top of plate $B$ on the same stack, then $A$ must be less than $B$, or else we cannot access the plate beneath it.

We can greedily place each plate on stack $i$ if the top plate on stack $i$ is larger than our current plate and is the smallest out of all the other soapy stacks. This is because it is always more optimal to satisfy a stricter constraint, rather overriding a broader one if we place the plate on another stack which the plate on top is not the smallest possible.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ifstream fin("dishes.in");
	int n;
	fin >> n;
	vector<int> order(n);
	for (int i = 0; i < n; i++) { fin >> order[i]; }