Comentário por Pedro Racchetti e Luca Dantas
Para conferir a prova na íntegra, clique aqui.
Acelerador de Partículas
Conhecimento Prévio Necessário:
Para a resolução dessa questão é importante conhecer o uso do operador de módulo, que em C++ é representado por $$\%$$, ou também pode ser feito utilizando a estrutura de repetição while já que os limites do problema são baixos. Porém, utilizaremos aqui o operador de módulo, pois é a solução adequada e mais eficiente.
O primeiro fator a ser percebido é que não importa onde a partícula termine, ela vai terá que passar por três seções antes de entrar no ciclo, e também, depois de sair do ciclo, terá que passar por mais duas. Então, após lermos a distância a ser percorrida no início, podemos subtrair $$5$$ do valor total e assim reduzimos o problema a encontrar qual o ponto em que a partícula sairá do ciclo.
É fácil perceber que enquanto a distância a ser percorrida dentro do ciclo for maior ou igual a $$8$$ (tamanho do ciclo) a partícula poderá simplesmente dar uma volta completa e voltar para o ponto anterior com $$8$$ quilômetros a menos a serem precorridos. Desse modo, o que queremos encontrar é a quantidade de quilômetros restantes após todos esses ciclos já terem sido contabilizados. É possível perceber que:
- Se $$1$$ quilômetro restar, o ponto final será o sensor $$1$$.
- Se $$2$$ quilômetros restarem, o ponto final será o sensor $$2$$
- Se $$3$$ quilômetros restarem, o ponto final será o sensor $$3$$
Lembre-se de confirmar os pontos acima na imagem disponibilizada na questão. Assim, para retirarmos essa repetição dos ciclos, basta tirarmos a distância a ser percorrida em módulo $$8$$ ($$a \% b$$ ou “$$a$$ módulo $$b$$” é igual ao resto da divisão de $$a$$ por $$b$$).
Assim, a complexidade final da solução é $$O(1)$$. Segue o código abaixo para melhor compreensão:
Promoção de Primeira:
Conhecimentos prévios necessários:
- Programação Dinâmica (DP)
- Árvores (Conhecer as principais propriedades e saber utilizá-las)
- Busca em profundidade (DFS)
A primeira observação importante é perceber que o reino de linearlândia pode ser representado como uma árvore, já que temos $$N$$ vértices e $$N-1$$ arestas e todos os vértices estão conectados por pelo menos um caminho. (Perceba que também consequentemente não há ciclos).
Podemos nos valer dessas propriedades de árvore e “enraizá-la” em um vértice qualquer e assim buscar a resposta para cada sub-árvore enraizada. Caso o conceito de “enraizar” uma árvore não seja familiar, observe a imagem: nela o vértice $$1$$ está se comportando como a raiz da árvore, e também é importante perceber que, como o grafo é uma árvore, é garantido que cada uma das sub-árvores formadas pelos filhos da raíz (no caso do desenho as subárvores formadas por $$3$$, $$4$$ e $$5$$) nunca se conectam, pois por definição uma árvore não possui ciclos e existir alguma ligação entre essas sub-árvores implicaria um ciclo. Essa observação segue recursivamente para todos os filhos (no caso do desenho é possivel perceber que a sub-árvore formada por $$5$$ segue as mesmas propriedades e implicações da árvore formada com raiz em $$1$$).
Antes de entrar na explicação da ideia trataremos cada linha de ônibus como uma cor para a aresta, sendo preto para a RoyalBus e branco para a ImperialBus.
Tendo essa definição em sub-árvores, podemos utilizar um conceito de programação dinâmica e nos perguntar o que realmente importa em cada uma das sub-árvores que poderia ser útil para calcular a resposta da sub-árvore atual. Defina $$maior_{branco}[u]$$ como o maior caminho que sai do nó $$u$$, termina na subárvore de $$u$$ e possui arestas de cores alternadas, onde a primeira aresta saindo de $$u$$ possui cor branca. Defina $$maior_{preto}[u]$$ analogamente. Podemos chegar no seguinte lema:
Lema: se o caminho da resposta estiver totalmente contido na sub-árvore de um nó $$u$$ e passar por este nó, esse caminho será composto pela união de dois outros caminhos:
- O caminho representado em $$maior_{branco}[u]$$
- O caminho representado em $$maior_{preto}[u]$$
O lema acima vale devido ao fato de que o caminho que passa por $$u$$ deverá ter arestas consecutivas com cores alternadas. Logo, é sempre ótimo escolhermos os caminhos de tamanho máximo para as duas cores (branco e preto).
Assim, precisamos encontrar, para cada vértice $$u$$, os valores $$maior_{branco}$$ e $$maior_{preto}$$. Podemos encontrá-los utilizando uma ideia similar a Programação Dinâmica, realizando uma $$DFS$$ na árvore. A resposta final do problema é, assim, o valor máximo de $$maior_{branco}[u] + maior_{preto}[u] + 1$$ dentre todos os vértices $$u$$ da árvore.
A complexidade final da solução é $$O(n)$$. Confira o código abaixo para melhor entendimento:
Fissura Perigosa
Conhecimento prévio necessário:
Para resolver esse problema podemos usar uma DFS ou BFS (no código abaixo foi utilizada a DFS) para realizarmos um flood fill na matriz, partindo da posição do canto superior esquerdo. Além disso, precisamos garantir que, ao passar de uma posição a outra, essa nova posição não tem altitude maior que a força inicial. Outro possível caso de erros acontece quando a primeira posição tem altitude maior que a força, e o modo de entrada, já que a matriz é dada como uma série de $$strings$$ de números.
Complexidade: $$O(N^2)$$
Segue o código, comentado, para melhor compreensão:
| #include<bits/stdc++.h> | |
| using namespace std; | |
| int orig[512][512]; //matriz original, dada na entrada. | |
| int dx[5] = {1, 0, -1, 0}; | |
| int dy[5] = {0, 1, 0, -1}; //vetores de auxílio, que servirão como | |
| //arestas no grafo. | |
| int n, f; | |
| void dfs(int i, int j){ | |
| orig[i][j] = 100; | |
| //definimos a posição i j como 100, valor absurdo | |
| //para que, no momento de saída, se reconheca o fato que é de fato uma | |
| //posição atingida pela lava | |
| for(int k = 0; k < 4; k++){ | |
| int ii = i + dx[k]; | |
| int jj = j + dy[k]; | |
| if(ii <= 0 || ii > n || jj <= 0 || j > n) continue; | |
| if(orig[ii][jj] > f) continue; | |
| dfs(ii, jj); | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d", &n, &f); | |
| for(int i = 1; i <= n; i++){ | |
| for(int j = 1; j <= n; j++){ | |
| char c; | |
| scanf(" %c", &c); | |
| //lemos cada posição como um caractér, e depois os transformamos | |
| //em um inteiro | |
| int k = c – '0'; | |
| orig[i][j] = k; | |
| } | |
| } | |
| if(orig[1][1] <= f){ | |
| dfs(1, 1); | |
| //se a posicao inicial tiver altitude menor que a forca, iniciamos a DFS | |
| } | |
| for(int i = 1; i <= n; i++){ | |
| for(int j = 1; j <= n; j++){ | |
| if(orig[i][j] > 9){ | |
| //todos os poontos atingidos estao marcados como 100 | |
| printf("*"); | |
| }else{ | |
| printf("%d",orig[i][j]); | |
| } | |
| } | |
| printf("\n"); | |
| } | |
| } |
Pandemia
Conhecimento prévio necessário:
Para esse problema, podemos primeiro perceber que qualquer reunião que tenha acontecido antes do primeiro amigo ser infectado, não influenciará na resposta, portanto podemos ignorá-las. Iremos guardar as reuniões em um vetor de $$vectors$$, onde cada $$vector$$ desse vetor guarda os amigos que estiveram presentes na reunião. Além disso, iremos usar um vetor de marcação para representar os amigos já infectados. Como o total de reuniões e amigos são pequenos, podemos fazer um algoritmo com complexidade $$O(N*M)$$. Podemos portanto passar por todas as reuniões, e sempre que houver ao menos uma pessoa infectada, marcamos todos os presentes no vetor de marcação. No final, basta iterar pelo vetor de marcação, e aumentar a resposta por um sempre que houver um infectado marcado.
Complexidade: $$O(N*M)$$
Segue o código, comentado para melhor compreensão:


