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:
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.
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[][ ]$$.