Campeonato de Robótica

Solução escrita por Malu Azevedo

O problema nos pede para determinar se é possível transformar a sequência inicial $A$ na sequência alvo $B$ realizando trocas entre elementos cuja distância na linha seja exatamente $d$.

Ideia Central

Como a operação permitida troca apenas elementos que estão a uma distância exata $d$, percebemos que podemos trocar elementos cujos índices deixam o mesmo resto quando divididos por $d$. Isso significa que o array é dividido em $d$ grupos independentes, conhecidos como as classes de resto módulo $d$. Dentro de cada um desses grupos, os elementos podem ser reordenados livremente de qualquer maneira. Portanto, para que a transformação seja viável, cada grupo de elementos com o mesmo resto módulo $d$ na sequência $A$ deve conter exatamente os mesmos valores que o grupo correspondente na sequência $B$.

Abordagem Completa

Lemos os valores de $N$ e $d$, seguidos pelas sequências $A$ e $B$. Para verificar a condição, criamos estruturas para armazenar os elementos de cada resto módulo $d$. Para cada índice de 0 a N-1, pegamos o elemento de $A$ e o de $B$, e os agrupamos pelo seu resto correspondente módulo $d$. Em seguida, ordenamos os elementos de cada grupo tanto para $A$ quanto para $B$. Se todos os grupos forem idênticos nas duas sequências, significa que conseguimos organizar as caixas e imprimimos ‘S’, caso contrário, imprimimos ‘N’. A complexidade da solução é $O(N \log N)$

Clique aqui para ver o código completo.