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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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: