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.

Posições nas quais o 1° coletor (amarelo) e o 2° coletor (azul) chegam no primeiro exemplo

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.

Posições em que chegam os 1°, 2° e 3° coletores, respectivamente, no segundo exemplo

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.