<p>The game is defined by two integer parameters: n and k.
We are given an array of n sets:
<span class="math-container">$$S_1, S_2, ...., S_n$$</span>
such that, each of them is a subset of
<span class="math-container">$\{1, 2, ..., k\}$</span>.
Adversary picks a set <span class="math-container">$S_i$</span> in each turn and changes it into an empty set.
the cost that we must paid is a minimal number <span class="math-container">$t$</span> such that:
<span class="math-container">$$S_i \subseteq S_{i-t} \cup S_{i-t+2} \cup ... \cup S_{i-1}$$</span> or
<span class="math-container">$$S_i \subseteq S_{i+1} \cup S_{i+2} \cup ... \cup S_{i+t}$$</span>
if there is no such <span class="math-container">$t$</span> we must pay:
<span class="math-container">$$min(i, n-i)$$</span>
can we settle an upper bound on the amortized cost of <span class="math-container">$n-1$</span> turns?</p>

CC BY-SA 4.0
2022-06-22T20:07:01.370Z
Do you want a bound that holds for all possible arrays, and depends on only $n$ and $k$?  What regime of $k,n$ are you interested in?  Where $k$ is very small compared to $n$?  Where $k$ is comparable to $n$?  If there is no $t$ such that either equation holds, then am I correct to assume that the cost is $+\infty$?  What's the motivation for this question or the context where it arises?  What have you tried?  What is the best bound you have been able to find so far?
D.W.
CC BY-SA 4.0
2022-06-23T07:35:56.047Z
when there is not such $t$, we must paid $min(i, n-i)$. I interest in cases that $k = o(log n)$.
R.hatam
CC BY-SA 4.0
2022-06-23T07:42:22.327Z
I'm motivated to this problem because it is very helpfull tool for online algorithm analysis. I fact I want to solve this problem to settle an upper bound on competitive ratio on an online algorithm for chordal graphs coloring.
R.hatam
CC BY-SA 4.0
2022-06-23T17:22:55.437Z
Your question does not match your comment.  $\min(i,n-i)$ or $\min(n,n-i)$?  Please [edit] the question accordingly.
D.W.
CC BY-SA 4.0
2022-06-24T07:31:20.733Z
The quantifiers are not clear at all. An adversary gives the array of sets, and also the adversary picks the $i$ in each round, i.e., we have no choice anywhere in this game?
domotorp
<analysis-of-algorithms><amortized-analysis>
Frogs Game Amortized Analysis
R.hatam
# Frogs Game Amortized Analysis

(Asked by: username_0 on 2022-06-22)

The game is defined by two integer parameters: n and k.
We are given an array of n sets:
$$S\_1, S\_2, ...., S\_n$$
such that, each of them is a subset of
$\{1, 2, ..., k\}$.
Adversary picks a set $S\_i$ in each turn and changes it into an empty set.
the cost that we must paid is a minimal number $t$ such that:
$$S\_i \subseteq S\_{i-t} \cup S\_{i-t+2} \cup ... \cup S\_{i-1}$$ or
$$S\_i \subseteq S\_{i+1} \cup S\_{i+2} \cup ... \cup S\_{i+t}$$
if there is no such $t$ we must pay:
$$min(i, n-i)$$
can we settle an upper bound on the amortized cost of $n-1$ turns?

**Tags:** analysis-of-algorithms, amortized-analysis
> **Comments:**
> **username_1**: Do you want a bound that holds for all possible arrays, and depends on only $n$ and $k$?  What regime of $k,n$ are you interested in?  Where $k$ is very small compared to $n$?  Where $k$ is comparable to $n$?  If there is no $t$ such that either equation holds, then am I correct to assume that the cost is $+\infty$?  What's the motivation for this question or the context where it arises?  What have you tried?  What is the best bound you have been able to find so far?  
> **username_0**: when there is not such $t$, we must paid $min(i, n-i)$. I interest in cases that $k = o(log n)$.  
> **username_0**: I'm motivated to this problem because it is very helpfull tool for online algorithm analysis. I fact I want to solve this problem to settle an upper bound on competitive ratio on an online algorithm for chordal graphs coloring.  
> **username_1**: Your question does not match your comment.  $\min(i,n-i)$ or $\min(n,n-i)$?  Please [edit] the question accordingly.  
> **username_2**: The quantifiers are not clear at all. An adversary gives the array of sets, and also the adversary picks the $i$ in each round, i.e., we have no choice anywhere in this game?  

---

## 0 answers

