Soluções da Qualificação das ONI'2020
Problema A - Corridas de Berlindes
Tipo de problema: Ciclos e contagens
Autor do problema: Pedro Paredes (CMU)
Dificuldade do problema: Fácil
Parte I
Dados os $N$ berlindes, dados por um par de agilidade e velocidade $ (A_i, V_i) $, determinar quantos berlindes diferentes há.
Restrições
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ $N$ ≤ $10^5$ | Número de berlindes |
0 ≤ $A_i$, $V_i$ ≤ 10 | Agilidade e velocidade |
Solução
Há várias formas de resolver este problema eficientemente, mas vamos ver a mais simples. É sempre muito importante verificar as restrições do problema. Neste problema sabemos que os valores de $A_i$ e $V_i$ são no máximo 10 e no mínimo 0, por isso há no máximo 121 (11 vezes 11) berlindes diferentes. São eles o (0, 0), o (0, 1), o (0, 2), ...
Isto significa que podemos manter uma array bidimensional onde
marcamos que berlindes existem. Vamos chamar a array de
berlindes
e será uma array de 11 por 11, ou seja, int
berlindes[11][11]
. A entrada $i, j$ desta array, isto é, o valor
de berlindes[i][j]
, representa se há um berlinde de agilidade igual
a $i$ e velocidade igual a $j$. Para preenchermos esta array basta
iterarmos por cada berlinde e marcar a posição correspondente, isto é,
para o $i$-ésimo berlinde marcamos berlindes[A[i]][V[i]]
.
Finalmente, basta contabilizarmos o número total de berlindes que marcámos, o que podemos fazer iterando por todos os valores de $i$ e $j$ entre 0 e 11 (ou seja, todos os valores de agilidade e velocidade possíveis).
Esta solução pode ser implementada através do seguinte pedaço de código:
Vamos agora fazer a análise da complexidade temporal deste algoritmo. Se ainda não leste o conjunto de artigos de iniciação às ONI é muito importante que o faças. Entre outros temas mais introdutórios e avançados abordamos como analisar um programa de modo a conseguir estimar quantos pontos terá. Vamos fazer essa análise a seguir para o código acima a seguir.
Artigo: Guia de iniciação às ONI
No 4o artigo deste guia abordamos o tema de análise de complexidade.
Precisamos de dois ciclos: um que percorre todos os berlindes e um que percorre todos os tipos de berlindes possíveis. Em notação Big-O, a complexidade desta solução é traduzida por $O(N + B)$, onde $B$ representa o número de tipos de berlindes diferentes (ou seja 121). Isto é suficiente para resolver ambas as subtarefas da primeira parte e obtém assim os 50 pontos desta parte.
Parte II
Dados os $N$ berlindes, dados por um par de agilidade e velocidade $(A_i, V_i)$, determinar quantas vitórias terá o berlinde vencedor de um torneiro.
Restrições
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ $N$ ≤ $10^5$ | Número de berlindes |
0 ≤ $A_i$, $V_i$ ≤ 10 | Agilidade e velocidade |
Solução
A que berlindes ganha o $i$-ésimo berlinde numa corrida? Ora, aos berlindes do tipo $(a, v)$ onde $a < A_i$ e $v < V_i$. Dado isto vamos fazer-nos a seguinte pergunta: como é que podemos obter o número de berlindes que perdem corridas contra o $i$-ésimo berlinde de forma eficiente?
A estratégia vai ser a mesma que na Parte I, nomeadamente, vamos
contar quantos berlindes há de cada tipo. Fazemos isto mantendo a
mesma array berlindes
que guarda a contagem de berlindes de cada
tipo. Agora que temos esta array, se quisermos responder à pergunta
anterior só temos de somar os valores de berlindes[a][v]
para todos
os valores de a
e v
tais que $a < A_i$ e $v < V_i$, o que
podemos fazer com dois ciclos. Basta fazermos isto para cada berlinde
e manter o máximo número de vitórias que encontrámos.
Esta solução pode ser implementada através do seguinte pedaço de código:
Nesta solução temos um ciclo que para cada berlinde itera por todos os tipos de berlindes diferentes, por isso a complexidade final é de $O(NB)$, onde, novamente, $B$ representa o número de tipos de berlindes diferentes. Isto é suficiente para resolver ambas as subtarefas da primeira parte e obtém assim os 50 pontos desta parte.
Extra *
Há várias soluções alternativas e mais eficientes para ambas as partes. Listamos aqui as suas complexidades e algumas dicas de como as obter como exercício:
- Na Parte II, podemos obter um algoritmo cuja complexidade é $O(N + B)$ se précalcularmos algumas coisas. Consegues ver como?
- Vamos supor que os valores de agilidade e velocidade, em vez de serem no máximo 10, eram no máximo $10^5$. Neste caso as nossas soluções anteriores são pouco eficientes. Mas podemos obter uma solução $O(N \log N)$ que resolveria este caso, usando ideias de ordenação e pesquisa binária. Consegues pensar como fazê-lo?