War story - Final ONI 2004

Nos posts anteriores, fiz a análise aos problemas das ONI 2004. Infelizmente, já não encontro online o link para os resultados da prova. Se bem me lembro, 22 dos 30 finalistas tiveram 0 pontos, eu incluído.

Pessoalmente, houve várias coisas que correram mal, descontando a óbvia falta de conhecimentos de algoritmos:

• Não tinha uma estratégia bem definida para atacar os problemas. 
• Estava a concorrer usando uma linguagem, Pascal, que tinha aprendido no ano anterior mas que usava pouco nessa altura, visto que no 11º usava essencialmente Visual Basic.
• O editor que sempre tinha usado para programar em Pascal, Turbo Pascal, não funcionava nos computadores da prova e tive de usar outro editor. Apesar de não ser muito grave, ainda perdi 30+ minutos já com a prova em curso para saber que editor poderia usar, como usar, como compilar, etc.

No fundo, tudo se resume a má preparação. Não se vai a um evento importante sem a devida preparação dos detalhes importantes.
A falta de experiência pode levar-nos a pensar coisas como "o Turbo Pascal tem de estar disponível, é o editor que sempre usei!", mas é importante aprender que tanto nos concursos como em todas as coisas coisas da vida, não devemos assumir nada, por mais evidente que possa parecer.

Durante a prova, fui deambulando de problema para problema e as 4h passam bem depressa para quem não tem uma ideia clara do que está a fazer!

No problema A, penso que na altura não compreendi bem o enunciado e tive dificuldades com os centros das quadrículas, não conseguindo determinar correctamente quais eram as quadrículas abrangidas pelas crateras.

Gastei a maior parte do meu tempo no problema B. Não tinha (ou não conhecia) um algoritmo eficiente na biblioteca standard do Pascal. Por isso tentei implementar um Quick Sort à mão e penso que não correu bem. Isto foi numa altura em que eu tentava memorizar a implementação de alguns algoritmos e despejar caso me lembrasse..

Penso que não ataquei muito o problema C. Provavelmente tentei alguma coisa mas penso que tive problemas com a geração recursiva dos números possíveis.

A prova acabou por correr bastante mal a toda a gente da minha escola. Para mim, valeu pela experiência e para aprender com os erros. Infelizmente, não tenho fotos desta prova.

A importância dos algoritmos para um engenheiro de software

Estou muito satisfeito por estar a ajudar a renovar as equipas que vão representar a FEUP nos concursos de programação da ACM. Há muitos alunos novos que estão a ver este "mundo" pela primeira vez e foi giro ver a sua reacção no concurso interno que fizemos esta semana :-)

No entanto, apesar deste interesse inicial dos alunos, uma pergunta natural é: porque é que isto é importante? Ou, por outras palavras, porque é que eles hão de despender parte do seu tempo livre a aprender mais sobre algoritmos, estruturas de dados e tudo o resto que está relacionado com os concursos?

Parte da resposta já foi dada noutros sítios. Neste post vou apenas realçar algumas das razões.
Eu sugiro a leitura do tutorial do TopCoder sobre a importância dos algoritmos e o artigo da Academia ONI sobre a análise de algoritmos.

Antes de mais.. o que é um algoritmo?
Um algoritmo pode ser definido como uma sequência de passos que transforma um dado input (um valor ou conjunto de valores) no resultado pretendido - output - sendo este tipicamente um valor ou conjunto de valores.
Na prática, um engenheiro de software gasta grande parte do seu tempo a implementar algoritmos. Para cada parte do projecto de desenvolvimento de software, existem um conjunto de desafios e é necessário definir qual vai ser a abordagem para os ultrapassar. Estes desafios podem ser coisas simples como ler um ficheiro de texto e apresentar a informação ao utilizador ou coisas mais avançadas como o processamento de giga, tera ou mais bytes de dados para determinar alguma estatística.

Análise do tempo de execução de algoritmos
Imaginem que têm este problema: dados N números inteiros, existem 2 números que somados dão um número S?
Uma solução natural é testar todos os pares de números e verificar se a sua soma dá S. Exemplo em C++:

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int soma) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == soma) return true; return false; }

O código é simples e tudo indica que dá a resposta certa. No entanto, um factor importante na vida real é saber se esta performance chega para as nossas necessidades. Qual é a quantidade máxima de números que este algoritmo suporta se o nosso programa tiver no máximo 1 segundo para executar?

Para responder a esta pergunta, é necessário analisar o tempo de execução do algoritmo apresentado. A notação mais popular para representar o tempo de execução (ou complexidade temporal) é a notação Ó-grande e é expressa em função do tamanho do input. Neste caso, é em função do número N de elementos do array.

Para cada número do array (ciclo i), é verificada a sua soma com todos os outros números (ciclo j). Assim, para cada iteração do ciclo i, o ciclo j tem N-1, N-2, N-3, .., 1, 0 iterações.
O número total de iterações é a soma dos números [0, N-1] que é a soma da conhecida progressão aritmética de passo 1, igual a N*(N-1)/2 = (N² - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,

• O((N² - N) / 2) = O(N² / 2), ignoramos o factor N porque este é dominado pelo factor N²
• O(N² / 2) = O(N²), ignoramos o factor 1/2 visto que é uma constante.

Deste modo, conseguimos uma definição compacta para a complexidade temporal do algoritmo proposto (ler os links dados para mais detalhes): O(N²). O processo pode parecer complexo ou envolvendo muita matemática mas na verdade é tipicamente muito simples porque ignoramos as constantes e outros factores dominados (e.g. o N acima).

Agora que sabemos qual é o tempo de execução, falta-nos estimar o N máximo para que o programa execute no máximo em 1s. O meu portátil tem um processador com frequência de 2.53 GHz, isto significa que o processador executa cerca de 2.53 * 10⁹ instruções por segundo. No entanto, o processador não está 100% dedicado ao nosso programa e aquilo que programamos é tipicamente traduzido em mais do que uma instrução do processador.

A experiência diz-nos que uma estimativa razoável é considerar que 100 milhões de operações são executadas em 1 segundo. Como o nosso programa tem um tempo de execução O(N²), o nosso programa pode processar √10⁸ = 10000 números em 1s. A tabela seguinte contém algumas estimativas do tempo de execução em função do tamanho do input (ver análise de algoritmos).

Nota: como diz no artigo, estes tempos consideram apenas ciclos que demoram um determinado tempo, ignorando o resto do programa. Daí a diferença de 1s para 0.1s, 1s é uma estimativa mais conservadora.

Exercício para o leitor: a solução apresentada é propositadamente ineficiente. Como fazer melhor do que 2 ciclos encadeados? Isto é, como fazer melhor do que O(N²)?

Impacto na vida real e no meu estágio na Google
Não há necessidade de reinventar a roda nestes posts. Volto a sugerir a leitura dos links referidos para obtenção de mais informação. Existem diversos tipos de algoritmos e conhecimento é poder.
Este conhecimento de determinados algoritmos ou técnicas pode permitir transformar uma ideia que parecia impossível (como vimos acima, um algoritmo poderia demorar centenas de anos ou mais até dar a resposta) numa feature bem real e popular que torna a nossa aplicação melhor do que a concorrência.

Muitos dos problemas dos concursos de programação são apresentados via uma história que pode parecer irrealista. No entanto, os algoritmos usados para resolver estes problemas são úteis para as situações que aparecem na vida profissional de um engenheiro de software.

As skills desenvolvidas ao participar nos concursos de programação são úteis no desenho e implementação de soluções para os desafios do software. Não só a parte dos algoritmos, mas também a capacidade de trabalho sob pressão, debugging e coding skills. Com a experiência destes concursos, e lendo soluções de outros concorrentes se possível (e.g. TopCoder, CodeChef), nós aprendemos a estruturar os nossos algoritmos da forma mais simples possível, resultando tipicamente em código bastante sucinto e eficiente.

Eu já resolvi alguns milhares de problemas online, seja em treino, seja por hobby. Assim, já enfrentei desafios muito diversos e também problemas semelhantes mas com restrições ou enquadramentos diferentes.
Deste modo, o meu cérebro foi treinado ao longo do tempo para analisar e identificar rapidamente quais são os requisitos e as restrições verdadeiramente importantes de diversas situações, seguido-se a identificação da solução mais apropriada para cada situação.
A consequência disto foi estar à vontade durante as entrevistas e conseguir um estágio na Google. Além disso, quer se queira, que não, parte do desenvolvimento de software é pouco desafiante e/ou repetitivo. A experiência adquirida ao resolver este tipo de exercícios permitia-me resolver as minhas tarefas muito rapidamente porque estava (tipicamente) perante problemas (mais fáceis ou mais difíceis) que já tinha enfrentado antes. Daí o ganho na produtividade.
Frequentemente, os meus superiores tinham de me arranjar outros projectos para me manter ocupado ("I have to find something to keep this guy busy"), enquanto que eles tentavam arranjar tempo para me fazerem code reviews :-)

Sou o maior da minha aldeia, mas.. isso significa alguma coisa?

Já conheço o CodeChef há bastante tempo, mas só nas últimas férias, em Agosto, decidi participar no seu concurso mensal. Estes concursos mensais decorrem no inicio de cada mês, contêm 10 problemas que os concorrentes podem tentar resolver durante os 10 dias de prova.

Após 2 concursos, Agosto e Setembro, já sou o #1 português do ranking de concursos longos (os de 10 dias). Sim, sou o maior da minha aldeia, mas.. na prática .. isso significa alguma coisa?

Por um lado, a minha participação é puramente por hobby, for fun. No concurso de Setembro, dediquei algumas horas (de 1 dos 10 dias) ao concurso e resolvi 6 dos 10 problemas.
Por outro lado, e mais importante do que isso, só há 14 portugueses a participar no CodeChef. Além disso, não se sabe se eles estão a dedicar-se mais ou ainda menos do que eu. Mais ainda, não se sabe se são muito bons, medianos ou medíocres.

Este é apenas um exemplo do quão enganosos os números podem ser. Na prática, estes números não significam nada.
Eu cheguei a ter colegas na escola que só decidiam se ficavam satisfeitos ou tristes com uma nota depois de saber as notas dos outros. Esta mentalidade é muito comum e é um grande erro. Nós devemos aproveitar o contacto com as pessoas à nossa volta para aprender o máximo possível, mas estas pessoas não devem nunca definir os nossos limites ou os nossos objectivos.

Por todos estes motivos, o meu lema nunca foi tentar ser o melhor da turma ou da minha aldeia, mas sim tentar sempre aprender mais e melhorar as minhas competências. Usando uma analogia do futebol, o que acham melhor: ser o melhor jogador a actuar nos campeonatos distritais ou fazer parte da equipa campeã nacional?

Citando William Faulkner,

Always dream and shoot higher than you know you can do. 

Don't bother just to be better than your contemporaries or predecessors.

Try to be better than yourself.