1
$\begingroup$

In a recent exam, I've been asked to solve the following problem:

The problem

Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players take turns in taking one coin from either "end" of the sequence. The value of that coin is added to their score.

Player 1 always starts. What is the maximum score that Player 1 can reach if Player 2 plays optimally (always minimizing their potential score)? What is the time-complexity of your algorithm? Prove your result.

Example:

Given the coin sequence $1,1,3,1,1,2$ one of the best playing sequence for player 1 is (scores denoted as the second tuple):

$$(\lbrack 1,1,3,1,1\rbrack,(2,0)) \rightarrow (\lbrack 1,1,3,1\rbrack,(2,1)) \rightarrow (\lbrack 1,3,1\rbrack,(3,1)) \rightarrow (\lbrack 3,1\rbrack, (3,2)) \rightarrow (\lbrack 1 \rbrack, (6,2)) \rightarrow (6,3)$$

The best score player 1 can reach is 6.

My solution

I'm just going to roughly outline my proof here, the formal correctness is not the point of this question. I'm more interested in the correctness of my asserted upper bound of complexity.

For the following I will use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\ldots,v_j$.

We iteratively create a DAG $G = (V, E, \gamma)$ as follows:
Create a vertex $v$ named $(1,n)$. Create or refer to the previously created vertices $v_1, v_2, v_3$, named $(2,n-1), (3,n), (1,n-2)$ respectively.

Create the edges $e_1 = (v,v_1), \gamma(e_1) = v_1$ and $e_2 = (v,v_2), \gamma(e_2) = max\lbrace v_1, v_n \rbrace$ and $e_3 = (v,v_3), \gamma(e_3) = v_n$. Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$ using a queue or similar to repeat the process until the sequence of coins denoted by the $v$ we iterate over is empty.

The number of edges in the created graph is bounded as follows: $\lvert E \rvert \leq 3\lvert V \rvert$.
The number of vertices is denoted by the following sum: $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$

We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.

This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

The problem I have with my answer is the upper bound for the number of vertices. I just pull that number out of thin air and my gut-feeling tells me that it is correct, but I might just be completely wrong.

Assuming that this is indeed a correct way to calculate the answer to the question, is my time-complexity argumentation sound?

|cite|improve this question
$\endgroup$
  • $\begingroup$ edits to make the title more useful are very much appreciated, as are suggestions to make this question more generally applicable $\endgroup$ – Vogel612 Sep 7 '18 at 21:19
2
$\begingroup$

Your algorithm may work, but FWIW it's more conventional to build game trees where the two players' moves form alternating layers of vertices rather than combining one move from each into a single edge. If you do this alpha-beta tree you get a graph with $|E| \le 2 |V|$ and $|V| = \frac{n(n+1)}{2}$.

We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.

This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

If $|V| = \Theta(n^2)$ and $|E| = \Theta(|V|)$ then $|V| * |E| = \Theta(n^4)$.

However, the propagation should actually take $\Theta(|V| + |E|) = \Theta(n^2)$.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.

Analysis of Your Argumentation

Here are some unclear or unconventional or inconsistent notations found in your post, which makes it difficult to understand or justify your arguments about time-complexity.

  • Does "$n|2$" mean $n$ is even? The standard convention for for "$a$ divides $b$" is $a|b$ according to math stackexchange answers and my years of practicing number theory. So $2|n$ is the prefered notation for $n$ is even. Anyway, in current case, I strongly prefer the plain English, $n$ is even.
  • "use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\cdots,v_j$.". People use $(i,j)$ generally to mean the pair of elements $i$ and $j$ or an open interval with ends $i$ and $j$. I would suggest you use $v_{i..j}$, where the two-dot notation $i..j$ are the convention for an integer interval.
  • "create a DAG $G = (V, E, \gamma)$". Do you mean an edge-weighted DAG?
  • "Create a vertex $v$ named $(1,n)$", which does not sound like English. It is better to write "Create a vertex $v$ that represents $1..n$".
  • "Create or refer to the previously created vertices $v_1,v_2,v_3$, named $(2,n−1),(3,n),(1,n−2)$ respectively". Although I can probably guess your intention, I am puzzled by the notations. Did you not notice that $v_1, v_2, \cdots, v_n$ appears as the coin values in the quoted problem? It looks like you want to use "$(2,n-1)$" as a name, which would be very confusing, since I have never seen any name of a person, a item, a variable or whatever starts and ends with a parenthesis for years except for very few social online accounts.
  • "Create the edges $e_1=(v,v_1),\gamma(e_1)=v_1$ and $e_2=(v,v_2), \gamma(e_2)=\max\{v_1,v_n\}$ and $e3=(v,v_3),\gamma(e_3)=v_n$". Now I am more into the wanderland. Is the codomain of $\gamma$ the vertices or the indices or the coin values?
  • "Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$". It is better to just write $v_1, v_2, v_3$.
  • "the sequence of coins denoted by the $v$". Didn't you say $v$ is a vertex?

Now Let us check your computation of the time-complexity.

  • "The number of edges in the created graph is bounded as follows: $|E|\le3|V|$. The number of vertices is denoted by the following sum: $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$". It looks like your estimates are correct, even though they can be tighter.
  • "We can determine the maximum score for player 1 by 'backpropagating' the edge weights through the graph, which takes $| V | * | E |$ steps. This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps". Since it is not clear how your backpropagating works exactly, it is hard to justify the number of steps. However, since $| V |* | E | \le |V| * (3 |V|) \le 3 n^4 $, you can only say that your algorithm takes $O(n^4)$ time.

In summary, even assuming that your algorithm is indeed a correct way, there is not enough clear information to fully justify or disprove your time-complexity argumentation. There are quite some room for you to improve the description of your algorithm and the time-complexity argumentation.

A Reference Solution

For simplicity, I will assume $n$ is even. Let $f(i,j)$ be the maximal score reachable by the first player if the two players start the game with the coins sequence $v_i, v_{i+1}, \cdots, v_j$.

Then we have the base cases, $$f(i, i+1)=\max(v_i, v_{i+1})$$ and recurrence relation $$ f(i,j) =\max(v_i+\min(f(i+2,j),\ f(i+1,j-1)),\ v_j + \min(f(i+1,j-1),\ f(i,j-2)))$$

The parameter pair $(i,j)$ of any $f(i,j)$ that appears in the course of computation of $f(1,n)$ will be such that $1\le i\le j\le n$ and $(i-1)+(n-j)$ must be even. The number of all such parameter pairs are $n^2/4$. The base case and the recurrence relation together shows that we need some $O(1)$ operations to obtain $f(i,j)$ for a new parameter pair $(i,j)$, assuming that the usual memorization technique in dynamic programming is used. So the time-complexity of computing $f(1,n)$ is $\Theta(n^2/4)=\Theta(n^2)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Peter correctly pinpointed the mistake in my bound of the backpropagation step. That should be a sum instead of a product. The domain of $\gamma$ is the edges of the graph. I'm using the notation I was taught for weighted edges, though the use of tuples to represent ranges makes the whole proof rather confusing. The reference solution you put here is really great, I will diligently study it. $\endgroup$ – Vogel612 Sep 8 '18 at 16:24
  • $\begingroup$ Your "backpropagation" strategy is probably what is called "recursion" by convention. I suspect that the $|E|$ steps in your analysis should better be considered as part of the $|V|$ steps. It would be clearer and easier to say your algorithm takes $|V|$ steps without involving $|E|$, anyway. Instead of writing the above judgement, I wrote a reference solution to illustrate it as well as other judgements. I am glad that my reference solution might be helpful for you. $\endgroup$ – John L. Sep 9 '18 at 6:33
2
$\begingroup$

Aren't you just overcomplicating things? I'd use an n x n matrix, and a nested loop that finds the result in about five lines of code in O (n^2).

Let b[i,j] = the amount by which you can beat your opponent if you are allowed to start on the subsequence i,j.

for 1 ≤ i ≤ n
    b[i, i] = v[i]

for 1 ≤ d ≤ n-1
    for 1 ≤ i ≤ n-d
        j = i + d
        b [i, j] = max (v[i] - b [i+1, j], v[j] - b [i, j-1])

You can beat your opponent by b [1, n], found in O (n^2). In O (n) you calculate the total value of all coins, and that gives you the best possible score.

Now with a very simple O (n^2) solution available, I wouldn't be totally surprised if someone came up with a much more complicated and much more clever solution that runs faster.

|cite|improve this answer
$\endgroup$

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.