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:
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:
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:
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$$