Blog de Helton Duarte

Olá pessoal!

Precisamos seguir nossos sonhos segundo a vontade de Deus! Apesar de estarmos com um comparecimento muito baixo (média de 2,5 pessoas por competição), nós não desistiremos, pois não podemos fazer pelos outros, mas também ninguém fará por nós, ou seja, cada um tem consciência do que precisa treinar caso queira algum dia ter um resultado melhor nessas competições. Novamente, fizemos uma prova em equipe, comparecendo somente 2 componentes da Absurdo Clássico e nada mais.

Mid-Atlantic Regional 2010

Como já foi dito aqui, as provas da América do Norte são muito boas para quem está começando a treinar, pois possuem um nível intermediário, ou seja, simula aproximadamente a primeira fase da Maratona de Programação aqui no Brasil. Essa prova possuía 8 questões e nosso desempenho foi um pouquinho melhor do que a passada, pois conseguimos resolver 4 questões em tempo de prova e mais 1 depois, totalizando 5/8 (cinco oitavos) da prova analisados para vocês.

• Problem A: Palindrometer

LA ID: 4868. Link: Palindrometer. Dificuldade (0 a 10): 2. Assunto: Matemática Básica.

Esse problema foi um dos mais fáceis da prova, senão o mais fácil. Ele consistia em encontrar qual era o menor palíndromo maior ou igual do que um número dado. Esse tarefa parece ser bem simples logo de cara, contudo pode se tornar traiçoeira caso você queira ir incrementando o número de 1 em 1 e verificando se ele tornou-se palíndromo, afinal temos limite de N < 10^10 e essa solução lhe daria um belo Time Limit Exceeded. Todavia, não se desespere! Que tal você seguir a ideia de gerar todos os palíndromos de antemão e depois só percorrer a lista e ver qual é o primeiro encontrado maior ou igual ao N dado? Como os números só podem ir até 9 dígitos, então um for simples até 10^4 geraria todos os palíndromos necessários (com casos especiais para uma quantidade ímpar de dígitos). Gostou da explicação? Mande suas dicas e dúvidas!

• Problem B: Balloons

LA ID: 4863. Link: Balloons. Dificuldade (0 a 10): 3. Assunto: Guloso.

Agora chegamos no segundo mais fácil. Um problema de otimização, ou seja, devemos procurar qual o menor valor que satisfaz determinada condição (muito comum em competições de programação). Nesse caso, ele gostaria de saber qual a menor distância a ser percorrida para entregar os balões em uma competição dada a necessidade de cada time e a distância para cada uma das salas (eram 2). Logo de cara, percebe-se que a ideia é gulosa, no entanto podemos cair na armadilha de pensar que o que deve ser observado é a menor distância para as salas, ou seja, ordenar os times pelo mínimo entre a distância para a sala A e a distância para a sala B. Pense em um contra-exemplo para essa ideia! Quase desistíamos de fazer o problema quando vimos que essa ideia falhava, mas percebemos que ainda era guloso, contudo deveríamos ordenar pela diferença entre as distância para as salas, ou seja, entrega primeiro para as equipes que possuem uma maior diferença entre as distâncias. Deu para entender ou a ideia ficou confusa? Leia mais sobre algoritmos gulosos e dê também a sua dica!

• Problem C: Selling Cells

LA ID: 4916. Link: Selling Cells. Dificuldade (0 a 10): ? Assunto: Geometria.

Não conseguimos fazer esse problema. Qualquer dica, nos envie um comentário.

• Problem D: Not One Bit More

LA ID: 4864. Link: Not One Bit More. Dificuldade (0 a 10): 5. Assunto: Matemática, Representação Binária.

Acredito que esse foi o problema que fiquei mais feliz em ter conseguido fazer! Graças a Deus, a ideia foi vindo de pouco em pouco (estávamos eu e Zailton fazendo juntos) e no final tínhamos uma bela resolução. Logo de cara, eu tenho medo de problemas que colocam limites muito altos, como o 10^18 que ele coloca, no entanto dá para perceber que esses limites são realmente para assustar. Como ele conta a quantidade de bits acesos, então em 1 passo o número estaria em, no máximo, 64, pois 10^18 < 2^64. Nesse caso, calculamos a função dada no problema para todos os valores até 64 e, depois fazíamos um for, chamando a nossa função para cada número que tivesse K = X – 1, sendo X o valor passado, pois iríamos calcular os números que em 1 passo chegaria no nosso teste (confuso né?). Nessa nossa função principal (que fazia praticamente todo o cálculo do problema) nós contávamos quantos números menores do que nosso parâmetro possuíam exatamente N bits acesos e deixamos como exercício para você pensar. Para cada chamada, a quantidade de números entre LO e HI com N bits acesos seria f(HI + 1) – f(LO), tratando apenas os casos em que aparece o número 1 na contagem… Será que você também consegue fazer? Tente e depois nos passe suas dúvidas e dicas!

• Problem E: Abstract Extract

LA ID: 4917. Link: Abstract Extract. Dificuldade (0 a 10): ? Assunto: ?

Não conseguimos fazer esse problema. Qualquer dica, nos envie um comentário.

• Problem F: Roller Coaster

LA ID: 4870. Link: Roller Coaster. Dificuldade (0 a 10): 5. Assunto: Programação Dinâmica.

Bem, e esse foi o problema que só conseguimos fazer depois de a competição ter terminado. Na verdade, fiz somente um pouco antes de escrever esse post. Ele é um problema bem interessante e essencial para quem quer se dar bem em competições e aprender algoritmo em si, pois envolve a técnica de Programação Dinâmica (PD), a qual não é trivial de se dominar. De início, havia pensado em uma PD sobre a seção e o enjôo (dizziness), maximizando a diversão que se conseguia, contudo vi que o limite de enjôo era 300.000, enquanto que o de diversão, embora não explicitado na questão, é calculado facilmente como sendo 20.000. Dessa forma, a PD mais tranquila para se fazer, na minha opinião, seria sobre a seção e a diversão alcançada, minimizando o enjôo, ou seja, teríamos uma “recursão” (mas na verdade é preciso fazer essa PD bottom-up, pois não há como armazenar a tabela como um todo, devendo armazenar apenas 2 linhas) em que d(i, j) seria o menor enjôo que poderia se conseguir ao chegar na seção “i” com uma diversão total de “j”, deu para entender? Pense um pouquinho em como implementar essa ideia de forma rápida e, qualquer coisa, mande-nos suas dúvidas!

• Problem G: Spy Cam

LA ID: 4918. Link: Spy Cam. Dificuldade (0 a 10): ? Assunto: ?

Não conseguimos fazer esse problema. Qualquer dica, nos envie um comentário.

• Problem H: Underground Cables

LA ID: 4872. Link: Underground Cables. Dificuldade (0 a 10): 3. Assunto: Grafos, Árvore Geradora Mínima.

Quando comecei a ler esse problema me animei, pois percebi logo que era uma clássica Árvore Geradora Mínima, todavia li um pouco depois “os cabos não podem se cruzar” e pensei: minha ideia foi por água abaixo! Como adaptar o algoritmo de MST para que não haja cruzamento de arestas? Simples: não precisa fazer nada! É possível ver intuitivamente (não tentei provar) que se houver um cruzamento, então haveria outra forma melhor de ter ligado essas arestas, já que o grafo aqui é um grid cartesiano. Portanto, esse problema é muito simples ao ser reduzido para um caso clássico de grafos. Não entendeu a explicação? Mande-nos sua dúvida!

Nessa competição, já pudemos utilizar o BOCA para simular o ambiente da Maratona de Programação e foi um sucesso! A partir de agora, tentaremos sempre utilizar o sistema, a fim de testarmos seu uso e nos acostumarmos mais com a situação. Espero que vocês tentem fazer a prova e obtenham um bom resultado!

Posts interessantes:

• North America – East Central Regional 2010
• Waterloo Contest 2009 – Fall 2
• Computação e Matemática
• Não é apenas o emprego dos sonhos!
• Programando Melhor

E você, tentou fazer a prova do Mid-Atlantic Regional 2010? Conseguiu fazer todas essas questões? Fez alguma das que não conseguimos? Deixe como comentário as suas dúvidas e as suas dicas!

Helton de Melo Duarte

“Purificando a vossa alma na obediência à verdade, para amor fraternal, não fingido, amai-vos ardentemente uns aos outros, com um coração puro” 1 Pe 1.22

This entry was posted on sexta-feira, julho 15th, 2011 at 15:38 and is filed under Treinamento Maratona - UFRN. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.