PKU 1633 - Gladiators

Autor da análise: schultzschultz

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1633

Resumo

Dizemos que uma sequência $A=\langle a_0,\dotsc,a_{2n-1}\rangle$ é admissível se forem verificadas as seguintes condições:

  • $A$ contém os elementos de 0 até $n-1$ exatamente duas vezes cada.
  • Para cada $j$ de 0 a $n-1$, se os elementos com valor $j$ ocorrem nas posições $x$ e $y$ de $A$ ($x < y$), então $A_i > j$ qualquer que seja $i$, $x < i < y$.

Dada uma sequência admissível $A$ como acima, definimos a dificuldade de $A$ como

(1)
\begin{align} \delta(A) = 1+\bigl\lvert\{i : 0 < i < 2n,\ A_{i-1} < A_i\}\bigr\rvert. \end{align}

Esse problema consiste em, dados números $n, k\in\mathbb N$, determinar o número de sequências de $2n$ elementos admissíveis e com dificuldade $k$. É sabido que $0\leqslant n\leqslant 50$ e $0\leqslant k\leqslant n$.

Solução

Uma possível solução é por programação dinâmica. Definindo $\displaystyle \genfrac{\langle}{\rangle}{0pt}{}{n}{k}$ como o número de sequências admissíveis de tamanho $2n$ e dificuldade $k$, verificamos os seguintes casos base:

  • $\displaystyle \genfrac{\langle}{\rangle}{0pt}{}{0}{k} = \begin{cases}1,&k=1\\0&k\neq1\end{cases}$, pois $\delta\bigl(\langle\rangle\bigr)=1$
  • $\displaystyle \genfrac{\langle}{\rangle}{0pt}{}{n}{0}=0,\quad\forall n\in\mathbb N$
  • $\displaystyle \genfrac{\langle}{\rangle}{0pt}{}{n}{k}=0,\quad\forall k > n,\quad\forall n\geqslant 1$

Esse último se verifica do fato de que se $x$ e $y$ ($x < y$) representam a posição do elemento $j$ numa sequência admissível $A=\langle a_0,\dotsc,a_{2n-1}\rangle$, então $A_{y-1}\geqslant A_{y}$, e portanto $\delta(A)\leqslant n$ se $n\geqslant 1$.

Para montar a recorrência da PD, suponha que nosso objetivo atual seja calcular $\displaystyle \genfrac{\langle}{\rangle}{0pt}{}{n}{k}$ com $n\geqslant 1$ e $0 < k\leqslant n$. Observe então que, em uma sequência admissível de tamanho $2n$, os elementos de valor $n-1$ são adjacentes. Dessa forma, ao contar o número de sequências admissíveis de tamanho $2n$, iremos separá-las em dois tipos de acordo com a dificuldade da sequência resultante ao se remover da sequência original os elementos de valor $n-1$.

Acontece que existem apenas dois valores possíveis para essa dificuldade. Se denotarmos por $A$ a sequência original e $A'$ a resultante, então certamente $\delta(A')\in\bigl\{\delta(A),\delta(A)-1\bigr\}$. Mais precisamente, se retirarmos os elementos com valor $n-1$ das posições $j$ e $j+1$, se $j+2\neq 2n\land\bigl(j=0\lor A_{j-1} < A_{j+2}\bigr)$, então havia uma "subida" entre os dois elementos removidos, e então $\delta(A') = \delta(A)$. E caso $j+2=2n\lor\bigl(j\neq 0\land A_{j-1} > A_{j+2}\bigr)$, eles estavam entre uma "descida" e $\delta(A')=\delta(A)-1$.

Conversamente, dada uma sequência admissível $A'=\langle a_0,\dotsc,a_{2(n-1)-1}\rangle$ tal que $\delta(A') = k$, existem precisamente $k$ posições em que se pode inserir elementos com valor $n-1$ de forma que a sequência resultante $A$ tenha dificuldade $\delta(A) = k$, cada uma correspondendo ao início da sequência ou a um índice $j\geqslant 1$ tal que $A_{j-1} < A_j$. E isso é feito de forma injetiva, pois variando $A'$ ou a posição em que inserimos os elementos de valor $n-1$ em $A'$, teremos sequências admissíveis de tamanho $2n$ distintas.

Da mesma forma, se tivermos $\delta(A') = k-1$, existirão $2n-k$ posições em que se pode inserir os elementos com valor $n-1$ de forma que a sequência admissível resultante $A$ tenha dificuldade $\delta(A)=k$. Essas posições correspondem às posições que não são o início da sequência e que não são um índice $j$ tal que $A_{j-1} < A_j$. Como há $2(n-1)+1 = 2n-1$ posições para inserção e $k-1$ posições em que não podemos inserir, temos $2n-1-(k-1) = 2n-k$ possibilidades de inserção. De forma similar, isso é feito de forma injetiva.

O que acabamos de concluir é que

(2)
\begin{align} \genfrac{\langle}{\rangle}{0pt}{}{n}{k} = k\genfrac{\langle}{\rangle}{0pt}{}{n-1}{k}+ (2n-k)\genfrac{\langle}{\rangle}{0pt}{}{n-1}{k-1}, \quad \forall n\geqslant 1,\quad 0 < k \leqslant n. \end{align}

Quanto à implementação, esta tem que ser feita com bignums. É de fácil verificação que

(3)
\begin{align} \genfrac{\langle}{\rangle}{0pt}{}{n}{k} \leqslant \bigl(2n\bigr)! \Longrightarrow \log_2\genfrac{\langle}{\rangle}{0pt}{}{n}{k} \leqslant \log_2\bigl(2n\bigr)! \in \mathcal O\bigl(n\log n\bigr). \end{align}

Logo, há $\mathcal O\bigl(n\log n\bigr)$ bits na representação do número $\displaystyle\genfrac{\langle}{\rangle}{0pt}{}{n}{k}$. Como fazemos $\mathcal O(1)$ operações de soma e multiplicação por escalar na computação de cada célula da PD, e existem $\mathcal O\bigl(n^2\bigr)$ delas, nosso algoritmo roda sob

(4)
\begin{align} \mathcal O\bigl(n^3\log n\bigr), \end{align}

o que é suficiente.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License