Topcoder: SRM 517

Já faz um tempo que ocorreu o SRM 517, mas só agora resolvi estudar a solução. No dia resolvi só problema mais fácil (250) e ainda errei um challenge :(

Neste post vou apresentar apenas a solução do problema médio, que estava mais difícil do que o normal, o que estava sugerido por sua pontuação (600 ao invés de 500).

Adjacent swaps

Descrição

Seja um vetor de N elementos v = {0, 1, 2, …, N-1} e uma permutação de p = {p[0], p[1], …, p[N-1]} de v. Definimos como troca-completa o conjunto das N-1 possíveis trocas entre elementos nas posições i e e i+1 (i variando de 0 a N-2) executadas exatamente uma vez, em uma ordem arbitrária.

O problema pede para encontrar quantas trocas-completas levam a v a p.

Solução

A primeira observação é que ao invés de considerar trocas-completas que levem v a p, consideramos aquelas que levam p a v. Existe uma bijeção entre uma troca-completa do problema original e do novo problema, que é simplesmente inverter a ordem das trocas e portanto a resposta é a mesma para os dois problemas.

A solução proposta no editorial é resolver esse problema através de programação dinâmica. Para tanto, definimos

u(i,j, k) — como o número de trocas-completas que ordenam o subvetor p[i…j] = {p[i], p[i+1] …, p[j]}, usando apenas as trocas entre elementos consecutivos entre i e j-1, com a restrição adicional de que a última troca efetuada seja entre k e k+1. (0 <= i <= k < j <= N-1).

Seja . A solução que estamos procurando é então t(0, N-1). Além do mais, para o caso base i=j, temos um vetor de um único elemento ordenado e já não resta movimentos, portanto, t(i,i) = 1 para i=0, N-1.

Vamos ver como podemos calcular u(i,j,k).

Seja q[i…j] o subvetor p[i…j] ordenado e q'[i..j] o subvetor q[i..j] antes de fazer a troca entre k e k+1. Assim, q'[k] = q[k+1] e q'[k+1] = q[k], ou seja q'[i…j] = {q[i], q[i+1], …, q[k-1], q[k+1], q[k], q[k+2], …, q[j]}.

Observação 1: (q[i] < q[i+1] < … q[k-1] < q[k+1]) e (q[k] < q[k+2] < … < q[j]).

Por definição, q[i…j] e q'[i…j] são permutações de p[i..j]. Isso implica que todo elemento de q'[i…k] pertence a p[i…k] ou p[k+1…j]. Porém, como por hipótese a troca k,k+1 não foi feita ainda, um elemento de q'[i…k] não pode ter vindo de p[k+1…j]. Logo, concluímos que q'[i…k] deve ser uma permutação de p[i…k]. Temos assim duas condições a serem satisfeitas:

Condição 1: O subvetor p[i…k] deve ser uma permutação de q'[i…k].

Condição 2: O subvetor p[k+1…j] deve ser uma permutação de q'[k+1…j].

Na verdade podemos mostrar que as condições 1 e 2 são equivalentes. Supondo que as condições são satisfeitas, pela Observação 1, temos que q'[i…k] está ordenado, logo q'[i…k] = q[i…k], que é uma ordenação de p[i…k]. É possível argumentar o mesmo para q'[k+1…j] e p[k+1…j].

Por definição, t(i,k) conta o número de trocas-completas que leva p[i…k] em q[i…k] (o mesmo para t(k+1,j)). Assim, a princípio poderíamos combinar cada troca-completa em t(i,k) com cada troca-completa em t(k+1,j), levando à recorrência u(i, j, k) = t(i, k)*t(k+1, j).

Entretanto, há um número bem maior de combinações. Considere uma dada troca-completa A de t(i,k) e outra B de t(k+1, j). Embora a ordem das trocas em A e em B sejam fixas, não há restrição de ordem entre uma troca feita em A e outra feita em B. Por exemplo, poderíamos fazer todas as trocas de A primeiro e depois todas as de B ou qualquer combinação de intercalação entre os elementos de A e B.

Podemos mostrar que o número total de intercalações possíveis é dada por um coeficiente binomial C(n,r). No nosso caso em particular, n é o número total de trocas disponíveis, ou seja, j-i-1 (k-i de A e j-(k+1) de B) e r é o número de trocas em A (ou em B), ou seja, C(j-i-1, k-i). Para ver o porquê, considere que temos posições de 1 a j-i-1. Queremos escolher k-i dessas posições para atribuir a elementos de A e o restante das posições fica para B. Agora basta pensarmos nessas posições como a ordem em que as trocas são efetuadas.

Isso dá a recorrência

u(i, j, k) = t(i, k)*t(k+1, j)*C(j-i-1, k-i)

No caso de as condições 1 e 2 não serem satisfeitas, u(i, j, k) = 0.

Podemos usar a recorrência C(n,r) = C(n-1, r-1) + C(n-1, r) para pré-computar os valores dos coeficiente binomiais em . Também podemos pré-computar se para uma dada tripla i, j, k, as condições 1 e 2 serão satisfeitas, em (usando ordenação linear para encontrar q).

Dado isso, podemos computar cada u(i, j, k) em e cada t(i, j) m . A complexidade total das recorrências fica , que também é a complexidade total do algoritmo.

Decidi colocar minhas implementações de SRM’s também no github.

Conclusão

Achei a solução desse problema bastante complicada e como de costume fiquei surpreso de tanta gente ter conseguido resolvê-lo durante os 75 minutos de competição.

Programação dinâmica é uma técnica que eu acho difícil aprender, porque em geral não consigo encontrar uma estrutura no problema que me indique a forma de atacá-lo. Minha esperança é continuar estudando suas aplicações e quem sabe aprender por “osmose” :P

O uso do coeficiente binomial para contar intercalações é bem engenhoso! Lembro que alguma outra vez estudei um problema em que a contagem por coeficiente binomial também não era trivial de ver.

Visualização ótima de desenhos fisicamente realizáveis

Hoje vou descrever o trabalho que apresentei no Sibgrapi 2011, entitulado “Determining an Optimal Visualization of Physically Realizable Symbol Maps“, escrito em conjunto com meus orientadores (professores Pedro e Cid) e o professor Tallys da Universidade de Miami. Há um

Trata-se de uma extensão do estudo que realizamos para o problema de mapas de símbolos proporcionais usando desenhos em pilha, sobre o qual comentei em um post anterior.

Desenho fisicamente realizável

Um desenho fisicamente realizável é uma generalização de um desenho em pilha, pois este permite ordens cíclicas, como no exemplo abaixo.

Desenho fisicamente realizável e desenho em pilha

Podemos pensar que desenhos fisicamente realizáveis são aqueles feitos a partir de discos de papel, desde que estes não sejam dobrados nem cortados.

O problema é encontrar um desenho fisicamente realizável que maximize a soma dos comprimentos das bordas visíveis. Esse problema é chamado Max-Total para desenhos fisicamente realizáveis.

Tínhamos desenvolvido um modelo de programação linear inteira para o problema Max-Total para desenhos em pilha e mostramos que um subconjunto das desigualdades desse modelo, resolvia o problema Max-Total para desenhos fisicamente realizáveis.

Discutimos aspectos teóricos sobre as desigualdades utilizadas no modelo, argumentando que elas tornam a formulação apertada. Na prática um modelo com formulação apertada tende a ser resolvido mais rapidamente pelo algoritmo de branch and bound.

Técnica de decomposição

Desenvolvemos uma técnica de decomposição nova, que só serve para esse tipo de desenho. A ideia básica das decomposições é quebrar o conjunto de discos de entrada em componentes menores e mostrar que podemos resolver a cada componente de maneira independente e então combiná-las em tempo polinomial para gerar a solução ótima da instância completa. Uma decomposição óbvia é considerar conjuntos de discos disjuntos no plano.

Para desenhos fisicamente realizáveis, podemos ignorar a interseção de discos em alguns casos. Isso por sua vez pode gerar novas componentes disjuntas. No exemplo abaixo, mostramos que é possível ignorar a interseção dos discos nas faces amarelas. Isso quebra a componente em duas que podem ser resolvidas isoladamente.

Exemplo de decomposição

Junto com as outras decomposições que já havíamos desenvolvido para desenhos em pilha, conseguimos diminuir o tamanho das instâncias de teste.

Resultados computacionais

Após resolvermos a formulação do problema para desenhos fisicamente realizáveis, constatamos que na grande maioria dos casos, o valor da solução era exatamente igual ao da solução para desenhos em pilha.

Mesmo para as instâncias onde houve diferença, esse valor foi muito pequeno e visualmente é muito difícil distinguir as soluções, conforme pode ser visto na figura a seguir.

Zoom de uma solução ótima usando desenho em pilha e desenho fisicamente realizável

Entretanto, também tivemos uma boa surpresa, que foi o tempo de execução desse novo modelo. Em média, ele foi aproximadamente 2 ordens de magnitude mais rápido do que modelo para desenhos fisicamente realizáveis.

Conclusão

Devido aos tempos obtidos com o novo modelo e o fato de as soluções obtidas serem muito próximas a desenhos em pilha, uma ideia é usarmos esse modelo para resolver o problema de desenhos em pilha, adicionando restrições para remover os eventuais ciclos que apareçam.

Podemos adicionar essas restrições de remoção de ciclo através de um algoritmo de planos de corte, de um modo similar ao usado para resolver o problema do caixeiro viajante.

Codefest 2011

Este final de semana ocorreu a primeira edição do Codefest. A ideia do programa promovido pela Conpec é a de aproximar empresas, que propõem desafios de ordem prática, e os alunos, que por sua vez devem resolvê-los com soluções inovadoras.

Foram definidos 5 temas, cada qual organizado por um empresa. Os integrantes da equipe vencedora de cada tema ganhariam um smartphone da motorola. A Buscapé, propôs o tema que achei mais interessante: um problema de otimização em grafo (não posso dar mais detalhes devido a um contrato de sigilo).

Juntei-me a mais alguns amigos da pós-graduação em otimização, além de um pós-graduando em reconhecimento de padrões fazendo pós na elétrica.

A descrição dos problemas foi divulgada há cerca de duas semanas. Na verdade a competição era para ter acontecido pelos idos de Agosto, mas houve um problema e a organização precisou adiar. Isso complicou a vida de alguns participantes como eu, que agora estou trabalhando 40h por semana.

Mesmo assim, consegui dedicar um bom tempo no problema, graças a um feriado e alguns finais de semana. Durante esse tempo, nossa equipe atacou o problema com diversas abordagens e acabamos optando pela que apresentou melhores resultados nas instâncias de testes.

Neste Sábado e Domingo houve uma etapa presencial no Instituto de Computação onde as equipes deveriam concluir seus projetos e apresentá-los. No caso do problema da Buscapé, tínhamos que submeter nosso programa a uma bateria de testes fechados.

Haviam apenas 2 concorrentes com o mesmo tema que nossa equipe. Infelizmente não ganhamos a competição :( Cometemos um erro técnico grave que teria sido facilmente evitado com boas práticas de programação, mais especificamente testes unitários. Além disso, focamos muito na solução do problema e pouco na apresentação da mesma.

Fiquei chateado pelo fato de ter me esforçado tanto e uma bobeirinha ter estragado todo o trabalho, mas são coisas que acontecem e o melhor que dá pra fazer é tentar aprender com os erros :)

Conclusão

No geral, achei a iniciativa muito bacana e espero que seja repetida nos próximos anos (embora eu não possa mais participar). Houve alguns problemas de organização, mas totalmente compreensíveis dado que é a primeira vez que essa competição é realizada.

Também achei legal que vieram pessoas de fora (tinha até equipe de Natal) e de outros cursos (por exemplo mecatrônica). Seria muito bom ver a competição atingir abrangência nacional, ou mesmo que outras Universidades copiassem o modelo e realizasse competições locais.

As empresas deveriam ser as mais interessadas nisso já que, além de agregar ideias que possam evoluir para produtos, é uma forma eficaz de garimpar talentos.

Não tinha me dado conta, mas essa competição foi exatamente o que eu gostaria que a arena MTE fosse quando participei em 2010.

Google Summer of Code – Conclusões

Essa semana chegou o certificado de conclusão do Google Summer of Code, indicando que completei o programa com sucesso :) Também mandaram uma camiseta de brinde.

Camiseta do Google Summer of Code

Dicas para quem deseja participar

Eu já havia tentado participar no google summer of code em 2009 e 2010, pelas organizações Scilab e CGAL, respectivamente, mas sem sucesso.

O que eu fiz de diferente para ser aceito em 2011? Conversei com os mentores antes de enviar minha proposta.

Além de demonstrar interesse, as conversas permitem que o instrutor avalie suas habilidades necessárias para cumprir o projeto. No meu caso por exemplo, tive que implementar um patch para corrigir um bug.

A seguir algumas dicas quanto à escolha do projeto e da organização.

Escolha do Projeto

Uma coisa importante é a escolha do projeto. Há diversos pontos que devem ser considerados na escolha do projeto, entre eles: concorrência, relevância, dificuldade e motivação.

Provavelmente projetos relacionados a jogos são bastante concorridos, mas no geral não sei o que atrai mais os candidatos. Tem que acompanhar as listas de discussão e ver quais projetos estão sendo mais procurados. Minha dica fica em optar por projetos menos concorridos.

Uma organização em geral oferece diversos projetos, mas alguns têm maior prioridade do que outros. Se houver duas propostas igualmente boas e a organização tiver que escolher apenas uma, ela provavelmente optará pelo projeto de maior relavância. Algumas organizações explicitam a relavância do projeto nas descrições dos mesmos, mas vale conversar com os mentores para entender qual é o impacto do projeto para a organização.

Escolher a dificuldade adequada do projeto é complicado. Por um lado projetos muito fáceis tender a ser ou pouco relevantes ou muito chatos (do contrário provavelmente alguém já teria se disposto a fazê-lo voluntariamente). Projetos muito difíceis podem minar suas possibilidades de completar o programa e também torna mais difícil convencer o mentor que você é capaz de fazê-lo. Eu recomendaria então projetos de dificuldade média.

Finalmente, é preciso escolher um projeto que te motive. Isso não afeta muito suas chances de ser aceito, mas sim a de conseguir completar o programa. No meu caso, eu tinha bastante interesse em raytracers, por isso procurei projetos dentro desse tópico.

Escolha da Organização

A escolha da organização é bastante relevante. Querendo ou não, algumas organizações terão mentores mais atenciosos do que outras. Da minha experiência com Scilab, CGAL e BRL-CAD, posso dizer que Scilab e BRL-CAD têm mentores bastante acessíveis. No CGAL eu tive uma experiência ruim com trocas de emails, pois nenhum email meu relativo ao GSoC foi respondido.

Minha dica aqui é escolher organizações que tenham algum projeto que te agrade e começar a troca de emails. Com isso dará para ter uma ideia de quão prestativos são os mentores.

Habilidades necessárias

Considero importante as seguintes habilidades/conhecimentos para aumentar as chances de concluir o projeto:

– Ter compilado algum projeto open-source a partir do código-fonte, passando por todo o tormento de instalar dependências (mesmo quando não estão acessíveis via um “apt-get install” :P).

– Saber se virar sozinho. Ir atrás de tutoriais, documentação, fuçar código, etc.

– É bom conhecer a linguagem de programação que será usada no projeto, mas talvez não seja algo tão estrito se você tiver alguma base. Por exemplo, se tiver conhecimento em orientação de objeto, dá pra se virar tanto em C++ quanto em Java, por exemplo. O BRL-CAD teve um projeto em Tcl, mas o estudante alocado não conhecia essa linguagem e mesmo assim concluiu o projeto com sucesso.

– Dependendo do projeto, o conhecimento exigido é tão complicado que somente pessoas que trabalharam com isso vão conseguir realizá-lo. Por outro lado, há temas fáceis de serem aprendidos, pelo menos o básico, como por exemplo raytracing.

Conclusão

Aprendizado

Trabalhar com projeto open-source incrementa o aprendizado nas diversas ferramentas utilizadas, no tema do projeto, em práticas de programação, etc. Porém, na minha opinião, o maior benefício é a familiaridade que se adquire em trabalhar com código grande escrito por muitas mãos.

Lembro que nas minhas primeiras tentativas de mexer com código open-source (se não me engano foi com o Blender), eu desanimei muito rapidamente pois tinha dificuldade em entender o que o código fazia. Já recentemente, peguei um projeto com código mal comentado e mesmo assim consegui entendê-lo relativamente bem.

Não acredito que minha capacidade de entender código melhorou muito, mas é o costume com esse processo, por vezes tedioso e demorado, que te leva a perseverar e não desanimar tão facilmente.

Continuidade do projeto

Conforme mencionei em um post anterior, eu queria continuar trabalhando nesse projeto, mas até agora não tem sobrado muito tempo para isso. Vamos ver se até o final do ano faço alguma coisa.

Maven

Uma ferramenta que conheci recentemente é o apache maven, que serve para gerenciar projetos java, como por exemplo compilar código java, gerar documentação, fazer deploy de aplicações web etc.

O objetivo desse post é cobrir os principais conceitos dessa ferramenta, apontando referências para quem quiser se aprofundar mais. Me baseei na versão mais recente do maven, o maven 3 (versão 3.0.3 mais especificamente).

O arquivo pom.xml

O maven usa um arquivo de configuração chamado Project Object Model (POM) para determinar as características do projeto e suas dependências.

Maven usa o paradigma de convenção ao invés de configuração. Isso quer dizer que, a menos que explicitado de outra forma, ele supõe configurações padrões (como por exemplo a localização dos códigos-fontes), o que permite que o arquivo pom.xml fique bem pequeno.

Um exemplo de um arquivo pom.xml é o seguinte:

<project>
  <modelVersion>4.0.0</modelVersion>
  <groupId>br.com.organizacao</groupId>
  <artifactId>teste</artifactId>
  <version>1.0-SNAPSHOT</version>
  <packaging>jar</packaging>
</project>

No exemplo acima, modelVersion define a versão da estrutura POM utilizada e a versão atualmente usada pelo maven é a 4.0.0. Segundo o blog da Caelum [2], os seguintes parâmetros são suficientes para identificar unicamente um projeto:

• groupId – um identificador da empresa/grupo ao qual o projeto pertence. Geralmente o nome do site da empresa/grupo ao contrário;
• artifactId – o nome do projeto;
• version – a versão atual do projeto (PS: o modificador SNAPSHOT indica que essa versão é de desenvolvimento);

Além disso, no livro Maven By Example [1], eles definem o conceito de coordenadas maven, que é um conjunto de informações utilizadas para se referir a um projeto. Além das três propriedades acima, inclue-se o parâmetro packaging, que definirá se o pacote será comprimido em um jar, war, ear, etc. Dessa forma, o projeto acima seria referido por: br.com.organizacao:teste:jar:1.0-SNAPSHOT.

O maven implementa um mecanismo de herança. Isso quer dizer que um dado POM herda as configurações de seus ancestrais podendo sobrescrevê-las. Existe um POM que é ancestral de todos os POMs, o chamado super POM, de onde se herdam as configurações padrões.

Outro mecanismo é o de agregação, onde um POM principal pode definir módulos (sub-projetos) associados a outros POMs, que serão chamados pelo POM principal. Em [4], há um tópico detalhando e fornecendo exemplos para esses mecanismos.

Plugins

Se formos ver, o tamanho do maven é bem pequeno. Isso porque a maioria de suas funcionalidades é provida através de plugins. Um plugin consiste basicamente de uma coleção de goals. A sintaxe para executar um goal é

$mvn <plugin>:<goal>

Um exemplo é o plugin compiler, que possui o goal compile. Esse goal compila o código java e pode ser invocado da seguinte maneira:

$mvn compiler:compile

Repositório central do maven

Tanto os plugins quanto as bibliotecas mais comuns são mantidas em um repositório remoto central, chamado Maven Central Repository. Quando há uma dependência, quer de um plugin ou de uma biblioteca, o maven consulta esse repositório e cuida de fazer o download automaticamente.

Os objetos baixados são armazenados em um repositório local, que fica geralmente no diretório ~/.m2. Quando fazemos o build de um projeto nosso com o maven, ele também é copiado para esse diretório.

Ciclo de Vida do Build

O maven utiliza o conceito de ciclos de vida, que são compostos por uma sequência ordenada de fases. Há três ciclos de vida pré-existentes no maven: clean, default e site. O ciclo de vida default é composto pela sequência de fases: validate, compile, test, package, integration-test, verify, install, deploy (na verdade essa sequência está simplificada – a lista completa está nessa referência). Essas fases são sempre executadas nessa ordem. Assim, se executarmos a fase

$mvn install

Todas as fases que são anteriores a install serão executadas. Se quisermos executar o ciclo de vida default completo, basta executar a última fase, que é o deploy.

Na verdade uma fase não é executada, mas sim os goals associados a elas. Alguns goals já vêm associados por padrão a algumas fases. Por exemplo, ao declararmos o tipo de packaging como jar, o goal compiler:compile é associado à fase compile do ciclo de vida default. Para saber quais goals estão associados a quais fases por padrão, consulte essa referência.

Podemos associar mais goals às fases de build especificando no próprio arquivo pom.xml. Em [5], supõe-se a existência de um plugin chamado display-maven-plugin, que tem o goal time, que imprime o horário atual na saída padrão. Se quisermos imprimir o horário após a fase de testes terem sido executados, podemos associar esse goal à fase test, como no exemplo a seguir:

...
 <plugin>
   <groupId>com.mycompany.example</groupId>
   <artifactId>display-maven-plugin</artifactId>
   <version>1.0</version>
   <executions>
     <execution>
       <phase>test</phase>
       <goals>
         <goal>time</goal>
       </goals>
     </execution>
   </executions>
 </plugin>
...

Note que os conceitos de ciclos de vida e fases são uma maneira de organizar os diversos goals usados no processo de build. Em teoria poderíamos especificá-los explicitamente e estes seriam executados na ordem em que foram passados à linha de comando.

Plugin para o eclipse

Finalmente, para quem usa eclipse, existe um plugin para integração com o maven. A versão do eclipse que estou usando é a 3.7 (Indigo) e o plugin é o m2eclipse.

Para instalar o plugin, vá em Help > Install New Software…

Na barra de endereços coloque: http://download.eclipse.org/technology/m2e/releases

Selecione o item Maven Integration For Eclipse e siga as instruções até concluir a instalação. Algumas funcionalidades que esse plugin oferece são:

Importar um projeto que usa maven, no eclipse. O plugin utiliza informações do pom.xml para isso. Depois de instalado o plugin, vá em:

File > Import… > Maven > Existing Maven Projects

Dê Next, preencha o campo Root directory e então Finish. Pronto, o projeto deve ter sido importado.

Uma alternativa é usar o plugin do próprio maven, o eclipse, para gerar os .classpath e .project. Para isso basta fazer

mvn eclipse:eclipse

Depois é só importar o projeto no eclipse (General > Existing Projects into Workspace).

Fazer o build do projeto dentro do eclipse.

Figura 1: fases do maven providas pelo plugin m2e

Há algumas fases pré-existentes providas pelo plugin, como as da Figura 1. Entretanto, se quisermos personalizar o build, basta ir em:

Run > Run As… > Maven build…

Podemos configurar o build do maven, ajustando os goals ou fases (e.g. clean, package, install, compiler:compile) e definindo opções como modo offline (opção -o), pular testes (opção -Dmaven.test.skip=true), etc.

Para um tutorial mais completo, refira-se a [3], que trata de assuntos como a criação de projetos usando o plugin archetype do maven, importação de projetos (inclusive via checkout de um repositório remoto), etc.

Leitura adicional

[1] Livro Maven by Example
[2] Processo de build com o Maven
[3] Introduction to m2eclipse
[4] Introduction to the POM
[5]Introduction to the Lifecycle