YassirSalama3's blog

By YassirSalama3, 3 hours ago, In English

Hello Codeforces Community. I came up with a problem for you today. Hope you enjoy it!

Problem :

Given two integers $$$N$$$, and $$$K$$$. Two players A and B play a game on a grid of size $$$1\cdot K$$$. Each player has $$$N$$$ token.
We define a good sequence $$$c = [c_1,c_2,...,c_K]$$$ as a sequence of positive integers of length $$$K$$$, and its sum is equal to $$$N$$$, i.e, $$$c_1+c_2+...+c_K = N$$$.
Player A goes first, He chooses a good sequence $$$a$$$ (How he will partition his tokens on the grid). Then player B goes second, and chooses another good sequence $$$b$$$.
Let $$$s_i = b_i+b_{i+1}+...+b_K$$$. We define the value of the game as $$$\displaystyle T(a,b) = \sum_{k=1}^K k\cdot a_k \cdot s_k$$$.
We also define the value of the sequence $$$b$$$ as $$$Val(b) = max(\{T(u,b)$$$ $$$/$$$ $$$u$$$ is a good sequence $$$ \})$$$.
Finally, the score of the game is $$$\displaystyle Score(a,b) = \frac{T(a,b)}{Val(b)}$$$.

Player A is trying to maximize the score of the game, while player B is trying to minimize it.

If both players are playing optimally, find the maximal score that player A can achieve, and the sequences $$$a$$$ and $$$b$$$ to achieve it.

Smaller cases : find the maximal score for $$$K=10$$$ and $$$N=100$$$, and the sequences $$$a$$$ and $$$b$$$ to achieve it.

Generalization of the problem :

We define a good sequence as a sequence $$$c = [c_1,c_2,...,c_K]$$$ such that $$$c_1+c_2+...+c_K=1$$$ and $$$c_i \in [0,1]$$$ for $$$1\le i \le K$$$. Find the maximal score that player A can achieve, and the sequences $$$a$$$ and $$$b$$$ to achieve it. (The process of the game is the same)

  • Vote: I like it
  • +1
  • Vote: I do not like it