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 :).