Seletiva IOI 2018 - Dia 3

Se você quiser se preparar para a OBI e seletiva, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Clique aqui para conferir a prova na íntegra *A seletiva da OBI 2017 foi feita para a IOI 2018

Cabo de Guerra

Comentário escrito por Caique Paiva

Conhecimento prévio necessário:

Knapsack DP

Primeiro, veja que, se $N \le 20$ , nós poderiamos brutar todas as somas possíveis, e conseguiriamos fazer o problema em $O(2^N)$ . Então, temos que achar uma maneira mais esperta de brutar as respostas. Com isso, perceba que fazer uma Knapsack dp é uma maneira de brutar todas as somas. Quando fazemos ela para achar uma soma máxima por exemplo, nós sempre salvamos a maior resposta anterior para não temos problema de complexidade, mas no final, nós testamos todos os casos possíveis.

Com essa observação, perceba que $F_i$ também é pequeno, então vamos fazer a seguinte dp:

$dp(pos, qtd, sum)$

Onde ela vai guardar se, no intervalo $[1, pos]$ usando $qtd$ números, a soma dá igual a $sum$ (A dp é 1 se é verdade, e é 0 caso contrário). Veja que $pos, qtd \le N \le 50$ e $sum \le N \cdot max(F_i) \le 50^2$ , ou seja, a quantidade de memória que estamos utilizando é $50^4 < 10^7$ , que cabe na memória e no tl. Com isso, o caso base da dp vai ser $dp(0, 0, 0) = 1$ , $dp(0, x, y) = 0, \forall (x > 0$ ou $y > 0)$ e $dp(x, y, z) = 0$ com $x >0$ e $y = 0$ ou $z = 0$ . Então, a transição vai ser

$dp(pos, qtd, sum) = max(dp(pos-1, qtd, sum), dp(pos-1, qtd-1, sum-F[pos]))$

(Os raciocínios são iguais a de uma knapsack padrão).

Com isso, como achar a solução do nosso problema. Bem, tem uma forma mais rápida que essa com matemática, mas uma possibilidade é ver que se $dp(n, n/2, i) = 1$ , então o valor de um grupo vai ser $i$ , e o de outro vai ser $SUM-i$ , onde $SUM = F_1+F_2+\cdots +F_n$ , e a diferença entre os dois grupos vai ser abs(SUM-2*i), então, basta criar uma variável auxiliar $res$ , e se $dp(n, n/2, i) = 1$ , então fazemos $res = max(res, abs(SUM-2*i))$ .

Clique aqui para conferir o código

Equipe

Comentário escrito por Estela Baron

Subtask 20 pontos: 1 <= N <= 20

Conhecimento prévio:

Bitmask

Como $N$ é pequeno, podemos simular todas as possibilidades de equipes. Para cada conjunto, vemos se a equipe é válida, ou seja, vemos se cada tema é dominado por pelo menos uma pessoa e se não é por pelo menos uma. Caso a equipe seja válida, atualizamos a resposta caso ela contenha o menor número de pessoas. Para gerar todos os subconjuntos, podemos utilizar uma bitmask, em que cada pessoa é representada por um bit. A complexidade fica $O(2^N)$ .

Subtask 80 pontos: 1 <= N <= 200

Conhecimento prévio:

Bitmask DP

Para cada pessoa, vamos representar as suas habilidades por meio de uma bitmask: mask_pessoa: se o $assunto_i$ for dominado, então o $bit_i$ estará ligado. Além disso, vamos criar também uma bitmask inversa: inv para representar os assuntos não dominados: todo assunto não dominado tem o bit aceso. Com isso, podemos representar um conjunto de assuntos dominados ou não como um inteiro. A partir disso, vamos fazer: dp[mask assuntos dominados][mask assuntos não dominados] = menor quantidade de pessoas para ter as duas masks.

Para calcular os estados, vamos fazer um loop e passar por cada pessoa:

em cada pessoa, vamos simular todas os estados possíveis, ou seja, desde dp[0][0] até dp[ $2^k - 1$ ][ $2^k - 1$ ]
para cada estado, vemos se vale ou não a pena adicionar a pessoa à equipe: fazemos dp[ $mask_i$ ][ $mask_j$ ] = min ( dp[ $mask_i$ ][ $mask_j$ ], 1 + dp[( $mask_i$ | mask_pessoa) - mask_pessoa][( $mask_j$ | inv) - inv]
Observe que precisamos realizar a operação OR| para só retirar o que precisamos.

Assim a resposta estará em dp[ $2^K -1$ ][ $2^K-1$ ]

A complexidade fica $O(N * 2^K * 2^K)$ .

Clique aqui para conferir o código

Tribo

Comentário escrito por Henrique Vianna

Conhecimento prévio necessário:

Perceba, primeiramente, que o problema pode ser reduzido ao seguinte: Dada uma árvore com pesos nas arestas, escolha um subconjunto de exatamente $k$ vértices de tal forma que a soma dos pesos das arestas necessárias para interligá-los seja mínima.

Intuitivamente, trata-se de um problema de DP em árvore. Define-se então:

$dp[u][j]$ é o minimo custo possível para escolher exatamente $j$ vértices na subárvore de $u$ , sendo $u$ um desses escolhidos.

Imagine agora que queremos calcular a $dp$ para um vértice especifico que chamaremos de $u$ . Para tanto, teremos que "juntar" as respostas de seus filhos. Logo, faremos uso de uma segunda $dp$ , de tal forma que:

$dp2[i][j]$ é o minimo custo possível para escolher exatamente $j$ vértices, considerando os $i$ primeiros filhos de $u$ .

Inicialmente, todos os valores de $dp2$ devem ser iguais a infinito, exceto $dp2[0][1]$ , que deve ser igual a $0$ . A recorrência de $dp2[i][j]$ é bastante similar à DP clássica da Knapsack: deve-se brutar, para o filho atual, quantos vértices de sua subárvore serão escolhidos. Chamaremos esse numero de $c$ . Sendo assim:

$dp2[i][j] = min(dp2[i - 1][j], dp2[i - 1][j - c] + dp[v][c] + w)$ , tal que $1 \leq c \leq j$

Na recorrência acima, assim como no código a seguir, $v$ é o filho sendo processado e $w$ é o peso da aresta entre $u$ e $v$ . Ao final, para termos os valores de $dp[u][j]$ de fato, basta fazermos:

$dp[u][j] = dp2[f][j]$ , sendo $f$ o numero de filhos de $u$ .

Note, entretanto, que assim como na Knapsack podemos facilmente eliminar a primeira informação da $dp2$ , utilizando a técnica conhecida como Memory Saving Trick. Basta passarmos por $j$ em ordem decrescente, assim como feito no código abaixo.

A resposta final será:

$resp = min(dp[i][k])$ , $1 \leq i \leq n$

Clique aqui para conferir o código