Seletiva IOI 2020 - Dia 2

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 2019 foi feita para a IOI 2020

Saldo

Comentário escrito por Estela Baron

Subtask 1: K = 0

Para resolver esta tarefa, basta verificar se a soma total dos saldos é igual a 0.

Subtask 2: N <= 16

Conhecimento prévio:

• Bitmask

Vamos estabelecer o vértice 1 como a raiz da árvore. Com a técnica de representar um conjunto em um número (bitmask), podemos gerar todos os subconjuntos que representam as estradas que foram retiradas. Para cada conjunto, basta verificar se tem k estradas retiradas e se a soma de cada componente é igual a zero - para verificar, podemos chamar uma dfs que vá percorrendo toda a árvore, mas que separe os valores quando passar por uma estrada retirada. Se as condições anteriores forem verificadas, precisamos somar os custos e ver se é menor que o custo anterior - caso exista. Assim, obtemos a nossa resposta em $O(2^N * N)$, que passa para o limite da subtask.

Subtask 3: N <=100 e |Di| <= 1000 e estrada i conecta as cidades i e i+1

Conhecimento prévio:

• DP

|Di| neste caso - enunciado do codeforces- deve ser |Ri|, ou seja, o saldo da cidade i. Nesta subtask, temos uma linha. Então, podemos pensar em fazer algum tipo de dp para calcular a resposta. Observe ainda que a condição de N<=100 nos possibilita inferir que K < 100, pois K < N. Vamos construir os nossos estados da seguinte maneira: dp[x : vertice_i][y: quantidade de estradas dos vértices anteriores destruídas] = menor custo possível para obter grupos com soma igual a zero com y estradas destruídas até o vértice x. Para construir esta dp, vamos imaginar que a nossa linha acaba no vértice x. Depois disso, vamos percorrer todas as posições dos vértices 1 até x-1 e ver qual valor obtemos ao destruir a estrada que liga aquele vértice_w ao seguinte. Para fazer o teste, verificamos por meio de uma soma de intervalos se a soma dos saldos dos vértices de w+1 até x é igual a zero. Caso seja zero, verificamos se dp[w][y-1] é um valor diferente de -1, significando que existe tal configuração, e somamos o custo da estrada que liga o vértice_w ao vértice_w+1. Por fim, caso seja o primeiro valor diferente de -1, vamos colocar que dp[x][y] = dp[w][y-1] + C_w. Caso contrário, atualizamos o valor para o mínimo: dp[x][y] = min(dp[x][y], dp[w][y-1] + C_w).

O caso inicial de cada vértice é dp[x][0] = 0 se a soma dos saldos de 1 até x for 0 ou dp[x][0] = -1 se a soma dos saldos de 1 até x for diferente de 0. A complexidade final fica O(N^3), pois temos N vértices para percorrer, no máximo N-1 para K e, para cada estado, percorremos o vetor para achar o menor valor de dp[w][y-1].

Subtask 4: N<=5000

Nesta tarefa, vamos adaptar a ideia da subtask anterior: vamos tentar achar uma forma de construir a dp[x][y] sem ter que percorrer todos os outros estados. Observe que, se a soma dos saldos da posição 1 até a posição x for diferente de zero, então não tem como encontrar uma configuração válida. No entanto, se for 0, podemos encontrar o menor valor de dp[w][y-1], tal que w seja algum vértice menor que x. Assim, sabemos que a soma acumulada até w é zero e podemos garantir que a soma de w+1 até x também é igual a zero. Com isso, basta fazer um for iterando pelo y e, dentro desse loop, um for para iterar pelas posições, lembrando de guardar o valor do menor dp[][] até x com y-1 estradas - e ir atualizando para as outras posições à medida que os outros valores vão sendo calculados.

A complexidade final fica $O(N^2)$.

Subtask 6: Sem restrições adicionais - solução final

Conhecimento prévio necessário:

• DFS
• Árvores

Vamos pensar em uma árvore e suas sub-árvores. Se a soma dos saldos totais da árvore for diferente de 0, nem precisamos calcular mais nada, pois é só imprimir -1. Agora vamos supor que só queremos retirar uma estrada: em uma árvore cuja a soma total é zero, se acharmos uma sub-árvore que tem soma total também igual a zero, podemos destruir a estrada que conecta a árvore principal com a sua sub. De fato, esta observação também se aplica à sub-árvore e às suas sub-árvores, pois a soma total já é 0 - então, se acharmos uma sub com soma 0, o restante só pode ter soma igual a 0. Portanto, percorremos o grafo com uma dfs e vamos salvando qual é a soma dos saldos da sub-árvore do vértice em questão. Quando acharmos uma sub-árvore com soma igual a zero, guardamos o valor da aresta que liga ela com o restante do grafo. Ao final, teremos uma lista de possíveis estradas/arestas que podem ser destruídas. Como queremos exatamente K estradas e com o menor custo possível, temos que ordenar de maneira crescente, ver se existem pelo menos K arestas e somar as K primeiras.

Com isso, obtemos a nossa resposta com uma complexidade de O(N).

Clique aqui para conferir o código.

 

Carros

Comentário por Murilo Maeda

Conhecimento prévio necessário

• Busca Binária

Observação 0

O problema não tem nada a ver com carros.

Observação 1

Mover um doce pode ser interpretado como se estivéssemos o removendo da esteira, já que, se estamos na esteira $E1$, podemos só movê-lo o quanto for necessário para a direita e na esteira $E2$ podemos movê-lo quanto for preciso para a esquerda.

Observação 2

Não faz sentido remover um doce da esteira $E1$ se você não for remover os outros doces mais à esquerda e não faz sentido remover um doce da esteira $E2$ se você não for remover os outros doces mais à direita. Isso porque se, a partir de um certo momento mais nenhum doce for retirado, o tempo até a condição imposta pelo enunciado ser satisfeita depende apenas do doce mais à esquerda da esteira $E1$ e do doce mais à direita da esteira $E2$. Então, as operações gastas movendo doces que estão "no meio" da esteira poderiam ter sido usadas para retirar os doces que definem o tempo até o final, consequentemente reduzindo o tempo total.

Observação 3

A ordem dos doces retirados não afeta o tempo final.

Observação 4

Se a condição ainda não foi satisfeita, não faz sentido não remover um doce, já que mesmo que a condição seja cumprida nos próximos segundo com o movimento das esteiras, remover um docepossui pelo menos a mesma velocidade do movimento das esteiras. Então, podemos considerar que a cada segundo será removido um doce, ou que, o número de doces removidos vai ser igual ao tempo total.

Solução

Com essas observações, podemos estabelecer que os doces retirados da esteira $E1$ formarão um prefixo dos doces iniciais e os doces retirados da esteira $E2$ formarão um sufixo dos doces iniciais. A partir disso, queremos testar as configurações possíveis a fim de achar o tempo final mínimo.

Para fazer isso de forma eficiente, vamos fixar um determinado prefixo de doces retirados da esteira $E1$ e ver até qual sufixo da esteira $E2$ precisamos retirar de modo que a condição do enunciado seja satisfeita. De forma mais específica, queremos, dado um doce na esteira $E1$ na posição $k$, de modo que $k$ seja o doce mais à esquerda dessa esteira (ou ele é inicialmente o mais à esquerda ou os outros foram retirados) queremos saber até qual elemento da esteira $E2$ é preciso remover de modo que $k$ seja maior ou igual do que o elemento mais a direita na esteira $E2$.

Como lidar com as esteiras se movendo

Como é preciso levar em conta o tempo para retirar os doces e como temos a observação 4, vamos fazer isso da seguinte forma: passamos pelos elementos da esteira $E1$ e em cada um deles, vamos considerar que todos os doces antes dele foram retirados e adicionar esse tempo no atual (para simular que a esteira se moveu). Mais especificamente, o que será usado para comparar será $E1[i] + (i - 1)$, já que a esteira se move para a direita e foram usados $i - 1$ segundos para remover os elementos à esquerda de $i$. Como esse doce será o mais à esquerda na esteira $E1$, podemos usar só ele para comparar com os doces da esteira $E2$. Na esteira $E2$ vamos fazer algo semelhante, vamos criar um vetor $ajustado$ que vai manter em cada índice $i$ qual seria a posição do doce inicialmente em $E2[i]$ considerando que todos os doces para sua direita foram removidos. Mais especificamente, $ajustado[i] = E2[i] - (M - i)$, já que a esteira se move para a esquerda e foram gastos $M - i$ segundos removendo os doces para a direita. Perceba que o tempo gasto para retirar os elementos na esteira $E2$ também afeta os elementos da esteira $E1$ e vice-versa. Então, precisamos contabilizar isso na comparação. Basicamente, queremos saber se $E1[i] + (i - 1) + (M - j) \le ajustado[j] - (i - 1)$. Em outras palavras, queremos saber se quando retiramos os doces com índice no intervalo $[1,...i - 1]$ de $E1$ e todos os doces com índice no intervalo $[j + 1,...M]$ de $E2$, o doce mais à esquerda de $E1$ é maior ou igual ao doce mais a direita de $E2$. Se isso for verdade é porque o ciclo acaba e o tempo gasto seria $i - 1 + M - j$.

Então, poderíamos passar por todos os índices $i$ tais que $1 \leq i \leq N$ e para cada um deles passar pelos índices $j$ tais que $1 \leq j\leq M$ ,do maior para o menor e, no primeiro índice $j$ que a condição $E1[i] + (i - 1) + (M - j) \le ajustado[j] - (i - 1)$ for verdadeira, paramos, já que considerando que da esteira $E1$ só tiramos os doces antes de $i$, tirar os elementos depois de $j$ em $E2$ é o mínimo possível para que o ciclo acabe.

O código ficaria assim

Note, no entanto, que o limite do problema é com $N,M \leq 10^{6}$ e nossa solução é $O(N*M)$, então temos que otimizar a complexidade para passar para 100 pontos (ignore o fato de que os casos estão ruins e essa solução passa mesmo sendo quadrática).

Otimização

Perceba que, como o vetor $ajustado$ é crescente e estamos procurando o primeiro valor de modo que $E1[i] + (i - 1) + (M - j) \le ajustado[j] - (i - 1)$, podemos fazer uma busca binária para procurar pelo índice $j$ que satisfaz essa condição. Mas, o problema é que na inequação atual, a parte do vetor $ajustado$ depende do índice $i$ e a parte de $E1$ depende do item $j$, ou seja, não é possível fazer a busca binária, já que um termo depende do outro.

Então, iremos mudar a inequação de modo que o lado do $ajustado$ possa ser independente do índice do atual em $E1$ (para que possa ser pré-computado) e de modo que o lado do $E1$ não dependa do índice $j$ do $ajustado$. Podemos modificar a inequação para ela ficar assim: $E1[i] +2* (i - 1) \le ajustado[j] - (M - j)$ e agora, cada um dos lados é independente. Podemos colocar o $-(M-j)$ dentro da definição de $ajustado[j]$, que agora fica $ajustado[j] = E2[j] - 2*(M-j)$. Agora, podemos pegar o índice do upper_bound de $E1[i] + 2*(i - 1)$ no vetor $ajustado$ e subtrair $1$ desse índice para obter o primeiro índice (do maior para o menor) que satisfaz nossa inequação.

Então, o código fica assim.

 

Palavras

Comentário por Henrique Vianna e Fernando Gonçalves

Conhecimento prévio necessário:

• Segment Tree
• Explorando a STL

Na resolução desse problema, exploraremos as soluções das parciais mais importantes:

Parciais 1 e 2: $1\leq N, Q \leq 10^2$, $K=0$, apenas os números de $1$ a $6$ são usados.

Nessas duas parciais, basta checarmos se a string é substring de $S_6$, de tamanho $63$. Isso é verdade pois não podemos fazer nenhuma alteração nela ($K=0$) e o numero máximo que pode aparecer em nossa string é $6$. Uma maneira simples de fazer isso é gerar $S_6$, adicionar todas suas substrings num map/set e depois apenas verificar se a string atual se encontra nessa estrutura.

Parciais 3, 4, 5 e 6: $1\leq N, Q \leq 10^5$, $K\leq1$, $48MB$ de memória.

Pense em todos os índices em que o $1$ ocorre. Perceba que esses devem estar todos em posições pares, ou todos em posições ímpares (por conta da forma que a string foi construída) . Imagine agora que fixamos a paridade dos elementos $1$, ou seja, escolhemos se eles estarão todos em posições pares ou todos em posições impares.  Ao removermos esses elementos da string, nos deparamos com um problema análogo, em que o $2$ possui propriedades semelhantes ao $1$. A principal observação para esse problema é justamente essa: pensar de forma recursiva.

Para melhor simular essas escolhas, utilizaremos uma árvore binária. A raiz "conterá" nossa string inteira. A aresta para seu filho esquerdo representará a escolha de que o $1$ ocorre nos índices pares, enquanto a aresta para o filho direito fará o mesmo mas considerando que o $1$ ocorre em posições impares. Colocaremos como o peso dessas arestas o numero de alterações na string que tivemos que fazer (elementos em posições pares diferentes de $1$, para o filho esquerdo da raiz, por exemplo). Nos filhos da raiz em si consideraremos as novas strings, com os índices da paridade do elemento $1$ já removidos. Um raciocínio parecido será aplicado aos demais nós. Perceba que o que estamos fazendo é análogo a escolher um resto na divisão por potências de $2$ para cada número. Assim, só precisamos fazer isso para os números menores ou iguais a $21$,  já que $2^{20}\gt N$ (não podemos ter dois números maiores ou iguais a $21$ numa mesma sequência).

Tendo essa árvore, nosso problema pode ser reduzido a achar o caminho de menor custo da raiz a uma das folhas da árvore, para depois compararmos esse valor com o de $K$. Para tanto, podemos manter para cada nó o minimo custo para, a partir dele, chegar a alguma folha (de forma similar ao que fazemos numa segment tree de minimo). Não precisamos, de fato, guardar as strings em cada nó. Além disso, perceba que num update teremos de atualizar apenas um caminho da raiz a uma folha, já que o índice em questão estará sempre contido em exatamente um dos dois filhos. Assim, é fácil fazermos updates em $\mathcal{O}(logN)$.

Veja o código abaixo:

Parciais 7: $1\leq N, Q \leq 10^6$, $K\leq5$, $6MB$ de memória.

Para resolver a ultima parcial desse problema, precisamos otimizar a memória que estamos utilizando. Ainda não utilizamos o fato de que o valor de $K$ é pequeno. Exploraremos esse fato para reduzirmos nosso uso de memória. Perceba que, na maioria dos casos, não precisamos de fato criar os dois filhos para cada nó, já que frequentemente o custo já seria maior do que o de $K$. Manteremos dinamicamente uma quantidade reduzida de nós, apagando els quando possível e mantendo apenas os que são realmente necessários no momento. Perceba que isso significa que teremos de reconstruir a nossa árvore depois de certos updates, fato que deve ser considerado na implementação dessa solução (veja o willbuid, no código abaixo).

Há vários casos e detalhes que devem ser tratados durante a implementação. Veja o código abaixo caso precise de ajuda: