Comentário NOIC OBI 2016 - Fase 2 - Programação Nível 1

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível 1 da OBI 2016, clique aqui.

Este comentário utiliza os objetos cin  e cout como métodos de entrada e saída. Eles estão na biblioteca iostream, do C++, e são de muito fácil uso.

Para ler uma variável qualquer a, basta a linha de código: cin >> a;

Para ler uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cin >> a >> b >> c >> ...;

Para imprimir uma variável qualquer a, basta a linha de código: cout << a;

Para imprimir uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cout << a << b << c << ...;

Medalhas

Conhecimento prévio necessário:

1. Entrada e Saída (Aula 1)
2. Estruturas condicionais (Aula 2)

Devemos imprimir o número do atleta que terminou a prova em cada lugar. Para tal, em cada posição, basta checarmos o tempo de cada atleta e verificar se ele é quem estamos procurando. No início, vamos ler os valores da entrada e guardar nos inteiros t1, t2 e t3. Eles representarão o tempo de cada atleta, respectivamente.

Vamos checar se o primeiro atleta foi o que terminou em primeiro lugar: basta checar se o seu tempo é menor que  dos outros dois (if(t1<t2 and t1<t3)). Não precisamos nos preocupar com igualdades pois o enunciado nos diz que os tempos são, necessariamente, diferentes. Caso o primeiro atleta seja de fato o primeiro colocado, imprimimos seu número (cout << "1\n";), e repetimos essa checagem com cada atleta.

Agora, basta repetirmos o mesmo processo para descobrirmos quem são o segundo e o terceiro lugar, mudando, logicamente, apenas a condição. O segundo lugar, por exemplo não tem o tempo menor que o dos outros dois, mas está entre os dois colocados, ou seja, se t1 é o segundo colocado, então ou t2>t1>t3 ou t3>t1>t2 (if((t2>t1 and t1>t3) or (t3>t1 and t1>t2))). Por fim, o último colocado deve ter um tempo maior que os outros dois.

Para cada posição, quando descobrimos qual atleta a ocupa, basta imprimirmos o número dele. Segue o código para melhor entendimento:

Caverna de Ordinskaya

Conhecimento prévio necessário

1. Estruturas condicionais (Aula 2)

A solução deste problema segue a ideia geral de um algoritmo guloso: basta sempre tentar construir a fita com o menor número e, caso ele seja menor que a medição anterior, uso a maior, pois só há duas possíveis em cada posição. Caso a maior também seja menor que a anterior, é impossível.

De maneira mais formal, seja $a_i$ o i-ésimo número da entrada e suponha que já sabemos que o valor da medição anterior ($i-1$) é $s_{i-1}$. Seja $x_i$ o menor entre $a_i$ e $M-a_i$ (o menor valor possível), e $y_i$ o maior entre $a_i$ e $M-a_i$ (o maior valor possível). Em outras palavras,  $x_i=max(a_i,M-a_i)$ e $y_i=min(a_i,M-a_i)$. Se $y \geq s_{i-1}$, devemos utilizá-lo, ou seja determinar que $s_i=y_i$, pois é o melhor que podemos fazer para minimizar o comprimento da corda. Se isto não for possível, então só nos resta utilizar o valor de $x_i$ ($s_i=x_i$). Note que, se $x_i<s_{i-1}$, então é impossível atribuir algum valor a $s_i$, pois $s_{i-1}$ foi construído de modo a ter o menor valor possível.

Assim, basta guardarmos a variável resp e a variável ant. No começo, resp=ant=$0$. Depois, usamos um for para percorrermos todas as medições. Em cada iteração i, ant será o valor de $s_{i-1}$, e resp  o atual comprimento da corda. Se for possível atribuir algum valor a $s_i$, somamos seu tamanho a resp. Caso contrário, resp=$-1$ e paro o loop. Não podemos esquecer de atualizar o valor de ant para $s_i$, para a próxima iteração do loop.

Por fim, basta imprimir o valor salvo em resp. Note que ant começa $0$ para que seja sempre possível usar o menor valor na primeira medição. Como a soma total pode ser, num limite bem rude, $N \times M = 5 \times 10^9$, usaremos long long. Segue o código para melhor entendimento:

Arco e Flecha

Conhecimento prévio necessário

1. Número de inversões no vetor (Aula 5)

Seja $d_i$ a distância ao quadrado da flecha $i$ até o centro. Note que se $d_i > d_j$, então a flecha $i$ está mais distante do centro do alvo que a flecha $j$. Usaremos os quadrados das distâncias para não termos que trabalhar com double, o que poderia acarretar em perda de precisão. Seja $S={d_i, 1 \leq i \leq N}$, ou seja, $S$ é a sequência formada pelas $N$ distâncias.

Observe agora o tiro $i$. Olhando para todos os tiros $j$ anteriores a ele ($j<i$), todos os que tiverem distância menor que ele do centro constituem uma penalidade (se $d_j \leq d_i$, há uma penalidade), ou seja, os tiros que não irão acrescentar penalidades são todos aqueles anteriores a $j$ que são mais distantes do centro que ele ($d_j>d_i$). Deste modo, cada tiro anterior a $i$ que não resultará em uma penalidade no tiro $i$ são aqueles cujo par $(j,i)$ é uma inversão na sequência $S$ ($j<i, d_j>d_i$).

Assim, qualquer par de tiros $i,j$, com $i<j$ será uma penalidade no momento em que o tiro $j$ for dado, a não ser que este par seja uma inversão na sequência. O número total de pares $(i,j), i \neq j$ é $\binom{N}{2}= \frac{N \times (N-1)}{2}$, do qual seja $I$ o número total de inversões em $S$. A penalidade total será exatamente $\binom{N}{2} - I$.

Para resolvermos o problema, basta usarmos um vetor v para representarmos a sequência $S$. Lembre-se que o quadrado da distância de um ponto à origem do plano é, simplesmente, a soma dos quadrados de suas coordenadas. Ou seja, se as coordenadas do ponto $i$ são $X_i$ e $Y_i$, então v[i] = $d_i$ = $X_i^2+Y_i^2$. Como as coordenadas têm módulo que pode ir até $10^6$, usaremos long long para guardarmos os valores do vetor v.

Por fim, basta calcularmos o número de inversões em v, de maneira exatamente igual ao que foi feito no fim da aula de ordenação, e imprimirmos a resposta. Segue o código para melhor entendimento:

Caminhos do reino

Conhecimento prévio necessário

1. Vetores (Aula 3)
2. Grafos (Aula 8)

Este problema envolve uma implementação minuciosa, dividida em várias etapas. Seja $d(v,u)$ o tamanho do caminho que sai de $v$ e chega em $u$, se existir. Para cada vértice $v$ do grafo, devemos calcular os valores de $pos_v$ e $h_v$. Seja $c_v$ a cidade do ciclo interno tal que $d(v,c_v)$ é mínimo. Se $v$ está no ciclo, $c_v=v$. Defina $h_v$ como $d(v,c_v)$.

O ciclo tem um pai, que é um vértice $u$ qualquer pertencente ao ciclo. Se $k$ é um vértice qualquer do ciclo, defina $pos_k$ como $d(u,k)$. Note que $pos_u=0$. Agora, para qualquer vértice $v$, defina $pos_v=pos_{c_v}$.

Agora que já definimos esses valores, calcular o menor tempo de encontro entre duas pessoas nos vértices $v$ e $u$ do grafo é bem simples. Se ambos os vértices estiverem no mesmo caminho periférico, ou seja, $c_v=c_u$, a distância entre eles é $\mid h_v-h_u \mid$, pois basta que a pessoa na cidade de maior "profundidade" caminhe até chegar na cidade mais próxima do ciclo.

Entretanto, se os vértices estiverem em caminhos periféricos diferentes, a conta é ligeiramente mais complicada. Primeiramente, note que os dois vão, necessariamente, se encontrar em algum vértice do ciclo. Quando um dos dois chega no ciclo, não vale a pena que os dois se movam nele, pois qualquer movimento de um distancia-se do outro, visto que só podem andar em uma direção, logo um dos dois, digamos $v$, não se movimentará no ciclo e o ideal será que se encontrem no vértice $c_v$.

De maneira mais formal, suponha que o vértice ideal de encontro é $k$ diferente de $c_v$ e $c_u$. Sem perda de generalidade, digamos que $d(c_v,k)<d(c_u,k)$. Neste caso, como o ciclo só tem um sentido, o caminho do $c_u$ a $k$ necessariamente passa pelo vértice $c_v$, sendo melhor que ambos se encontrassem, portanto, em $c_v$.

Sabendo agora que o ponto de encontro será $c_v$ ou $c_u$, basta calcularmos qual dos pontos de encontro é a resposta. Seja $d_v$ o tempo em que as pessoas no vértice $v$ e $u$ se encontram em $c_v$. Note que $d_v=max(d(v,c_v),d(u,c_v))$, pois veremos quanto tempo cada um demora para chegar em $c_v$ e a resposta será o maior deles (o que chega mais rápido espera o outro). Sabemos que $d(v,c_v)=h_v$, restando-nos calcular o valor de $d(u,c_v)$. Para chegar de $u$ a $c_v$, primeiro temos que chegar ao ciclo, ou seja chegar em $c_u$, e sabemos que $d(u,c_u)=h_u$. Feito isso, basta calcularmos o valor de $d(c_u,c_v)$, pois sabemos que $d(u,c_v)=d(u,c_u)+d(c_u,c_v)$. Se $pos_{c_v}>pos_{c_u}$, então $d(c_u,c_v)=pos_{c_v}-pos_{c_u}$. No entanto, se $pos_{c_v}<pos_{c_u}$, $d(c_u,c_v)=(pos_{c_v}-pos_{c_u}) \mod m$, onde $m$ é o tamanho do ciclo interno. De qualquer modo, $d(c_u,c_v)=(pos_{c_v}-pos_{c_u}) \mod m$. Assim,$d_v=max(h_v,h_u+((pos_{c_v}-pos_{c_u}) \mod m)$. De maneira análoga, $d_u=max(h_u,h_v+((pos_{c_u}-pos_{c_v}) \mod m)$.

Deste modo, o menor tempo para que pessoas nos vértices $u$ e $v$ se encontrem é $min(d_v,d_u)$. Note que parto do princípio de que $a \mod b$ sempre é positivo, ou seja, se $a>0$, $-a \mod b = b-a$. Agora, basta implementarmos um código que calcule os valores de $h_v$ e $pos_v$ para todo vértice $v$ do grafo.

Primeiramente, vamos identificar todos os vértices que estão no ciclo e guardá-los no vector cycle. Para isso, vamos salvar as arestas em dois grafos: um original, em que son[v] guarda o destino da aresta que sai de v, e um grafo inverso, em que o  vector invers[v] guarda todos os vértices cujas arestas chegam em v.

Agora, para encontrar um cara no ciclo, basta percorrer todos os vértices, procurando por um com grau de entrada maior que $1$, ou seja invers[v].size()>1. Quando o encontramos, basta seguirmos o caminho que começa nele no grafo normal, adicionando todos os vértices que passaremos ao ciclo, até que voltemos a v, e então paramos.

Agora, para cada vértice do ciclo, vamos chamar uma DFS no grafo inverso, que irá calcular os valores de h[v] e pos[v] para todos os vértices do grafo. Para o vértice v no ciclo, h[v] já começa $0$ e pos[v] será sua posição em cycle.

Agora, suponha que chamamos a DFS para um vértice v qualquer. Para cada vizinho seu u, se ele não estiver no ciclo, o valor de pos[u] será o mesmo de pos[v], pois eles chegam ao mesmo vértice do ciclo, e como o caminho de u a esse vértice consiste em ir de u até v e então ao vértice, temos que h[u]=h[v]+1. Agora que já calculamos esses valores para u, podemos chamar dfs(u).

Depois de chamada a DFS para todos os vértices do ciclo, já teremos os valores de h e pos para qualquer vertice do grafo, logo, basta ler cada uma das perguntas e respondê-las com as fórmulas calculadas anteriormente. Segue o código para melhor entendimento: