#3 Exercícios Aleatórios

Nest post vou comentar sobre os seguintes exercícios:

Dudu Faz Serviço – Grafos, Busca em Profundidade.
Brincando Com Operadores – AdHoc.
Jaida e o Jogo de Multiplicar – Teoria dos Números, Primos, Crivo de Eratóstenes.

Eu recomendo que vocês tentem resolver o exercício acima antes de ler a solução abaixo. Assim suas teorias podem ser comparadas/contrastadas com as minhas, e isso pode ajudar no aprendizado.

Dudu Faz Serviço – [uri]

Este exercício pode ser resolvido utilizando o algoritmo Busca em Profundidade da Teoria dos Grafos, geralmente referenciado como DFS (Depth First Search). O primeiro passo é montar um grafo com N vértices, e para cada dependência de documento dada no enunciado inserir um vértice direcionado nesse grafo.

Para ajudar a identificar um loop nesse grafo, vamos utilizar uma “técnica” de coloração dos vértices conforme eles vão sendo visitados. As cores utilizadas serão white (branco), grey (cinza) e black (preto).

Conforme os vértices vão sendo visitados pela DFS eles vão mudando de cor, indicando o estado da busca atual. O pseudo-código da DFS fica da seguinte maneira:
– Inicialmente todos os vértices são pintados com a cor white, indicando que eles ainda não foram visitados.
– Assim que um vértice é visitado, e antes dele ser “desvisitado”, sua cor passa a ser grey.
– Para cada vértice sendo visitado, ele irá visitar todos os seus vizinhos.
– Quando um vértice é “desvisitado”, ou seja, a função chega ao final, a cor desse vértice passa a ser black.

Para resolver nosso problema em específico (encontrar loops), podemos tirar vantagem do seguinte insight: se um vértice u da cor grey visitar um vértice v também de cor grey, isso indica que há um caminho entre o vértice v que chegou até o vértice u, assim como há um caminho entre o vértice u que chega até o vértice v, ou seja, um loop. Segue o algoritmo em questão em C++:

// assuma que retornar true significa que está tudo ok (não há loops).
bool dfs(int u) {
    color[u] = grey;

    for(int i=0; i<adj[u].size(); i++) {
        int v = adj[u][i];
        if(color[v] == white) {
            if(!dfs(v)) {
                return false;
            }
        } else if(color[v] == grey) {
            return false;
        }
    }

    color[u] = black;
    return true;
}

 Brincando Com Operadores – [uri]

Com o decorrer das operações sendo realizadas no vetor de inteiros, podemos notar que temos em mão umas espécia de árvore binária, onde cada nó ou é uma folha (um dos valores dados na entrada) ou tem um ou dois filhos, e seu valor é o resultado de uma das operações (adição ou subtração) aplicada sobre seu(s) filhos. Segue um exemplo desta árvore com um dos exemplos de entrada:

        -7            (soma)
   -2        -5       (subtração)
 6    8    7    12    (soma)
4 2  3 5  1 6  10 2   (folhas)

O exercício então nos pede que realizemos updates nas folhas, e que o resultado final seja adaptado coerentemente. Poderíamos simplesmente fazer os updates nas folhas e recalcular toda a árvore do início, porém isso nos consumiria muito tempo (muitas folhas, e muitos updates), logo precisamos pensar em algo mais eficiente.

Um insight importante sobre esta árvore é que alterar o valor de uma folha não afeta o valor de todos os outros nós. De fato, ele só altera o valor de no máximo ⌈lg N⌉+1 nós. Por exemplo, vamos aplicar um update na terceira folha da árvore acima, e prestar atenção nos valores que de fato mudaram:

        [-4]           (soma)
   [1]        -5       (subtração)
 6   [5]    7    12    (soma)
4 2 [0] 5  1 6  10 2   (folhas)

Logo, em vez de reconstruirmos toda a árvore do início, uma estratégia mais eficiente seria apenas atualizar alguns dos valores, e imprimir então o resultado final.

Jaida e o Jogo de Multiplicar – [uri]

Vamos rever algumas definições da Teoria dos Números:

(1) Um inteiro positivo K é considerado primo se, e somente se, ele tem exatamente dois divisores: 1 e K. (Uma exceção é o inteiro 1, que é considerado primo mesmo só tendo um divisor.)
(2) Um inteiro positivo K é considerado composto se, e somente se, ele não é primo. Ou seja, ele tem três ou mais divisores.
(3) Um inteiro composto pode ser fatorado com dois ou mais inteiros primos. Logo, seja K um inteiro composto, pi inteiros primos, e ai inteiros positivos, X = (p1^a1) * (p2^a2) * … * (pi ^ ai).
Por exemplo, 45 = (3*3*5) = (3^2) * (5^1), onde 45 é um inteiro composto e 3 e 5 são inteiros primos.

É interessante notar que, utilizando a operação de multiplicação citada no exercício e lembrando da definiCão (3) acima, é possível obter todos os números compostos até K, desde que na lista já existam todos os primos menores que K.

Por exemplo, se na lista eu tenho os primos 1, 2 e 3, é possível obter os compostos 4 (2*2), 6 (2*3) e 8 (2*2*2), mas não os primos 5 e 7. Logo, a resposta seria 4.
Se os primos 5 e 7 já estivessem na lista, eu poderia continuar e obter os compostos 9 (3*3), 10 (2*5), mas não o primo 11. Logo, a resposta seria 10.

Reduzimos então o exercício em: encontre o menor primo P não contido na lista, e imprima P-1.

Para saber qual o menor primo não contido na lista precisamos antes listar todos os primos de nosso interesse (para podemos compará-los). Vejamos, a lista contém N <= 10^6 inteiros. Vamos supor o pior caso possível, onde todos os inteiros da lista são primos e todos em sequência (1, 2, 3, 5, 7, etc). Logo, precisamos pré-calcular quais são os 10^6 primos. O algoritmo mais recomendado para este tipo de pré-cálculo de primos é o Crivo de Eratóstenes.

Pré-calcule então os 10^6 primeiros inteiros com o algoritmo do Crivo (um limite de aproximadamente 2*10^8 é mais do que suficiente), guarde-os em uma lista, e leia a lista com os N inteiros. Para cada número primo da lista, sinalize como “presente” este primo na sua pré-calculada lista de primos. Ao final, analize a sua pré-calculada lista de primos, e o primeiro primo não sinalizado como “presente” é o resultado do nosso problema. Imprima este primo P-1.

 

É isso. Se você tiver alguma dúvida, crítica ou sugestão, deixe um comentário abaixo.

Até mais 🙂

23 ideias sobre “#3 Exercícios Aleatórios”

  1. Olá Cristhian, obrigado pela explicação dos exercícios, são de grande ajuda ^^.

    O problema D – Jogo Entediante, que fez parte desse contest, me deixou intrigado. Teria como dar algumas dicas para tentar resolvê-lo de forma eficiente?

    Além disso, tenho uma dúvida em relação aos níveis dos problemas, é o seguinte:
    Como é calculado o nível de um problema? Pois há problemas de nível 6 que são mais fáceis que um de 3, por exemplo.

    Valeu!

    1. O problema D também me deixou confuso no comeco. Ele é de uma classe de problemas que alguns chamam de “Don’t think hard, think smart”. São problemas que são “fáceis”, mas a resposta está meio “escondida”.
      Ele é muito similar a um problema que caiu na Warmup da Regional da ICPC desse ano, o “Fechem as portas”. Eu escrevi sobre ele no meu blog antigo, dá uma olhada:
      http://crbonilha.blogspot.co.uk/2013/08/abstraindo-um-problema.html

      Em relacão ao nível dos problemas, trata-se de algo meio subjetivo. Primeiro por que o que é fácil pra mim pode não ser fácil para você, e vice-versa, e segundo que o URI as vezes deixa aberto aos usuários escolherem o nível do problema quando eles estão adicionando, e isso recai no primeiro item citado.
      Quando eu noto que há uma classificacão bem fora do padrão (um 8 muito fácil, ou um 3 muito difícil), eu mando um e-mail pedindo pra eles reverem. Você pode fazer o mesmo quando sentir necessidade.

  2. Consegui achar o padrão, mas só depois de parar e pensar o que realmente afetaria o resultado. Onde nesse caso, o resultado só é afetado por número de divisores ímpares, se for par, vai permanecer o mesmo ganhador que o inicial. (O que de fato, é igual ao problemas das portas haeuhaeuh).

    Realmente, a abstração de um problema é super importante para a resolução do mesmo.

    Valeu pela ajuda! 😀

  3. Cristhian, no problema Brincando Com Operadores tu usou segment tree né? O exemplo que tu colocou tem 8 elementos logo uma potência de 2. Mas e pra exemplos mais irregulares? Se tivesse 6? Quando eu tentei fazer dava erro pq eu dividia esse 6 em 2 partes com 3 elementos. Mas o elemento da borda direita da parte da esquerda com o elemento da borda esquerda da parte direita precisavam ser calculados juntos. Cheguei na conclusão depois do contest que o lado esquerda do segment tree tinha sempre que ter tamanho par (com excessão na hora de dividir um nó de tamanho 2). Não cheguei a programar ainda pra testar. Mas tu teve esse mesmo problema?

    1. Dependendo da forma que a Segment Tree for implementada você pode acabar tendo esse tipo de problema mesmo. Eu implementei usando sempre potências de 2 para o alcance de cada nó. Quando havia casos irregulares, os nós à direita teriam o valor 0, não afetando o resultado final. Logo, casos onde N = 6 seriam transformados em N = 8, por exemplo.

  4. Gostaria de agradecer e parabenizar pelo blog, os exercícios comentados tanto nesse como no seu antigo me ajudam muito a estudar. Na faculdade onde estudo não existem professores experientes em maratona, então quando fico travado em um exercício fica complicado de progredir.

    Seu blog já me ajudou em diversos assuntos e exercícios, obrigado!!!

  5. Olá Cristhian, parabéns pelo blog!

    Estou iniciando (na verdade já faz um tempinho) meus estudos para maratona de programação e tenho algumas dúvidas e gostaria muito que você me respondesse se possível.

    1. No geral, você acha interessante fazer as estruturas de dados em C ou usar as prontas do C++ (exemplo: vector, deque, sort). Eu sei que depende muito do problema mas gostaria de ler sua opinião.

    2. São tantos assuntos diferentes que fico perdido nos estudos, você direcionou seus estudos usando algum material de apoio?

    3. Para problemas de grafos no geral, quando é melhor usar matriz de adj e quando é melhor usar lista de adj ?

    4. Você possui algum link de uma implementação boa de dijkstra por lista de adj? Eu procurei mas não consegui encontrar direito uma boa para aprender…

    Muito obrigado!!

    1. Olá André,

      1. É importante ter uma noção de como as estruturas funcionam, pois uma vez ou outra você pode precisar implementá-la com uma pequena modificação, sem falar que só de conhecer essa estrutura você já ganha mais experiência em como resolver problemas em geral. Mas já faz algum tempo que eu não encontro um exercício que me forçe a implementar a estrutura em si, uma vez que as bibliotecas do C++ são bem robustas.

      2. Na minha própria experiência eu fui estudando os assuntos conforme precisava. Confesso que não sei qual a estratégia mais eficaz. Depende muito da pessoa.

      3. Na maioria dos exercícios de grafos que eu encontro é sempre mais vantajoso usar lista de adjacência, pois, dependendo do tipo de grafo (esparso ou não) e do algoritmo que você vai implementar, a lista ocupa menos espaço e tem melhor desempenho.
      Mas existem alguns casos em específico que matriz de adjacência é mais vantajoso. Por exemplo, se você precisa verificar constantemente se um determinado vértice entre U e V existe, você precisaria (1) verificar toda a lista de adjacência de U, que pode conter até N elementos; ou (2) simplesmente verificar se a posicão matriz[U][V] é igual a 1.
      Então você precisa analisar bem o (1) tipo de grafo, (2) tipo de algoritmo, e (3) tipo de operação que você pretende utilizar antes de escolher entre lista ou matriz.

      4. Dá uma olhada nessa implementação:
      http://zobayer.blogspot.co.uk/2009/12/dijkstras-algorithm-in-c.html

  6. Olá Cristhian,

    Aproveitando que você está resolvendo questões aleatórias, gostaria de pedir que resolvesse uma questão bem interessante que caiu na modalidade programação nível 1 da OBI desse ano: Jogo da Memória.

    Quando fiz a prova, utilizei uma busca em largura, e programação dinâmica para calcular a distância entre os vértices. Ainda assim, não consegui passar no tempo de alguns casos de testes, e recebi apenas metade da pontuação.

    Segue o link com o caderno de tarefas da OBI -> http://olimpiada.ic.unicamp.br/extras/provas/ProvaOBI2014_prog_f2n1.pdf

    Parabéns pelo blog e agradeço desde já!

    1. Olá Carlos,
      Interessante esse exercício. Ele é um exemplo bem clássico de um problema que pode ser resolvido com o algoritmo Lowest Common Ancestor (Menor Ancestral Comum). Vou ver se escrevo sobre ele no blog.
      Você sabe se já é possível submeter solucões destes exercícios da OBI deste ano em algum site?

  7. Olá, Cristhian. A solução para o problema “Dudu faz serviço” está correta? Fiz um código com base na solução apresentada e estou recebendo WA10%. Existe mais algum detalhe?

    1. Dá sim. O processo que eu citei é basicamente a operacão de atualizacão da árvore de segmentos, só esqueci de citar o nome.

  8. Legal Christian! Só uma sugestão, no 1696 (Brincando com Operadores), acho que não precisa percorrer a árvore lg[N+1] vezes. Você pode usar sua árvore (na verdade, não precisa montar ela) para saber se cada elemento afeta positivamente ou negativamente na soma final. Salvando a soma e o vetor de elementos, quando alterar um elemento é só alterar o (Novo valor-Valor antigo)*(Sinal) na soma. Aí daria O(1) para cada consulta.

    Acho que como o problema só altera um elemento por vez, montar uma árvore é matar formiga com canhão hehe. Mas ficou bem explicado, mandou bem! 🙂

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *