Comentário Noic OBI 2020 - Fase 1 Turno A - Programação Nível 2

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:

Programação Básica

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");
	}

	}

view raw

fissura.cpp

hosted with ❤ by GitHub

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: