Seletiva IOI 2018 – Dia 4
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
Jogo
Solução escrita por Rafael Nascimento
Conhecimento prévio necessário:
Nesse problema, nós podemos desenhar um segmento de reta entre dois pontos quaisquer, e a pontuação consiste na soma de todos os pontos que interceptam com o segmento de reta.
Para resolver este problema, usaremos uma propriedade geométrica:
Digamos que tenhamos uma linha e escolhemos dois pontos quaisquer contidos nelas. Podemos afirmar que o ângulo alfa (como pode ser visto na imagem acima) sempre será o mesmo independentemente de quais pontos contidos na linha sejam escolhidos. Essa propriedade gera uma forma fácil de saber se o ponto está contido na linha.
Dessa forma, imagine que nós temos o seguinte algoritmo:
- Nós escolhemos com força bruta o primeiro ponto (ponto A) a pendurar a corda.
- Nós escolhemos com força bruta o segundo ponto (ponto B) a pendurar o final da corda.
- Nós iteramos por todos os pontos (ponto i) e checamos se o ponto está contido na corda, ou seja, comparamos os alfas.
Dessa forma, nós temos um algoritmo $$O(N^3)$$ que é capaz de resolver a segunda parcial, obtendo 25 pontos.
Agora nós temos que otimizar esse algoritmo de força bruta para ser capaz de computar a resposta em aproximadamente $$O(N^2)$$.
Primeiro, vamos sortar os pontos pela coordenada $$x$$. Assim, afirmarei que o ponto A é o mais a esquerda, e o ponto B o mais a direita (considerando a coordenada $$x$$).
A ideia é que nós não precisamos iterar por todos os pontos no #3, porque nós já iteramos todos os pontos contidos no segmento entre A e B enquanto executávamos a etapa #2. Isso é verdade porque todos os pontos que estão no segmento de reta entre A e B possuem sua coordenada $$x$$ entre a coordenada $$A_x$$ e a coordenada $$B_x$$, e já que estamos iterando em ordem (nós sortamos as coordenadas), nós iteramos todos os pontos entre $$A_x$$ e $$B_x$$.
Dessa forma, quando iteramos os pontos pela etapa #2, podemos salvar os ângulos dos pontos anteriores em uma estrutura como map ou unordered_map. Assim, ao invés de consultar todos os pontos na etapa #3, podemos simplesmente checar o map, consultando a soma dos pontos que possuem aquele ângulo.
O código abaixo possui complexidade $$O(N^2\cdot log)$$, já que foi utilizado map. No código, foi armazenado o ângulo através de duas informações: O quadrante (considerando o ponto A como o centro $$<0,0>$$ do quadrante) e o seno.
Clique aqui para conferir o código
Chuva
Comentário por Fernando Gonçalves
Conhecimento prévio necessário:
Nesse problema, queremos saber em quantos coletores de água um retângulo de chuva chega, sendo que a aǵua sempre vai para uma casa adjacente que tem altura menor ou igual a sua atual.
A principal observação desse problema é que devemos encarar ele ao contrário do que ele é apresentado: ao invés de calcular para cada retângulo quantos coletores ele afeta, devemos calcular para cada coletor de quais retângulos ele recebe água.
Para tanto, devemos calcular para cada coletor quais posições levariam água a ele. Podemos fazer isso por meio de uma dfs ou uma bfs, que começa na posição do coletor e passa pela matriz, caminhando somente para posições que tenham altura maior ou igual a sua. Também marcamos todas as casas pelas quais passamos, desta forma as casas que chegam no coletor estarão marcadas com $$1$$, enquanto aquelas que não chegam estarão marcadas com $$0$$.
Agora, só precisamos checar, para cada retângulo, se a sua água chega no coletor, ou seja, se dentro dele existe alguma casa marcada com $$1$$. Podemos fazer isso rapidamente usando somas de prefixo 2D, pois haverá alguma casa marcada com $$1$$ dentro do retângulo se, e somente se, a soma da marcação das casas for maior que $$0$$.
Em suma, nosso algoritmo fará o seguinte:
- Para cada coletor, uma busca no grafo que marca aqueles em que o coletor chega;
- Tendo marcado as casas, pré-calcular as somas de prefixo 2D da matriz de marcação;
- Passar por cada retângulo checando se ele chega no coletor;
- Por fim, imprimir a resposta.
As complexidades serão:
- $$O(K*N*M)$$ para as buscas
- $$O(K*N*M)$$ para o pré-calculo das somas de prefixo 2D
- $$O(K*Q)$$ para checar os retângulos
- $$O(K*(N*M + Q))$$ no total
Obs: o tempo limite desse problema está bem apertado, podem ser necessárias otimizações de constante ou de cache. Em caso de dúvida, cheque o código.
Clique aqui para conferir o código
Danone
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
A ideia inicial do problema vai ser pensar na soma no formato de prefix sum, sendo $$pf_i = v_1+v_2+…+v_i$$. Se sabemos que a soma de $$l$$ até $$r$$ é $$x$$, então $$pf_r – pf_{l-1} = x \Rightarrow pf_r = pf_{l-1}+x$$. Isso quer dizer que sabemos qual diferença entre os valores de $$pf_r$$ e $$pf_{l-1}$$. Conseguir responder uma query de um $$l$$ até um $$r$$ significa saber a diferença entre os valores de $$pf_r$$ e $$pf_{l-1}$$.
Agora vamos ver o que podemos fazer quando temos várias informações de soma:
- $$A_{l1+1}+… +A_{r1}= x1 \Rightarrow pf_{r1} = pf_{l1} + x1$$
- $$A_{r1+1}+… +A_{r2}= x2 \Rightarrow pf_{r2} = pf_{r1} + x2$$
- $$A_{l2+1}+… +A_{r1}= x3 \Rightarrow pf_{r1} = pf_{l2} + x3$$
Antes de proseguir, pense em todos os intervalos que conseguimos saber a soma.
Resposta: conseguimos saber a soma de todos os intervalos em que o início é um dos $$l1+1,l2+1,r1+1,r2+1$$, o final é um dos $$l1,l2,r1,r2$$ e o início é menor que o final, ou seja, $$(l1+1,l2),(l2+1,r1),(r1+1,r2)…$$.
O motivo disso é que conseguimos saber o valores de $$pf_{l2},pf_{r1},pf_{r2}$$ em função de $$pf_{l1}$$:
- $$pf_{r1} = pf_{l1} + x1$$
- $$pf_{r2} = pf_{l1} + x1 + x2$$
- $$pf_{l2} = pf_{l1} + x1 – x3$$
Portanto, se queremos saber, por exemplo, a soma de $$l2+1$$ até $$r2$$, basta fazer $$pf_{r2}-pf_{l2}$$ $$= pf_{l1} + x1 + x2 – (pf_{l1} + x1 – x3) =$$ $$x2+x3$$.
A ideia vai ser manter vários valores de $$pf$$ em relação à um outro $$pf$$. Vamos manter dois vetores:
- $$rel_i=$$ Em relação à qual índice você está mantendo $$pf_i$$. Inicialmente, $$rel_i = i$$.
- $$val_i=$$ Qual a diferença entre $$pf_i$$ e $$pf_{rel_{i}}$$. Ou seja, $$pf_i = pf_{rel_{i}} + val_i$$. Incialmente $$val_i = 0$$.
Subtask 1 ($$ N,Q \leq 5000$$)
Primeiro, vamos pensar em como lidar com uma Query perguntando a soma de $$l$$ até $$r$$. Se $$rel_r \nq rel_{l-1}$$, então é impossível saber a resposta. Caso contrário, a resposta é $$val_r-val_{l-1}$$, pois $$pf_{rel_r}$$ desaparece na subtração.
Agora basta lidar com um update falando que a soma de $$l$$ até $$r$$ é $$x$$. Se $$rel_r = rel_{l-1}$$, então já sabemos essa informação e podemos ignora-la. Caso contrário, temos que juntar as “componentes” de $$r$$ e $$l-1$$. Para isso, vamos fazer todo mundo que tem $$rel_i = rel_{r}$$ ter $$rel_i = rel_{l-1}$$, mas para isso temos que mudar o valor de $$val_i$$:
- $$pf_r = pf_{rel_r} + val_r$$
- $$pf_{l-1} = pf_{rel_{l-1}} + val_{l-1}$$
- $$pf_r = pf_{l-1} + x \Rightarrow pf_{rel_r} + val_r = pf_{rel_{l-1}} + val_{l-1}+x\Rightarrow pf_{rel_r} = pf_{rel_{l-1}} + val_{l-1} – val_r + x$$
Para todo $$i$$ com $$rel_i = rel_r$$, temos $$pf_i = pf_{rel_r} + val_i \Rightarrow pf_i = pf_{rel_{l-1}} + val_{l-1} – val_r + val_i+x$$, portanto, se quisermos mudar $$rel_i$$ para ser $$rel_{l-1}$$, então precisamos mudar $$val_i$$ para $$val_{l-1} – val_r + val_i+x$$.
Conseguimos dar um merge nas duas componentes dessa maneira. Perceba que é possível visualizar o problema como um grafo em que ligamos uma aresta entre $$l-1$$ e $$r$$ se sabemos a soma entre eles 2 através de um update e as componentes desse grafo são os pares que sabemos a soma.
Esse código fica $$O(1)$$ para responder a query e $$O(N)$$ no pior dos casos para lidar com um update, portanto fica $$O(N*Q)$$.
Subtask 2 ($$ N,Q \leq 2*10^6$$)
Precisamos diminuir a complexidade do update, para isso basta usar um small-to-large na hora do merge das componentes. Se a quantidade de $$i$$ com $$rel_i = rel_{l-1}$$ for menor que a quantidade com $$rel_i = rel_{r}$$, então fazemos os $$i$$ t.q. $$rel_i = rel_{l-1}$$ virarem $$rel_{r}$$. Senão, fazemos o contrário.
Com isso, o update fica, no total, $$O(N*logN)$$ e código inteiro fica $$O(NlogN + Q)$$.
Clique aqui para conferir o código