Solução Informática - Nível Intermediário - Semana 35

Solução escrita por Arthur Lobo

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops

Considerando que $i \le j$ só existem 2 formatos diferentes que satisfazem a condição de ser interessante, vamos pensar em como contar cada uma delas:

$A_i = i, A_j = j$

Vamos chamar $i$ de legal se $A_i = i$. Qualquer par $i,j$ em que $i< j$ e ambos $i$ e $j$ são legais é um par interessante, pois o fato de $A_i = i$ torna $i$ meio "independente" de $j$.

Seja $Q$ a quantidade de índices legais. A quantidade de pares nesse formato vai ser $Q*(Q-1)/2$, porque podemos escolher quaisquer $i,j$ entre os que tal que $i < j$, e $i$ e $j$ são legais.

$A_i = j, A_j = i$

Para cada $i$, existe no máximo um $j$ que satisfaz essa condição. Então podemos fazer um for com $i$ indo de $1$ até $N$ checando 2 coisas: se $A_i > i$ e $A_{A_i} = i$ (ou seja, se $A_j = i$). Se ambas forem verdadeiras, aumentamos a resposta em 1, pois encontramos um par válido.

A primeira parte é $O(N)$ e a segunda também, então no final o a complexidade fica $O(N)$.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.