Aquecimento para a OBI Fase 2 – Editorial

Neste dia 9 de agosto, o pessoal do portal URI Online Judge organizou um contest visando “aquecer” os maratonistas antes da Olimpíada Brasileira de Informática. Este aquecimento contou com vários exercícios originais, escritos pelo Neilor Tonin, Leandro Zatesko, Marcelo Cezar, Lucas Negri e eu.

A lista de problemas e o ranking do contest pode ser visualizado neste link:
https://www.urionlinejudge.com.br/judge/pt/challenges/index/9

Clique abaixo para ler um editorial escrito por mim.

A – Matrizes de Quadrados – [uri]

O maior desafio deste exercício está na formatação da saída, onde deve-se calcular a distância entre cada número e à margem esquerda da coluna.

Declare um vetor maior, e salve na posicão maior[i] o maior número da coluna i. Quando for imprimir cada valor da matriz, calcule a diferença de dígitos entre o valor atual e o valor da posição maior[i]. Seja D essa diferença, imprima D espaços em branco antes do valor atual.

Para descobrir o número de dígitos de um valor é possível utilizar a função log10, da biblioteca “math.h”. Por exemplo:

#include <stdio.h>
...
int num_digitos;

// a função log10 não funciona bem com o valor 0.
if(maior[i] > 0) {
    num_digitos = (int)log10(maior[i])+1;
} else {
    num_digitos = 1;
}
B – Transporte de Painéis Solares – [uri]

Um detalhe importante a ser notado neste exercício é que o transporte dos painéis deve ser “feito na sequência correta, que é exatamente a sequência na qual eles aparecem na entrada”.

Isto reduz drasticamente o número de possíveis combinações, e nos permite aplicar algumas estratégias para resolver o exercício. Vou apresentar aqui uma solução por ProgramaCão Dinâmica.

Seja dp[i][j] o peso do caminhão com a maior soma de painéis, se os painéis forem divididos de maneira ótima entre os caminhões entre i e num_caminhões, que vão carregar os painéis entre j e num_painéis.

Para calcular dp[i][j], escolha um valor k entre j e num_painéis, simbolizando que o caminhão i vai carregar todos os painéis entre j e k, inclusive. O objetivo é que o máximo entre a soma dos painéis entre i e j, inclusive, e o valor de dp[i+1][k+1], seja o mínimo possível.
Ou seja:

dp[i][j] = min{ max(dp[i+1][k+1], soma_peso(j, k)) },
para todo k entre j e num_painéis, inclusive,
onde soma_peso(j, k) retorna a soma dos pesos dos painéis entre j e k, inclusve.

C – Quid Est Veritas? Est Vir Qui Adest! – [uri]

Este título um tanto inusitado escrito em latim (segundo o Google Tradutor), esconde um problema de combinatória.

O número de possíveis permutações de N elementos é N!, porém como há elementos repetidos algumas permutações se repetem.

Seja N o número total de elementos, e elemento[i] o número de vezes que o elemento i se repete, a fórmula final da solucão é:
N! / (elemento[1]! * elemento[2]! * … * elemento[26]!).

Como o resultado pode ficar muito grande, o exercício pede para que seja impresso o resultado em resto de divisão por 10⁹+7. Para os javarianos é possível usar a biblioteca BigInteger e aplicar a fórmula, mas para os adeptos de C/C++ essa tarefa fica um pouco mais interessante.

Seja Num = N!, Den = elemento[1]! * … * elemento[26]!, e Mod = 10⁹+7.
Se Num > Mod ou Den > Mod, a fórmula citada, (Num%Mod)/(Den%Mod), não vai nos trazer a resposta correta (teste!). Quando quisermos dividir um número que passou pela operação de resto de divisão devemos, em vez de dividir por Den, multiplicar pelo inverso modular de Den.

Pesquisem mais a respeito de inverso modular:
http://marathoncode.blogspot.com.br/2012/04/inverso-multiplicativo.html

D – Conversa Internacional – [uri]

Este exercício baseado em uma história real pode ser facilmente resolvido elegendo um idioma “representante”, e verificando se todos os outros idiomas são o mesmo que este.

Se sim, imprima este idioma “representante”. Senão, imprima “ingles”.

E – O Teorema de Pitágoras – [uri]

A soluCão pode ser dividida em duas partes: descobrir se a tripla é pitagórica; e se sim, descobrir se é primitiva.

Para descobrir se a tripla é pitagórica, basta testar todas as combinaCões para valores de hipotenusa e catetos. Ou seja, teste se X² = Y²+Z², ou Y² = X²+Z², ou Z² = X²+Y².

Por fim, para descobrir se a tripla é primitiva, como o próprio enunciado diz, basta descobrir se mdc(X, Y, Z) = 1. Para descobrir isso podemos aplicar três vezes algoritmo de Euclides:

// algoritmo de Euclides,
// retorna o maior divisor comum entre a e b.
int mdc(int a, int b) {
    if(a == 1 or b == 1) return 1;
    if(b > a) {
        int aux = a; a = b; b = aux;
    }

    while(b) {
        int c = a%b;
        a = b;
        b = c;
    }

    return a;
}
F – Contaminação – [uri]

Este é um exemplo clássico de exercício que pode ser resolvido pelo conceito de Flood Fill.

Visite todas as células que inicialmente estão contaminadas. Para cada uma destas células, visite as quatro células adjacentes a ela no mapa, e infecte todas estas que forem do tipo Água. Repita o processo para cada célula Água infectada.

Ao final apenas imprima o mapa resultante.

// o vetor dir guarda todas as 4 direcoes adjacentes
const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

// o vetor visi garante que o algoritmo não entre em um loop infinito
bool visi[64][64];

void flood(int a, int b) {
    if(visi[a][b]) return;
    visi[a][b] = true;
    matriz[a][b] = contaminante;
 
    for(int i=0; i<4; i++) {
        int na = a+dir[i][0];
        int nb = b+dir[i][1];
 
        if(na >= 0 and na < n and nb >= 0 and nb < m
        and (matriz[na][nb] == contaminante or matriz[na][nb] == agua)) {
            flood(na, nb);
        }
    }
}
G – Espertofone – [uri]

Seja G o grafo simples definido por:

  • V (G) é o conjunto das posições do grid, numeradas de 1 a N²;
  • existe a aresta uv se e somente se é possível ir do botão u ao botão v sem passar pelo centro de nenhum botão intermediário.

Sejam u e v vértices quaisquer, e seja Suv(K) o número de passeios que começam em u e terminam em v com exatas K arestas. Um fato muito conhecido da Teoria dos Grafos é que Suv(K) é exatamente o valor da célula uv na matriz de adjacências de G elevada à K-ésima potência. Para elevarmos a matriz à K-ésima potência fazendo apenas O(log K) multiplicações de matrizes, utilizamos exponenciação binária, tomando o cuidado de realizar todas as operações módulo P = 10⁹+7. O valor que devemos imprimir no final, evidentemente, é ∑u,v ∈V(G) Suv(K) (módulo P, claro).

Discutamos agora sobre como construímos o grafo. Sejam (i, j) e (ii, jj) duas posições distintas no grid N ×N . Independentemente de haver aresta entre os vértices correspondentes, a posição (ii, jj) bloqueia para a posição (i, j) todas as posições (ii +dif i , jj +dif j ), (ii +2dif i , jj + 2dif j ), (ii + 3dif i , jj + 3dif j ), . . . , sendo dif i = ii − i e dif j = jj − j, enquanto essas posições estiverem dentro do grid. Como N é pequeno (no máximo 5), vemos, para cada (i, j), quais as posições que cada (ii, jj) bloqueia — ao final, os vizinhos de (i, j) no grafo serão as posições que não terão sido bloqueadas.

Dê uma olhada no código em cc.uffs.edu.br.

Fonte: Caderno de Problemas – 3a Maratona de Programação UFFS

H – Fazendo Pandorgas – [uri]

Basta descobrir como calcular a área de um losango, e imprimir tal valor (google it).

I – Cabo de Guerra – [uri]

Um insight importante para se resolver este exercício é que: tenha-se escolhido um estudante E para dividir as equipes, se a equipe A ficar com menos força deveríamos escolher um estudante à direita de E; e se a equipe B ficar com menos força deveríamos escolher um estudante à esquerda de E.

Isso nos lembra um algoritmo muito famoso chamado Busca Binária. Escolha um estudante E bem no meio da lista (índice N/2). Dependendo da soma das forças, escolha outro estudante no meio da lista da esquerda ou direita. Repita este processo até encontrar o estudante certo, ou até descobrir que não há solução.

J – BIT Park – [uri]

Este é, a princípio, um problema de simulação. Memorizamos em dois vetores xA e xB as posições dos jogadores, atualizando-as à medida que os eventos vão ocorrendo. Mantemos também uma flag impedimento, inicialmente 0, segundo a qual contabilizaremos ou não os gols. Dessarte:

  • Se um evento é I Xi ou P Xi, tudo o que precisamos fazer é contar o número de jogadores adversários que estão mais próximos do gol adversário que o jogador Xi. Se este número for estritamente menor que N /11, setamos impedimento para 1. Para sermos econômicos, apenas fazemos esta conta se impedimento é 0.
  • Se um evento é M Xi x, atualizamos as informações acerca da posição do jogador Xi.
  • Se um evento é G e impedimento = 0, apenas setamos impedimento para 1 (sempre que a bola sai, a flag deve ser ressetada); senão, contabilizamos o gol.
  • Se um evento é S, apenas ressetamos impedimento.

Como fazer, entretanto, para contar o número de jogadores adversários que estão mais próximos do gol adversário que o jogador Xi? Se optássemos por simplesmente varrer todo o vetor das posições dos jogadores adversários, teríamos uma complexidade total O(N E), mas N E no pior caso pode ser 2 551 804 · 10 5 > 10 11 , e precisaríamos de (muito) mais de 100 segundos para computar a resposta. Outra abordagem seria, para cada time, armazenar num vetor com 2 000 001 posições a quantidade de jogadores daquele time presentes em cada linha paralela. Porém, isso nos traria uma complexidade O(N + 2 000 000E) e não nos livraria da ordem de grandeza 10 11 . Para uma solução que seja aceita, o jeito é usar uma estrutura de dados eficiente, e o próprio problema já sugere qual: BIT (Binary Indexed Tree).

Usamos, então, duas BITs, uma para o time A e outra para o time B. Cada BIT armazena as frequências das distâncias dos jogadores do respectivo time até a linha do gol do mesmo time. No entanto, como essas distâncias podem ser 0, somamo-las com 1; assim, as distâncias não vão de 0 a 2 000 000, mas de 1 a 2 000 001. Para obtermos a distância (incrementada) de um jogador do time A que se encontra na posição x até a linha do gol do time A, basta fazermos x + 1. Para obtermos a distância (incrementada) de um jogador do time B que se encontra na posição x até a linha do gol do time B, basta fazermos 2 000 001 − x.

Deste modo, para sabermos quantos jogadores do time B estão mais próximos do gol do time B que um jogador do time A na posição x, basta  obtermos a frequência acumulada de (2 000 001−x)−1 na BIT do time B. Analogamente, para sabermos quantos jogadores do time A estão mais próximos do gol do time A que um jogador do time B na posição x, basta obtermos a frequência acumulada de (x + 1) − 1 na BIT do time A. Confira o código em cc.uffs.edu.br.

Fonte: Caderno de Problemas – 3a Maratona de Programação UFFS

 

Qualquer sugestão, dúvida ou comentário, usem a caixa de comentários abaixo. Até mais.

21 ideias sobre “Aquecimento para a OBI Fase 2 – Editorial”

  1. O exercício B também pode ser resolvido com busca binária, em que o seu “chute” é o “maior menor valor” que um caminhão leva. 🙂

  2. A ideia de se calcular o fatorial com big numbers é extremamente prática, mas o tempo de processamento da solução aumenta com o número de dígitos. Como a entrada poderia ser muito grande e me tomar 20 minutos de penalidade, usei o inverso multiplicativo. Uma alternativa mais rápida, ainda em Java, é o método modInverse() da classe BigInteger.

      1. Jadson, tudo bem? A penalidade se aplica somente aos problemas resolvidos pelo competidor no contest. Ou seja, é uma aposta: se a solução passar, você ganha um balão, se não passar, você não perde nada (a não ser que resolva o problema na próxima tentativa, recebendo os 20 minutos de penalidade).

  3. No problema C eu tentei uma abordagem diferente: Faço a fatoração de todos os números fatoriais que aparecem em números primos de todos . Utilizo a seguinte propriedade: (2^(a_0) * 3^(a_1) * 5^(a_2) … )/ ( 2^(b_0) * 3^(b_1) * 5^(b_2) … ), então esse valor pode ser representado por: (2^(a_0 – b_0) * 3^(a_1 – b_1) * 5^(a_2 – b_2) … ). Ai faço a multiplicação de todos os números primos usando exponenciação rápida (log n). Recebi várias respostas erradas, mas ainda não consegui encontrar o bug :

    1. Wyllian, boa noite. Você considerou que se a0 < b0 para algum fator o expoente será negativo, causando uma divisão implícita?

        1. Boa noite Wyllian, se a fatoração foi feita corretamente, nunca que a0 < b0, dado que o resultado pedido é sempre um inteiro. Você pode confirmar erros de contagem usando o seguinte comando em C++:

          vector v = fatora(x); // v[i] para todo i = 0, 2, 4, … guarda um fator primo distinto e v[i + 1] guarda seu expoente
          long long y = 1;
          for (int i = 0; i < v.length(); i += 2)
          __y = (y * modPot(v[i], v[i + 1])) % 1000000007;
          assert(x == y);

          1. Boa noite Altamir, muito obrigado pela ajuda! Infelizmente não consegui resolver o problema.. fiz testes com a fatoração e pareceu ok.

            Bom vou deixar meu código disponível aqui (http://ideone.com/SNZ9aQ) tá recebendo 10% de WA no URI. Vou deixar pra resolver quando disponibilizarem o toolkit 😛

    2. Atualização: Consegui encontrar o que estava errado no código. O contador de frequências eu tinha declarado como char, sendo que deveria ser int. Portanto essa estratégia que utilizei está correta.

      @Cristhian, não sei se devo deixar um código completamente funcional aqui. Qualquer coisa, pode apagar sem problemas :p. Abraços.

  4. Matriz de Quadrados:

    Estou recebendo “Presentation error” no exercício 1578, poderia me ajudar?

    #include
    #include

    unsigned char N, M, I = 4, A, B, Maior[20] = {0};
    unsigned long long int V[20][20];

    inline void clear(){
    for(A = 0; A 0; N–){
    scanf(“%hhd”, &M);

    for(A = 0; A < M; A++){
    for(B = 0; B < M; B++){
    scanf("%llu", &V[A][B]);
    V[A][B] *= V[A][B];
    if(V[Maior[B]][B] < V[A][B]) Maior[B] = A;
    }
    }

    for(A = 0; A 0 ? (int) log10 ((double) V[Maior[A]][A]) + 1 : 1;

    printf(“Quadrado da matriz #%hhd:n”, I++);

    for(A = 0; A < M; A++){
    for(B = 0; B < M; B++){
    printf("%*llu ", (int)Maior[B], V[A][B] );
    }
    printf("n");
    }
    }
    return 0;
    }

    1. Recomendo que você “limpe” o vetor Maior antes de cada caso de teste, caso contrário ele irá conter valores do caso de teste passado que podem acabar alterando o resultado do atual. Exemplo:
      2
      3
      5 5 5
      5 5 5
      5 5 5
      1
      1

      1. Faz todo o sentido, agora me recordo porque criei aquela função inline do primeiro código que postei, só esqueci de chama-lá. Mas agora funcionou, e levou 0.008s

  5. Olá, primeiramente, parabéns pelo blog!
    Olha, no problema F, eu acredito que você trocou algumas variáveis. Vide a linha:
    if(na >= 0 and na = 0 and nb < m
    no caso, N e M são A e B, respectivamente.

    abs,

    1. Olá Miguel, obrigado pelo suporte e pelo comentário.

      Acredito que o código está correto sim, talvez você não tenha entendido o objetivo das variáveis.
      – A e B são as coordenadas da posicão atual; N e M são as dimensões da matriz; e NA e NB são coordenadas temporárias que se referem às posicões adjacentes à posicão [A, B].
      – O que aquela condicão verifica é se as posicões adjacentes à atual estão dentro dos limites (entre 0 e N, e entre 0 e M), e se são posicões com água ou contaminada.

      Se ainda sobrarem dúvidas ou você encontrar algum outro erro, sinta-se a vontade para comentar 🙂

  6. Olá, boa tarde!

    Parabéns pelo blog, tenho aprendido bastante com seus posts, muito bom mesmo! Seguinte, no exercício B (Transporte de Paineis Solares) como devem ser feitas as distribuições iniciais dos paineis em cada caminhão? Pois, não entendi muito bem seu algoritmo. Obrigado!

    1. O problema como um todo é dividido em diversos sub-problemas, e cada sub-problema tenta dividir os painéis da melhor forma possível nos caminhões em questão. Eu recebi seu e-mail e o respondi com mais detalhes.

Deixe uma resposta

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