XIV Maratona de Programação da SBC - Problema G

Esse problema eu fiquei "sentado em cima da solução" por um bom tempo (desde o dia da maratona), então vamos, sem mais rodeios, à solução do Problema H - Escultura a Laser. Esse problema tem uma solução quadrática simples, tanto que dos times que resolveram ele em Curitiba, boa parte sofreu com tempo limite excedido. Porém, a solução linear dele não é tão óbvia, tanto que algumas equipes não conseguiram resolvê-lo. A pergunta é simples, dado um histograma de alturas de uma peça recortada com um laser, quantas vezes é preciso ligar o laser para que o corte seja feito?

Vamos estabalecer as regras do jogo. Primeiro, o laser percorre na horizontal a peça, retirando uma camada de material por passada. Toda vez que o laser acaba uma passada ele é desligado, volta à posição inicial e, se for o caso, é ligado novamente. Não tem nenhuma pegadinha de otimização com o laser indo e vindo. Assim, caso exista uma protuberância no caminho, o único jeito de fazê-la é desligando o laser para que o material não seja cortado.

A solução ingênua é simular o funcionamento do laser, removendo as camadas em um for aninhado de altura A e largura C. Ingênua porque ela é quadrática e estoura o tempo de processamento. Os limites são de 10000 para cada dimensão, assim, são 100 milhões de comparações que devem ser realizadas. Como o juiz online é draconiano e tem uma entrada dessas, não precisa ser gênio para entender porque essa solução não serve.



A solução linear, por sua vez, requer um pouco de insight, já que devemos pensar "verticalmente". O fato do laser ir do começo ao final é traiçoeiro neste problema, já que ele nos induz ao uso de uma repetição para percorrer o bloco de material do início ao fim, de cima para baixo. Porém tal fato é irrelevante: Não precisamos saber quantas viagens o laser faz do início ao fim, mas sim quantas vezes ele é ligado no processo. Assim, basta considerar, para cada degrau descendente no objeto, que o laser foi ativado uma vez para cada unidade de altura, como na figura abaixo! Quando subimos, o laser é desligado, então não conta. Idem para quando mantém-se a altura, o laser vem ligado e pronto.



A solução deste problema usando apenas uma repetição simples usa uma variável auxiliar que marca a altura atual do objeto, inicialmente a altura máxima da peça (dado no problema), além de um contador de vezes em que o laser foi ligado (que começa com zero). Com uma repetição do começo ao final do histograma fornecido, observamos a variação da altura do bloco com a altura atual. Se ela permanece a mesma não fazemos nada. Se ela mudar, além de alterarmos a altura atual verificamos a diferença de altura: se subiu, ignoramos, mas se desceu, adicionamos ao contador o módulo da diferença. Ao encerrar a repetição, o contador tem o número de vezes em que o laser foi ligado.

O fonte do programa C que faz a solução linear encontra-se aqui. Agora é começar a implementar o resto que já tem esquematizado, mas nunca tive inspiração de codificar :).

Forma vs Conteúdo

O Pio num twit interessante sobre metodologias ágeis me fez lembrar de um assunto interessante. Hoje em dia, uma empresa de software valoriza mais a forma do que o conteúdo. Não importa se o sistema for simplesmente uma agenda para a produção de pão em uma padaria, o mercado valoriza tanto a reusabilidade de código, a documentação, o plano de testes, a infra-estrutura utilizada e 2000 páginas de documentação que, no final, a funcionalidade única do sistema fica em segundo plano.

Longe de defender uma metodologia anárquica, porém organização por si só não garante boas coisas, afinal, ela deve ter um objetivo maior. E é aí que eu vejo alunos entrando de cabeça em todo esse aparato sem se preocupar que isso é acessório para realizar uma tarefa bastante concreta e que existe no mundo real. Não adianta dezenas de boas práticas se no fundo não se conhece bem o negócio que se quer modelar. Dificilmente o cliente reclama que o sistema trava, mas sim que ele não faz o esperado. E não tem boa prática de projeto ou infra-estrutura de servidor que resolva isso.

Acho difícil sair dessa espiral descendente em que se mede qualidade de software com métricas que são dissociadas do objetivo do software em si. Afinal, uma empresa de software é tocada por administradores que não sabem diferenciar um documento Word de um programa Hello world!, mas é preciso pelo menos colocar na cabeça do pessoal que sai da universidade de que software é negócio, mas não nosso, é negócio do cliente e que nenhuma metodologia vai conseguir sozinha traduzir isso para um sistema. Por mais simples que ele seja.

Aleluia!

Até que enfim, um ambiente de desenvolvimento para Linux legal, que consegue depurar um programa SDL multi-thread sem aperto: Netbeans. Quem diria que o ambiente Java mais caprichado iria, também, ser uma boa pedida para programar C/C++? Projetos organizados de maneira clara e simples, configurações intuitivas, projetos com referência relativa aos arquivos e integração perfeita com o gdb. Falta chão para chegar no Visual C++, mas o suporte a C/C++ dá de 10 no Eclipse (que pra mim já leva de 10 quando o assunto é Java).