2
$\begingroup$

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} $.

$\endgroup$
  • $\begingroup$ You gave a greedy heuristic. There are standard ways of showing that such heuristics are optimal. $\endgroup$ – Yuval Filmus Oct 27 at 19:23
  • $\begingroup$ cs.stackexchange.com/q/59964/755, cs.stackexchange.com/q/65284/755 $\endgroup$ – D.W. Oct 28 at 8:05
  • $\begingroup$ @D.W. I read both of the links you commented, but I don't exactly understand how to implement those theories here. For example, I don't understand how the jobs in O( ) could be different than the jobs in A, since I thought of O() based on the function of A. $\endgroup$ – maverick98 Oct 28 at 10:19
  • $\begingroup$ @D.W. Can you see my proposed proof, I can't get it any further $\endgroup$ – maverick98 Oct 29 at 19:07
  • $\begingroup$ Thanks for editing. I don't understand what you mean by "case number 2". I suggest trying to write out your proof in more detail, and being clearer at what step you are stuck. Try to avoid "I think it is obvious that.." and instead spell out the reason why. Try to make the structure of your proof clearer. If it is a proof by induction, follow the standard structure for a proof by induction; what is the induction predicate, the base case, and the inductive step. I don't understand why it is a problem that we supposed $A^{i-1} \prec O^{i-1}$; are you familiar with proof by induction? $\endgroup$ – D.W. Oct 29 at 23:04
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you please see the edit I made in my post with another try at proving what you said? $\endgroup$ – maverick98 Oct 29 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.