What is the best solving algorithm for a game with stacks?

Question

Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose one card from the deck and we create a stack. Then when we chose the next if the card is a number lower than the top of the stack we add it to the stack. If the card is greater than the top of the stack we create a new stack with this card as the top. As we progress each card we draw from the deck should go either in one of the stacks (if it is less than the top of at least one of them) or create a new stack (if it is greater than the tops of all the stacks). If the card we drew can go to more than one stack it is our choice as to which stack it should go.

Game rule: If there is at least one stack were a card can go, we cannot create a new stack with this card as the top.

Game Objective: Finish the game (draw all n cards) with the minimum number of stacks.

My solution: Except the first time we draw were we have to create a stack, the next rounds, when we draw a card, we examine the top of each stack and find the minimum top call it M1 . Then if the card can go there (less than M1) we place it there. If it is greater than M1, we place it in the next minimum top we can. That way, we leave the tops that have greater numbers open for new numbers that could be greater than the one we drew this round, thus we minimize the possibility of creating a new stack.

My question: Is my solution correct? If it is, is there any solution better than mine? I think my solution is O(n*m), where n is the number of cards and m the number of stacks. Is there a solution with better complexity?

First Attempt at proving that the algorithm is optimal (based on links provided) : Let f be the number of stacks and A our algorithm and O an optimal algorithm. For i=1 card deck: then f(A) <= f(O), they will actually be equal f(A)=f(O), because each algorithm must create a stack with the first card (by rule). If f(A)<=f(O) for i=n then for i=n+1 (I don't know how to prove that f(A)<=f(O) here).

Second Attempt:

My proof: At the base the number of stacks will be equal as I mention above. Then suppose that the state $A^{i-1} \preceq O^{i-1} $ .

This means that the vectors will be the following

1. $(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k \prec \ell$

2. $(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} \prec u_{j+1}$.

In case number 1 the number of stacks in A is less than or equal to the one of O. I think it is obvious that if another element (card) was to be added to both of those vectors, the resulting vectors would be either equal in number of stacks (if only the left vector stack number increases) or again $(t_1,\dots,t_{k+1}) \prec (u_1,\dots,u_{\ell+1} )$ where $k+1 \prec \ell +1$. I have two problems here. The first is that I can't prove this for case number 2 and also this proof is if we supposed $A^{i-1} \prec O^{i-1} $.

Answer 1

Denote the current state of the stacks as a $k$-vector $t=(t_1,\dots,t_k)$, where $k$ counts the number of stacks, $t_i$ is the number on the top of the $i$th stack, and I assume you have sorted the $t_i$ so that $t_1 < t_2 < \dots < t_k$.

Define a total order on state vectors as follows: $(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k<\ell$, and $(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} < u_{j+1}$. Basically, this is comparing state vectors first by length (i.e., number of stacks), and comparing equal-length vectors by lexicographic order.

Now I suggest that you use the "greedy stays ahead" proof strategy, to try to prove by induction that if $A^i$ is the state of the stacks after $i$ steps of your algorithm and $O^i$ is the state after $i$ steps of the optimal algorithm, then $A^i \preceq O^i$. I will let you work out the details of this proof to see whether you can prove it. If you can do that, you will be done. Letting $A$ be the final state after running your algorithm and $O$ the final state after running the optimal algorithm, it follows that $A \preceq O$. Therefore, by the definition of $\prec$, $f(A) \le f(O)$. This shows that your algorithm is as good as the optimal algorithm.

In other words, use "greedy stays ahead" to try to prove your algorithm correct, but you'll need to keep track of more information than just the number of stacks used so far; you need a more fine-grained measure of what it means to be "ahead" than just the number of stacks.