Simulado - Segunda Fase OBI 2021 - Comentário P1

Comentário por Lúcio Figueiredo, Luca Dantas e Anita Almeida

Para conferir a prova na íntegra, clique aqui.

Binário

Conhecimento Prévio Necessário:

• Estrutura de Dados Set

Para resolver este problema, vamos utilizar a seguinte observação:

Observação: Em um vetor binário $V$, defina $ultimo_0$ como maior índice $i$ tal que $V[i] = 0$; de forma similar, defina $primeiro_1$ como o menor índice $i$ tal que $V[i] = 1$. O vetor $V$ será um vetor ordenado crescentemente se e somente se $ultimo_0 < primeiro_1$.

Para resolvermos o problema, precisamos de uma estrutura de dados que consiga armazenar dinamicamente (ou seja, com operações de update) os índices $ultimo_0$ e $primeiro_1$. Uma estrutura que satisfaz esta condição é o Set; podemos utilizar dois sets, $set[0]$ e $set[1]$, que guardam todos os índices do vetor que contém $0$ e $1$, respectivamente. Assim, é facil manter os dois sets após uma operação de update: se o índice $i$ teve seu valor modificado, basta remover $i$ de $set[V[i]]$ e inserir $i$ no outro set. Para responder se o vetor está ou não ordenado, utilizaremos a observação acima, conferindo se o maior elemento de $set[0]$ (ou seja, $ultimo_0$) é ou não menor que o menor elemento de $set[1]$ (ou seja, $ultimo_1$).

Como utilizamos um set em cada operação de update, a complexidade final da solução é $O(N + M \cdot \log_{} N)$. Segue o código, com comentários, para melhor compreensão do problema:

Eleições da Nlogônia

Conhecimento Prévio Necessário:

• Estruturas Condicionais

Para esse problema temos 4 casos para analisar: ou algum dos 3 candidatos ganham a eleição (caso tenha mais que 50% dos votos, que numericamente representa 500 votos), ou nenhum candidato alcançou mais que 500 votos e isso significa que a eleição irá para o segundo turno. Para sabermos qual a opção correta basta utilizarmos as estruturas condicionais $If/Else$ considerando todos os casos. Segue o código para melhor compreensão:

Operações

Conhecimento Prévio Necessário:

• Vetores

Inicialmente, observe que se fizermos uma operação que remove alguns números de valor $v$, não é ótimo realizar outra operação que remove números de mesmo valor, já que estes poderiam ser incuídos na primeira operação. Logo, em uma solução ótima, cada operação realizada remove números com valores distintos entre si. Portanto, podemos concluir que a resposta para o problema é a quantidade de valores distintos presentes no vetor.

Para calcularmos quantos valores distintos existem no vetor, podemos utilizar um vetor de booleanos $mark[]$, tal que $mark[i] = 1$ se o valor $i$ está presente no vetor, e $mark[i] = 0$ caso contrário. Este vetor pode ser calculado assim que os números são dados na entrada. Assim, a resposta final para o problema é igual à quantidade de índices de $mark[]$ que são iguais a $1$. Como o vetor $mark[]$ tem tamanho igual ao maior elemento da entrada, a complexidade final da solução é $O(N + M)$, onde $M$ é o valor do maior elemento presente no vetor.

Nota: Uma outra forma de encontrar a quantidade de números distintos no vetor utiliza a estrutura de dados Set. Nesta solução, basta inserir os valores da entrada em um set e, em seguida, imprimir como resposta o tamanho do set. A complexidade desta solução é $O(N \cdot \log_{} N)$, e é uma solução particularmente boa caso os números da entrada possam ser muito grandes.

Segue o código, com comentários, para melhor compreensão do problema: