Solução Informática - Nível Avançado - Semana 40

Solução escrita por Fernando Gonçalves

Conhecimento prévio:

• Árvores

Podemos logo no começo fazer duas operações de tipo 1: "$+$  $n$  " e "$+$  $(n+1)$ " .

A primeira operação criará as arestas de $1$ para $n-1$, de 2 para $n-2$, e por aí vai

A segunda criará as arestas de $1$ para $n$, de $2$ para $n-1$, e por aí vai.

Portanto, acabaremos criando um grafo especial: uma linha. Nesse grafo, temos os vértices $n$ e  $\lceil \frac{n}{2} \rceil$ como bordas e todas os demais vétices estão no meio desses dois.

Note que, se fixarmos uma das bordas para ser $n$, conseguimos descobrir quais são todos os outros vértices apenas pelas suas distâncias até essa borda. Por exemplo, para n = 5, sabemos que o vértice $1$ sempre está a $1$ de distância do $n$, o $4$ está a $2$ de distância, etc.

Desta forma, ao acharmos as duas bordas do grafo, podemos gerar as duas permutações possíveis, uma das quais estará correta, cada uma ao fixar uma das bordas como $n$.

Entretanto, ainda resta o problema de achar as bordas do grafo. Afinal, elas podem corresponder a qualquer índice na permutação.

Para achá-las, podemos pegar um indíce na permutação qualquer e, por meio de operações tipo 2, testar todas as distâncias para ele (excluindo ele mesmo, que já sabemos que é zero). A maior dessas distâncias será aquela do indíce de uma das bordas.

Agora que temos uma das bordas, calculamos, pelas operações tipo 2, a distância de todos os índices (novamente, excluindo o da própria borda) para ela e usamos esses valores para conseguir a permutação, considerando que essa borda é $n$.

Por fim, usamos as distâncias para a borda que já calculamos para achar a outra borda, que será a mais distante. Note que, como o grafo é uma linha, as distâncias $d'_i$ de cada índice $i$ para essa nova borda serão $d'_i = n-1 - d_i$, sendo $d_i$ a distância de cada indíce $i$ para a borda antiga. Portanto, podemos calcular, pelo mesmo procedimento da borda antiga, uma permutação que fixa a nova borda como $n$, sem precisar de operações a mais.

Em suma, o algoritmo terá os seguintes passos:

1. Faremos duas operações de tipo 1: "$+$  $n$" e "$+$  $(n+1)$";
2. Pegaremos um indíce da permutação arbitrário (por praticidade, $1$) e calcularemos a distância de todos os índices para esse. Utilizando $n-1$ operações;
3. A maior das distâncias será aquela relativa a uma das bordas;
4. Calcularemos as distâncias em relação a esta borda que acabamos de achar, usando mais $n-1$ operações;
5. Com essas distâncias para a borda, conseguimos achar uma das permutações possíveis;
6. Achamos a outra borda, que é aquela que tem maior distância para a borda original.
7. Achamos a distância de todos os indíces para a nova borda, que será $d'_i = n-1$ - $d_i$. Esse passo não usará nenhuma operação.
8. Usamos essas distância em relação à nova borda para calcular uma segunda permutação, que fixa essa nova borda como $n$.
9. Usando $2 + (n-1) + (n-1) = 2n$ passos, conseguimos achar duas permutações, uma das quais certamente está correta.

 

Cheque o código abaixo em caso de dúvida: