Placar do Jogo
Solução escrita por Julia Tiosso
Conhecimentos necessários:
Nesse problema, são dadas duas listas com os momentos em que Paulo e Camila marcaram gol ao longo de um jogo, em ordem crescente. O objetivo é determinar a situação do placar após cada gol.
Dado isso, e considerando que o problema garante que não há dois gols no mesmo instante, podemos pensar em utilizar um vetor de marcação, indicando, para cada minuto, quem fez o gol.
Assim, inicialmente passamos pelos minutos dos gols de Paulo e marcamos todos eles com o valor $$1$$. Em seguida, fazemos o mesmo com Camila, marcando o valor $$2$$. Ao final, podemos fazer a simulação do jogo e, para cada minuto $$t$$ em que houve gol, atualizamos a pontuação do respectivo jogador e imprimimos o placar atual.
A complexidade dessa solução é $$O(max_t)$$, pois percorremos todos os minutos possíveis.
Clique aqui para ver o código completo.
Solução alternativa:
Há ainda uma outra maneira interessante de resolver esse problema, utilizando a ideia de manter “dois ponteiros”:
- $$l$$, apontando para o último gol de Paulo
- $$r$$, apontando para o último gol de Camila
Enquanto ainda tiverem gols a serem processados, podemos comparar os tempos de Paulo e Camila e decidir quem marcará o próximo gol. Após isso, atualizamos o devido ponteiro e a pontuação do jogador.
Dessa forma, como cada ponteiro avança $$P$$ ou $$C$$ posições no total, esse algoritmo tem complexidade $$O(P + C)$$.
Clique aqui para ver o código completo.
Mania de Ímpar
Solução escrita por Pedro Rey
Conhecimentos necessários:
Primeiro, vamos analizar quais propriedades uma bandeja deve ter para que ela seja organizada. Considere duas posições adjacentes na matriz. Como a soma delas é ímpar, isso significa que as duas posições tem paridades diferentes. A partir disso, é facil ver que $$G_{i, j} \equiv i + j + G_{1, 1} (\text{mod $2$})$$. Ou seja, as paridades das casas da matriz formam um “xadrez”.
Note que só há dois modos de escolher as paridades das posições de uma matriz organizada, e estas são dependentes na paridade de $$G_{1, 1}$$. Vamos testar as duas alternativas. Para cada posição em que a paridade é diferente da paridade desejada, adicionamos um para alterar a paridade. Agora, basta escolher a menor quantidade de gotas necessarias dentre os dois modos de escolher as paridades.
Clique aqui para ver o código completo.
Um Desafio Muito Distinto
Solução escrita por Otávio Pinheiro
Conhecimentos necessários:
Vamos resolver cada partida como sendo uma query independente.
A primeira observação que vamos fazer para resolver esse problema é que a decisão ótima é sempre pegar o menor inteiro disponível no intervalo para ser o próximo. Para qualquer $$x$$, tal que $$ A \leq x \leq B$$ vamos sempre pegar um intervalo $$[A, x]$$. Veja também que a soma dos valores em $$[a, b]$$, por P.A (Progressão Aritmética), será $$\frac{(b + a)(b – a + 1)}{2}$$.
Note que, se $$x < B$$ e a soma dos valores em um intervalo $$[A, x]$$ for menor que $$L$$, então certamente será possível pegar o intervalo $$[A, x + 1]$$. Portanto, podemos fazer uma binary search que encontra o maior valor de $$x$$ válido.
Clique aqui para ver o código completo.
Feira de artesanato (p1-pS)
Solução escrita por Gustavo Nogueira Mendes
Conhecimentos prévios necessários:
- STL: pair e set / multiset
- Artigo sobre multiset
- obs: para remover é usado para um multiset
s: s.erase(s.find(valor));porques.erase(val);em um multiset apaga todas as ocorrências e queremos apagar apenas uma, então usamos os.find(valor), que retorna um iterator, fazendo apenas um elemento ser apagado, como ems.erase(s.begin()), pois os.begin()é um iterator que referencia o primeiro elemento.
O problema consiste em descobrir uma informação (o somatório do preço dos produtos vendidos) relacionada a um estoque / conjunto de $$N$$ produtos (com dado tipo e preço, que podem se repetir) que sofre $$C$$ alterações. As alterações são de dois tipos:
- 1: Venda do produto de menor preço
- 2: Venda do produto de menor preço de um tipo específico
Como a quantidade de alterações é relativamente grande, notamos que a dificuldade é encontrar uma estrutura eficiente para manter esse conjunto (o estoque) e lidar com as alterações.
Em específico, precisamos manter tanto uma estrutura para descobrir o menor preço de todos os produtos, quanto descobrir o menor preço dentre os produtos de um determinado tipo. Note que uma estrutura não irá interferir na outra, basta usar uma para pesquisar o produto e apagá-lo em ambas.
As nossas estruturas serão:
- Um multiset guardando todos os produtos, com um par de preço (valor pelo qual queremos ordenar os produtos) e tipo (não importa sua ordem, mas precisamos dessa informação para identificar o produto e apagá-lo na outra estrutura). Ele será usado para responder queries do tipo 1.
- Uma lista, onde a posição $$i$$ será um multiset guardando o preço (valor pelo qual os produtos serão ordenados) dos produtos do tipo $$i$$. Note que ao buscar o produto que será “resposta” (será vendido) de uma query do tipo 2, teremos seu tipo e preço, conseguindo indentificá-lo na estrutura 1.