OBI 2018 - Fase 3 - Programação Nível 1

Para conferir a prova na íntegra, clique aqui.

Troca

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Soma de Prefixos

A primeira ideia que temos é guardar dois vetores - um para os valores de cima e outro para os outros de baixo - e, para cada $L R$ , percorremos o intervalo invertendo os valores. No entanto, no pior caso, temos $10^5$ posições para percorrer $10^5$ vezes - com esse caso, o nosso código estouraria o limite de tempo (complexidade).

Como vimos que a ideia anterior não funciona, vamos tentar encontrar uma outra forma mais eficiente. Observe que o problema só quer saber quais são os valores na face de cima. Além do mais, se uma carta é virada uma quantidade par de vezes no total, quer dizer que o valor mostrado na parte de cima não vai mudar. Agora, se essa carta é virada uma quantidade ímpar no total, o valor na parte de cima tem que ser trocado. Com isso, concluímos que só precisamos saber a quantidade total que cada carta vai ser trocada.

Não podemos simplesmente adicionar $+1$ em todas as posições do intervalo $[L,R]$ , pois daria o mesmo problema da ideia inicial. Para resolver esse impasse, vamos utilizar a técnica de soma de prefixo - o novo valor atual é igual ao valor anterior mais o atual. Mais especificamente, vamos adicionar $+1$ na posição $L$ e $-1$ na posição $R + 1$ , pois, com a soma acumulada, adicionamos $+1$ em todas as posições de $L$ até o final e subtraímos $1$ de todas as posições a partir de $R+1$ - o que zera $1 - 1 = 0$ todas as posições fora do intervalo.

Com isso, para cada um dos $T$ intervalos, adicionamos $+1$ na posição $L$ e $-1$ na posição $R+1$ . Depois disso, percorremos todas as posições e mudamos o valor delas para o valor da posição anterior mais o valor atual.

A partir disso, temos a quantidade exata de vezes que cada carta foi virada. Veja que a complexidade fica boa, pois, em cada operação de $T$ , temos $O(1)$ . E só percorremos as $N$ posições uma vez, no fim.

Por fim, para definir qual é o valor da face de cima de cada carta, é necessário ver a paridade da quantidade de vezes que a carta foi virada, se for par, o valor é o mesmo do estado original, caso contrário, é o outro.

Clique aqui para conferir o código

Recibo de Compra

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Vamos fazer uma dp! Os estados serão $(int pos, int pes, int lastn)$ , onde $pos$ é a quantidade de produtos que precisamos pegar, $pes$ é o valor total que precisamos pegar, e $lastn$ o valor do último produto que a gente pegou. Então, a transição da dp vai ser

$dp(pos, pes, lastn) = \sum_{i = 1}^{lastn - 1} dp(pos-1, pes-i, i)$

Veja que, se fizéssemos uma knapsack normal, ou seja, só com os estados $(int pos, int pes)$ e tentassemos aplicar a mesma recorrência, teríamos:

$dp(pos, pes) = \sum_{i = 1}^{lastn-1} dp(pos-1, pes-i)$

Nós retornaríamos com a solução do problema, só que com ordem dos valores importando, ou seja, a escolha de valores $\{1, 4, 7 \}$ seria igual a $\{1, 7, 4\}$ , e além disso, poderíamos ter valores iguais. Por isso, colocamos o estado $lastn$ na dp, pois, além de garantir que não tenha valores iguais na compra, deixa as escolhas dos valores em ordem crescente, e então, não ocorre repetição.

No final, basta retornar $dp(k, r, r+1)$ . Essa dp roda em $O(K R^3)$ , pois temos $O(KR^2)$ estados, e a transição roda em $O(R)$ . Isso passa no problema, visto que $K, R$ são bem pequenos.

Clique aqui para ver o código

Bônus: Um problema parecido com esse é o Coin Combinations do cses, vale a pena dar uma olhada! (Link).

Pulo do Gato (P1)

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Podemos imaginar o grid (quadriculado) como um grafo, sendo que cada casa é um vértice, que possui arestas para todas as casas dentro do quadrado $5X5$ . Para descobrirmos a menor quantidade de pulos, temos que utilizar o algoritmo $bfs$ - mantemos uma fila com as posições que conseguimos alcançar e sempre pegamos a posição do início para analisarmos. Em cada posição da fila, em ordem, vamos ver se as outras casas contidas no quadrado $5X5$ (centrado na posição em análise) são lajotas e ainda não foram alcançadas. Se elas já tiverem sido alcançadas, quer dizer que há um caminho menor ou igual - então não há necessidade de adicionarmos na fila. Porém, se ela for uma lajota e não tiver sido alcançada, mudamos a distância mínima daquela casa para a distância da atual + 1 e adicionamos essa posição na fila.

Ao final, teremos analisado todas as casas alcançáveis. Portanto, basta imprimir a distância da posição $[L][C]$ . Podemos inicializar com todas distâncias iguais a -1, pois, se não for possível alcançar, vai imprimir -1.

Obs: no código, as distâncias mínimas foram armazenadas em $res[][ ]$ .

Clique aqui para conferir o código