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:
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:
https://gist.github.com/rogerioagjr/3a663a961c8c5b4769ba
Capitais
Conhecimento prévio necessário:
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.
https://gist.github.com/rogerioagjr/89d19d714970bd2cc9b8
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:
https://gist.github.com/rogerioagjr/ea7d25d69468d66ea151
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:
- 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:
https://gist.github.com/rogerioagjr/7aa8cdd9c37e8671bb4d
Torre
Conhecimento prévio necessário:
- 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:
https://gist.github.com/rogerioagjr/85c8635c11fa24fbbac3
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