Comentário NOIC OBI 2015 - Fase 2 - Programação Nível 1

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível 1 da OBI 2015, clique aqui.

Impedido!

Conhecimento prévio necessário:

  1. Entrada e saída (Aula 1 do Curso Noic)
  2. Estruturas condicionais (Aula 2 do Curso Noic)

O enunciado do problema é bem simples e a tarefa é bem direta:

Dadas as posições desses três jogadores, no momento exato do lançamento, haverá impedimento se e somente se a seguinte condição for verdadeira:

(R >50) e (L < R) e (R > D)

A regra parece estranha, não é mesmo? Mas a gente nem precisa entender a lógica dela. O seu programa deve apenas determinar, dadas as três posições L; R e D, se há ou não impedimento, implementando exatamente a condição acima

Inicialmente, vamos declarar e salvar os valores de l, r e d, que estarão nessa ordem na entrada. Feito isso, vamos usar um if para verificarmos se a condição do enunciado foi atendida ("if(r>50 && l<r &&  r>d)"). Se o jogador estiver impedido, imprimimos uma única linha com o caractere 'S' ("printf("S\n");"). Se ela não for, imprimo o caractere 'N' ("else printf("N\n");"). Segue o código para melhor entendimento:


// Impedido! - F2PJ/F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(1)
#include <cstdio> // scanf e printf
int main(){
// declaro e leio os valores de l, r e d
int l, r, d;
scanf("%d %d %d", &l, &r, &d);
// se as condições apresentadas no enunciado forem atendidas, imprimo o caractere 'S'
if(r>50 && l<r && r>d) printf("S\n");
// caso contrário, imprimo uma linha com o caractere 'N'
else printf("N\n");
return 0;
}

view raw

impedido.cpp

hosted with ❤ by GitHub

Capitais

Conhecimento prévio necessário:

  1. Distância em árvores (LCA) (Aula 14 do Curso Noic)
  2. Ordenação (Aula 5 do Curso Noic)

A abordagem mais ingênua para o problema seria calcular a distância entre todos os possíveis pares de capitais através do LCA e então imprimirmos a menor delas. Entretanto, calcular a distância com LCA tem complexidade O(log n), e o número de pares de capitais é da ordem de n², logo, a complexidade final do problema seria n² * O(log n) = O(n² log n). Infelizmente, o valor de n vai até 100000, o que é muito grande para uma complexidade dessas.

O problema dessa abordagem é o recálculo, visto que, no problema, precisamos da menor distância entre todos os possíveis pares de capitais. A primeira coisa que vamos fazer é ler o grafo e salvá-lo como uma lista de adjacências, no array de vector chamado lista. Agora, o próximo passo é montar a árvore, como em um algoritmo de LCA comum. Usaremos uma DFS para explorar todo o grafo a partir de uma raiz (será o vértice 1) e salvar o pai de cada vértice em um vetor pai e o nível de cada um no vetor lvl. Faremos pai[1] = 1 e lvl[1] = 0.


#define MAXN 100100
// declaro as variáveis
int pai[MAXN], lvl[MAXN];
// declaro a lista de adjacência
vector<int> lista[MAXN];
// DFS para montar a árvore
int dfs(int v=1){ // partindo do vértice V para baixo
// para cada vizinho de v
for(int i=0; i<lista[v].size(); i++){
// seja U o vizinho que estou explorando
int u=lista[v][i];
// se ele já tiver sido explorado, continuo
if(pai[u]) continue;
// caso contrário
// o pai de U é V
pai[u]=v;
// e, portanto, seu nível é o nível de V mais 1
lvl[u]=lvl[v]+1;
// e chamo a DFS em U
dfs(u);
}
}

view raw

dfs_capitais.cpp

hosted with ❤ by GitHub

Agora, ao invés de procurarmos o LCA de cada par de capitais, vamos olhar para cada cidade como o LCA entre todas as capitais que são descendentes dela, para então vermos quais duas têm a menor distância. Vamos declarar o vetor menor  e em menor[v] guardamos o nível da capital de menor nível (mais alta na árvore) que é filha do vértice v. Percorreremos a árvore nível a nível, logo, o primeiro passo será ordenar as cidades pelo nível (o maior nível antes), e guardar esta ordenação no vetor ord. Feito isso, usaremos um for para percorrer o vetor. Com a ordenação, garantimos que pais só são processados depois de seus filhos. Suponha que estamos no vértice v e seu pai é p. Se menor[v] ainda for zero, então nenhum filho de v foi processado, logo ele não tem filhos e é uma capital. Deste modo, a capital mais alta que é filha de v é ela mesma e menor[v] = lvl[v]. Se menor[p] ainda for zero, então nenhum outro filho de p foi processado ainda e não temos como saber a distância de v para outras capitais que sejam descendentes de p. Deste modo, menor[p]=menor[v] e vamos para o próximo vértice.

Se, porém, já tivermos processado algum outro filho de p, a altura do mais alto dentre eles estará salva em menor[p]. Seja u um outro descendente de p. Como visto no LCA comum, a distância entre v e u é lvl[v]+lvl[u]-2*lvl[p]. Deste modo, o descendentes de p mais próximos serão os de menores níveis (mais altos) e por isso só guardamos o nível do descendente mais alto de cada vértice que é capital. Visto isso, sabemos que a menor distância entre o descendente mais alto de v e outra capital descendente de p já explorada é menor[v]+menor[p]-2*lvl[p]. Se isso for menor que a menor distância conhecida (que salvaremos em resp) ele será a nova resposta. Agora basta atualizarmos o valor de menor[p]: se a altura da capital mais alta que é filha de v for menor que menor[p], então menor[p]=menor[v]. Fazemos isso para todos os vértices menos a raiz (pois ela não tem pai), logo só vamos até a penúltima casa de ord.

Note que como não processamos a raiz, é possível que ela seja a capital e a resposta seja a distância entre ela e outra capital. Porém, este é um problema facilmente resolvido, pois a capital mais próxima da raiz é a de menor nível! Assim, se a raiz for uma capital, vamos percorrer todos os vértices verificando se eles são capitais. Para cada capital, verificamos se seu nível (distância para a raiz) é menor que o valor salvo em resp, e se for, atualizamos a resposta! Agora, basta imprimir o valor salvo em resp. Segue o código para melhor entendimento:


// Capitais - F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(n log n)
#include <cstdio> // scanf e printf
#include <vector> // vector
#include <algorithm> // função min
using namespace std; // para uso do C++
// definoos valores de INF e MAXN
#define MAXN 100100
#define INF 0x3f3f3f3f
// defino PB como push_back
#define PB push_back
// declaro as variáveis que vou usar
vector<int> lista[MAXN], ord;
int n, pai[MAXN], lvl[MAXN], menor[MAXN], resp=INF;
// DFS para montar a árvore
int dfs(int v=1){ // partindo do vértice V para baixo
// para cada vizinho de v
for(int i=0; i<lista[v].size(); i++){
// seja U o vizinho que estou explorando
int u=lista[v][i];
// se ele já tiver sido explorado, continuo
if(pai[u]) continue;
// caso contrário
// o pai de U é V
pai[u]=v;
// e, portanto, seu nível é o nível de V mais 1
lvl[u]=lvl[v]+1;
// e chamo a DFS em U
dfs(u);
}
}
// função para ordenação dos vértices por nível
bool cmp(int x, int y){
return lvl[x] > lvl[y];
}
int main(){
// leio o valor de n
scanf("%d", &n);
// leio a árvore da entrada
for(int i=1; i<n; i++){
int v, u;
scanf("%d %d", &v, &u);
lista[v].PB(u);
lista[u].PB(v);
}
// defino 1 como pai de si mesmo
pai[1]=1;
// e chamo a DFS tendo 1 como raiz da árvore
dfs();
// preecho o vetor ord com o vértices de 1 a n
for(int i=1; i<=n; i++) ord.PB(i);
// ordeno o vetor pelo nível dos vértices
sort(ord.begin(), ord.end(), cmp);
// percorro vetor ordendo
for(int i=0; i<ord.size()-1; i++){
// v é o vértice atual e p é seu pai
int v=ord[i], p=pai[v];
// se menor[v] ainda é zero, ele não tem filhos e é capital
// logo a capital mais alta que descende de v é ele mesmo
if(!menor[v]) menor[v]=lvl[v];
// se menor[p] ainda é zero
// então não processamos nenhum outro filho de p
if(!menor[p]){
// logo o menor[p] será menor[v]
menor[p]=menor[v];
// e continuo para o próximo vértice
continue;
}
// se menor[p] não for zero, vemos se a distância do descendente mais alto de v
// para o mais alto de p é menor que a resposta que temos até agora
// se for, essa será a nova resposta
resp=min(resp, menor[p]+menor[v]-2*lvl[p]);
// por fim, vemos se a capital descendente mais alta de v é mais alta
// que a mais alta de p encontrada até agora
// se for, ele será o novo descendente mais alto de p
menor[p]=min(menor[p], menor[v]);
}
// se a raiz (1) for capital (tiver um único vizinho)
if(lista[1].size()==1)
// percorremos todo o grafo
for(int v=2; v<=n; v++)
// para cada capital, se a sua distância para a raiz (seu nível)
// for menor que a resposta, essa distância será a nova resposta
if(lista[v].size()==1) resp=min(resp, lvl[v]);
// por fim, imprimo o valor salvo em resp
printf("%d\n", resp);
return 0;
}

view raw

capitais.cpp

hosted with ❤ by GitHub

A complexidade é O(n log n) porque chamamos a função sort. Porém, como os valores ordenados são pequenos (n < 100000), podemos ordenar o vetor em O(n) e a complexidade do código ficaria O(n), mas isso não é necessário.

Letras

Conhecimento prévio necessário:

  1. LIS (Maior Subsequência Crescente) (Aula 19 do Curso Noic)

O problema é uma aplicação direta do algoritmo de LIS, com duas pequenas diferenças do que foi mostrado na aula 19 do curso. Em primeiro lugar, o problema não pede exatamente a maior sequência crescente, mas a maior subsequência não decrescente, ou seja, podemos repetir elementos. Este tipo de problema é citado no fihttps://gist.github.com/rogerioagjr/7aa8cdd9c37e8671bb4dm da aula de LIS e é facilmente resolvido: trocamos lower_bound por upper_bound. Outro pequeno detalhe é que a entrada não será uma sequência de inteiros, mas uma string. Este problema também é facilmente resolvido: basta lermos a string, salvá-la e depois percorrê-la executando o algoritmo. O código não passa de uma pequena adaptação do que é mostrado na aula de LIS do curso:


// Letras - F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(n log n)
#include <cstdio> // scanf e printf
#include <algorithm> // upper_bound
#include <vector> // vector
#include <cstring> // strlen
using namespace std; // para uso do C++
#define PB push_back // por simplicidade
#define MAXN 300300 // defino o valor de MAXN
// declaro as variáveis que vou usar
vector<char> pilha;
int n;
char frase[MAXN];
int main(){
// leio a string da entrada
scanf(" %s", frase);
// defino n como o tamanho da frase
n=strlen(frase);
// para cada elemento
for(int i=0; i<n; i++){
// guardo seu valor em x
char x = frase[i];
// declaro um iterador que guardará o elemento mais à esquerda de pilha
// que não é menor que x
vector<char>::iterator it = upper_bound(pilha.begin(), pilha.end(), x);
// se it for o fim do vector, então não há elemento que não seja menor que x
// ou seja, todos os topos de pilha são menores ou iguais a x
// logo, criamos uma nova pilha e colocamos x no seu topo
if(it==pilha.end()) pilha.PB(x);
// porém, se it apontar para alguma posição válida do vector
// colocamos x no topo desta pilha, substintuindo o valor que it aponta por x
else *it = x;
}
// no fim, basta imprimir a quantidade de pilhas
printf("%d\n", pilha.size());
return 0;
}

view raw

letras.cpp

hosted with ❤ by GitHub

Torre

Conhecimento prévio necessário:

  1. Vetores e matrizes (Aula 3 do Curso Noic)

A tarefa é clara: devemos encontrar o peso de cada uma das casas do tabuleiro para então descobrirmos qual delas tem o maior. Uma abordagem ingênua para o problema seria, para cada casa, somar, uma a uma, todas as casas da linha e da coluna em que nos encontramos. Tal cálculo, entretanto, tem complexidade O(n), pois cada linha ou coluna tem, no máximo, n casas. Para calcularmos o peso de todas as casas, deveríamos realizar essa operação n2 vezes (pois são n2 casas), o que daria uma complexidade final de n2 * O(n) = O(n3).

Infelizmente, o valor de n vai até 1000, o que é muito grande para uma complexidade dessas e o programa acabaria levando TLE (Tempo Limite Excedido). Note, porém, que recalculamos várias vezes a soma de uma mesma linha, o que é uma tremenda perda de tempo, já que poderíamos calcular a soma de cada linha apenas uma vez u usá-la sempre que fosse necessária. Para isso, vamos salvar o tabuleiro em uma matriz de inteiros de nome tab  dimensões 1010 x 1010. Nela, a casa tab[i][j] guarda o valor da casa do tabuleiro da linha i e coluna j. Além disso vamos declarar dois vetores de inteiros com 1010 posições cada: o linha e o coluna. Desse modo, linha[i] irá guardar a soma de todos os elementos da linha i enquanto que coluna[j] irá guardar a soma de todos os elementos da coluna j.

Vamos agora preencher os valores de linha e coluna. Declaremos eles como globais (fora da main) para que todos os seus valores comecem zerados. Agora, vamos percorrer todas as linhas da matriz, somando cada elemento de cada uma delas na posição dessa linha do vetor linha. Vamos fazer um for que percorrerá todas as linhas ("for(int i=1; i<=n; i++)"). Agora, para cada linha i, vamos fazer um for que percorre todos os seus elementos e soma seu valor em linha[i] ("for(int j=1; j<=n; j++) linha[i]+=tab[i][j];"). Feito isso, teremos salvo a soma de todas as linhas. Agora, basta fazermos o mesmo com as colunas, com o comando: ("for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) coluna[i]+=tab[j][i];").

Agora que já temos todas as somas salvas, podemos calcular o peso de cada casa em O(1) e descobrir qual delas é a maior de maneira rápida. Vamos declarar uma variável resp que começa com valor -INF, onde INF é um número bem grande (eu geralmente uso 0x3f3f3f3f, pois ele pode ser multiplicado por 2 sem que ocorra overflow e ser usado na função memset). Feito isso, vamos percorrer todo o tabuleiro, olhando o peso de cada casa. Se o peso for maior que resp, atualizamos o valor de resp para o peso calculado, pois ele é o maior já encontrado. Isso pode ser feito fazendo resp receber o máximo entre o peso e resp. Após percorrermos todo o tabuleiro, basta imprimirmos o valor salvo em resp.

Mas como calcular o peso de uma casa? Suponha que estamos na casa (i,j). Seu peso será a soma de toda a linha i e de toda a coluna j. Porém, o valor da casa (i,j) está tanto na soma da linha como na soma da coluna, logo estamos contando-o duas vezes. Deste modo, temos que subtrair duas vezes seu valor da soma da linha i com a coluna j, para que ele não seja contado. O valor da casa (i,j) está salvo em tab[i][j], a soma da linha i está em linha[i] e a da coluna j está em coluna[j]. Assim, o peso da casa (i,j) é linha[i]+coluna[j]-2*tab[i][j]. Segue o código para melhor entendimento:


// Torre - F2PJ/F2P1 - OBI 2015
// Rogério Júnior
// Complexidade: O(n²)
#include <cstdio> // scanf e printf
#include <algorithm> // função max
using namespace std; // algorithm
#define MAXN 1010 // defino o valor de MAXM como 1010
#define INF 0x3f3f3f3f // defino o valor de INF
// declaro as variáveis que vou usar
int n, resp=-INF, tab[MAXN][MAXN], linha[MAXN], coluna[MAXN];
int main(){
// leio o valor de n
scanf("%d", &n);
// leio os valores das casas do tabuleiro
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d", &tab[i][j]);
// calculo a soma de cada linha
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
linha[i]+=tab[i][j];
// calculo a soma de cada coluna
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
coluna[i]+=tab[j][i];
// percorro todo o tabuleiro, calculando o peso de cada casa
// e guardando o maior valor encontrado na variável resp
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
resp=max(resp, linha[i]+coluna[j]-2*tab[i][j]);
// por fim, imprimo o valor salvo em resp
printf("%d\n", resp);
return 0;
}

view raw

torre.cpp

hosted with ❤ by GitHub

 

Se você ainda tiver alguma dúvida em algum dos problemas, vá para a página inicial do Curso Noic de Informática e preencha o formulário para nos enviar sua dúvida.https://gist.github.com/rogerioagjr/ea7d25d69468d66ea151