Passes
Solução Escrita por Márcio Vitor
Conhecimentos necessários:
Subtarefa 2 ($$N = 3$$) (20 pontos):
Nessa subtarefa basta verificar se ocorreram passes entre o jogador $$1 e 2$$ e entre os jogadores $$2 e 3$$, mantendo também duas variáveis $$time1, time2$$ que guardam as quantidades de passes para cada time.
Como $$N$$ é bem pequeno é possível resolver usando várias condicionais, caso o aluno não saiba usar loops
Subtarefa 3 (todos os valores de $$J_i$$ são positivos) (20 pontos):
como a todo momento o time $$1$$ é necessário verificar apenas se há uma mudança de jogador entre dois tempos consecutivos. Para isso itere $$i$$ indo de $$2$$ a $$N$$ e verifique se $$J_i \neq J_{i-1}$$ então incremente a variável $$time1$$.
Sem restrições adicionais (100 pontos):
Vamos iterar da mesma forma que a subtarefa $$3$$ porém para para verificar se um passe ocorreu além da mudança de jogadores entre $$i$$ e $$i-1$$ é também necessário verificar se ambos são do mesmo time ou seja se $$J_i$$ e $$J_{i-1}$$ tem mesmo sinal.
nota: uma forma fácil de verificar se dois números $$X,Y$$ têm mesmo sinal é se $$X \cdot Y > 0$$(pelas regras de sinal da multiplicação), para mais detalhes consulte o código abaixo.
Clique aqui para ver o código completo.
Cinema à Distância
Solução escrita por Levi Oliveira
Conhecimentos necessários:
De forma resumida, o problema consiste em encontrar a sessão mais próxima disponível que ainda tenha espaço para cada pessoa. Note que uma pessoa que comprou o ingresso no instante $$T[i]$$ pode assistir a uma sessão $$j$$ somente se $$H[j] \ge T[i]$$. Além disso, cada sessão possui capacidade máxima $$C$$.
Os arrays estão ordenados de forma não decrescente, o que permite que utilizemos a técnica chamada Two Pointers. Assim, vamos percorrer as sessões na ordem em que elas acontecem e manter um ponteiro $$i$$ indicando a primeira pessoa que ainda não foi alocada. Para cada sessão $$j$$, tentamos colocar nela o maior número possível de pessoas, sempre respeitando a capacidade da sessão e o horário de compra do ingresso – com um contador que nos diz quantas pessoas já alocamos na sessão atual.
Considere a sessão $$j$$, com horário $$H[j]$$. Se $$H[j] \ge T[i]$$ e a sessão ainda possui espaço, podemos alocar a pessoa $$i$$ nessa sessão e avançar para a próxima pessoa. Caso contrário, avançamos para a próxima sessão. Se $$T[i] > H[j]$$, como os tempos $$T$$ estão ordenados de forma não decrescente, toda pessoa $$k > i$$ possui $$T[k] \ge T[i] > H[j]$$ e, portanto, também não pode entrar nessa sessão. Se a sessão já estiver cheia, também precisamos avançar, pois não há mais vagas disponíveis. Dessa forma, ao percorrer as pessoas e as sessões em ordem, cada pessoa é alocada na primeira sessão possível, conforme exige o enunciado.
Clique aqui para ver o código completo.
Separador de Produtos
Solução escrita por Theo Sampaio
Conhecimentos necessários:
O problema consiste em separar N produtos com pesos em T filas, priorizando a fila com menor peso, e em caso de empate, a fila com menor index.
Subtarefa 2 (Todos os pesos são iguais a 1) (18 pontos):
Esse caso é um problema interessante por si só. Como todos os pesos são iguais a 1, fica evidente que vamos colocar um produto pra cada fila entre a primeira e a última e repetir até acabar os pesos. Para não ter que simular todo o processo de colocar pesos, é possível inferir que todas as filas terão pelo menos $$\lfloor \frac{N}{K} \rfloor$$ elementos, e as primeiras $$N \bmod K$$ filas terão $$\lfloor \frac{N}{K} \rfloor + 1$$ elementos.
O código dessa parcial fica assim:
Subtarefa 3 ($$F = 2$$) (18 pontos):
Para essa subtarefa, basta continuamente escolher a fila com menor peso das duas filas, e colocar o novo item nela.
Subtarefa 4 ($$N \leq 1000$$)
Podemos aplicar a mesma lógica da parcial 3 e obter uma solução em que para cada item buscamos a menor fila em $$\mathcal{O}(F)$$ e colocamos esse item na fila, totalizando complexidade $$\mathcal{O}(NF)$$. A implementação fica como exercício para o leitor.
Subtarefa 5 (Sem restrições adicionais)
Para resolver essa parcial, basicamente precisamos descobrir, para cada item, a fila com menor peso nesse exato momento, e atualizar valores pontuais na fila. Esse é um problema clássico, e pode ser resolvido uma estrutura de dados pré-pronta (como priority_queue ou set), ou então uma segment tree.
Aqui opto pela solução usando priority_queue por sua legibilidade e simplicidade.
Loja Virtual
Solução escrita por Malu Azevedo
Conhecimentos necessários:
O problema nos pede a maior quantidade de produtos (ou seja, a área máxima de uma submatriz) que, ao ser selecionada e linearizada pelas linhas naturais da matriz, gere uma sequência estritamente crescente.
Ideia Central
Para alcançar a complexidade ótima e resolver os casos com $$N, M \le 800$$ dentro do limite de tempo, podemos transformar este problema de submatrizes em uma variação do clássico “Maior Retângulo em um Histograma” usando uma Pilha Monotônica, combinada com Busca Binária.
Fixando uma coluna inicial $$j$$, queremos descer pelas linhas $$i$$ acumulando “barras” de largura útil. Para que a submatriz seja válida, duas condições precisam ser satisfeitas:
- Na horizontal: Os elementos a partir da coluna na linha devem formar uma sequência estritamente crescente. Pré-calculamos isso na matriz $$pre[i][j]$$, que guarda o tamanho máximo do segmento crescente horizontal começando em $$(i, j)$$ .
- Na vertical (quebra de linha): O último elemento lido de uma linha precisa ser estritamente menor que o primeiro elemento da linha seguinte ($$at[i+1][j]$$).
Para descobrir qual parte do segmento horizontal da linha $$i$$ de fato sobrevive e pode se conectar com a linha $$i + 1$$, não precisamos testar elemento por elemento: como a linha já está ordenada estritamente de forma crescente, usamos uma busca binária (lower_bound) em $$O(\log_2 N)$$ para encontrar quantos elementos a partir de são estritamente menores que $$mat[i+1][j]$$. Guardamos esse limite na matriz $$dp[i][j]$$.
Por fim, para cada coluna $$j$$, simulamos a descida de cima para baixo como se estivéssemos calculando a área de um histograma cujas alturas são as larguras válidas das linhas, utilizando uma pilha monotônica para computar o maior retângulo possível em tempo eficiente.
Subtarefa 2 – $$N = 1$$
Como temos apenas uma linha na matriz, o problema se resume a encontrar a maior subsequência contígua estritamente crescente em um vetor (1D). Basta percorrer as colunas da esquerda para a direita. Se o número atual for maior que o anterior, aumentamos o tamanho da nossa sequência atual em 1. Se não for, a sequência quebrou e recomeçamos a contagem a partir do número atual. A resposta é o tamanho máximo alcançado.
Complexidade: $$O(M)$$
Subtarefa 3 – $$N,M \le 20$$
Com limites tão pequenos, uma solução de Força Bruta ingênua funciona. Podemos testar absolutamente todas as submatrizes possíveis. Usamos 4 laços de repetição para escolher as “bordas” da submatriz: linha inicial, linha final, coluna inicial ($$L$$) e coluna final ($$R$$). Com a submatriz definida, fazemos mais laços para passar por todos os elementos dentro dela e verificar se, ao linearizar, todos formam uma sequência estritamente crescente. Complexidade: $$O(N^2 \cdot M^3)$$
Subtarefa 4 – $$N,M \le 100$$
A Força Bruta anterior já seria muito lenta. Aqui, podemos otimizar a ideia. Em vez de testar todas as submatrizes do zero, podemos fixar a linha inicial, a linha final e a coluna esquerda (L). Depois, começamos a expandir a coluna direita (R) passo a passo. Assim que o próximo elemento adicionar uma quebra na regra (ou não for maior que o anterior na mesma linha, ou quebrar a regra de transição entre as linhas selecionadas), paramos a expansão imediatamente. Complexidade: $$O(N^2 \cdot M^2)$$
Subtarefa 5 – $$N,M \le 500$$
Aqui é onde a Programação Dinâmica (DP) entra em prática: Não podemos mais fixar duas linhas diferentes. Vamos fazer uma varredura linha por linha mantendo um estado: $$dp[L][R]$$ vai guardar a “quantidade de linhas” válidas que terminam na linha atual e usam exatamente o intervalo de colunas de até . Para a linha atual, verificamos se o intervalo de até é crescente. Se for, olhamos para a linha de cima: se o último elemento de cima for menor que o primeiro de baixo ($$mat[i-1][R] < mat[i][L]$$), então $$dp[L][R] = dp\_anterior[L][R] + 1$$. Se não puder conectar, a sequência quebra e começamos uma nova submatriz ali, fazendo $$dp[L][R] = 1$$. Guardamos a área máxima, que será $$dp[L][R] \dot (R – L + 1)$$. Complexidade: $$O(n \cdot M^2)$$
Subtarefa 6 – Sem restrições adicionais
Para garantir os 100 pontos absolutos, convertemos a ideia do problema para o clássico Maior Retângulo no Histograma. Em vez de testar todos os pares de colunas ($$L,R$$), testamos apenas qual é a “largura máxima útil” que uma coluna inicial $$j$$ consegue ter ao descer pelas linhas. Para conectar a linha de cima com a de baixo, usamos uma Busca Binária (lower_bound) para descobrir rapidamente onde a sequência da linha atual precisa ser “cortada” para que o último elemento seja menor que o primeiro da próxima linha. Com as larguras (alturas do histograma) de cada linha calculadas, usamos uma Pilha Monotônica (Stack) para calcular a maior área possível descendo pelas linhas. Complexidade: $$O(N \cdot M)$$