7. Problemas algorítmicos

Agora que já vimos alguns conceitos básicos de algoritmos vamos resolver alguns problemas para treinar, mas antes uma pequena nota.

Porque é que é importante treinarmos resolvendo problemas? É claro que para aprendermos um conceito é importante praticar aplicando-o e vendo diferentes vertentes do mesmo. Para resolver com sucesso problemas de Olimpíadas é preciso um pouco mais do que saber muitos conceitos como os que introduzimos aqui. O objetivo destes artigos é fornecer ferramentas que possam aplicar em diferentes contextos, mas no fundo todos os problemas requerem um pouco de criatividade. Isto significa que é preciso encontrar uma forma de simplificar ou abordar o problema para então chegar a uma solução. Isto é um pouco abstrato, mas com o tempo ficará mais concreto.

Venham então alguns problemas. Os primeiro usa técnicas que aprendemos nos últimos artigos, mas os últimos são um pouco mais abertos.

Problema 1

Vamos ver o primeiro problema que saiu numas Olimpíadas passadas. Foi o problema A da Qualificação de 2018. Podem encontrá-lo no Mooshak no concurso que inclui os problemas de Qualificação de 2016 a 2018, ou se quiserem ver só o enunciado, está disponível aqui. Nota, a solução deste problema está disponível online, mas se não conhecem o problema é boa ideia tentar resolvê-lo por vocês primeiro.

Este problema apenas requer que pensemos um pouco sobre a operação que estamos a fazer e depois aplicar uma das ferramentas que já vimos antes para melhorar essa mesma operação.

Problema 2

Mais um problema que saiu numas Olimpíadas passadas. Vamos resolver o problema A da Qualificação de 2016. Podem encontrá-lo no Mooshak no concurso que inclui os problemas de Qualificação de 2016 a 2018, ou se quiserem ver só o enunciado, está disponível aqui.

O problema é um pouco diferente do que vimos até agora. Comecem por pensar na solução $O(N^2)$, não deve ser muito difícil. Agora, que tipo de operações estamos a repetir várias vezes? O objetivo é agora manter alguma informação à medida que vamos iterando pela sequência de caracteres de forma a evitar repetir esse trabalho. Esta é uma ideia algorítmica muito importante e que aparece em muitos problemas, muitas vezes de forma mais disfarçada e difícil de aplicar.

Problema 3

Terminamos com um problema novo.

O Francisco organizou a sua coleção de canecas pela sua estante. Ele tem exatamente $N$ canecas e a sua estante tem $N$ prateleiras, numeradas de 1 a $N$ de baixo para cima. Para organizar tudo, o Francisco colocou exatamente uma caneca por prateleira.

No próximo Domingo vai haver uma grande festa e todos os seus $M$ amigos vão comparecer. O Francisco quer que cada um dos seus amigos tenha direito a uma caneca, mas nem todos conseguem chegar a todas as prateleiras. O i-ésimo amigo tem uma altura $A_i$, ou seja, consegue chegar a todas as prateleiras desde a primeira até à $A_i$. Cada amigo vai à estante buscar exatamente uma caneca, das canecas a que consegue chegar (se alguém não conseguir chegar a uma determinada prateleira, não pode pedir ajuda a um colega mais alto). Consegues determinar se existe uma forma de atribuir canecas a cada um de forma a que cada um consiga chegar à sua caneca?

Vamos ver um pequeno exemplo. Suponhamos que o Francisco tem $N=5$ canecas e prateleiras e $M=4$ amigos, com alturas $[5, 1, 3, 3]$, então o primeiro pode ficar com a caneca na prateleira 5, o segundo com a caneca na prateleira 1, o terceiro com a caneca na prateleira 2 e o quarto com a caneca na prateleira 3, logo é possível que cada um fique com uma caneca. Mas se o primeiro amigo tivesse altura 3 em vez de 5, já não existiria uma forma de distribuir canecas.

Para resolver este problema é preciso pensar um pouco em como escolher as atribuições de caneca/pessoa. É aqui que entra a tal criatividade que falámos no início. É preciso simplificar o problema de forma a arranjar uma forma eficiente, mas ótima. Por ótima queremos dizer que funciona sempre, ou seja, que se existe uma forma de distribuir as canecas, vamos encontrá-la e caso contrário não encontramos uma distribuição inválida. Uma solução que não é ótima neste sentido é chamada de "heurística", mas para a maior parte dos problemas das Olimpíadas queremos evitar este tipo de solução, pois não está correta e apenas nos vai atribuir alguns pontos com alguma sorte. Queremos obter uma solução que consigamos garantir que funciona sempre!

Uma pequena dica: imaginem que já atribuíram as primeiras $i$ canecas (ou seja, as canecas nas prateleiras $1, 2, \ldots, i$) a alguns dos amigos do Francisco, a quem devem atribuir a próxima caneca? Se só dois dos amigos do Francisco chegarem à próxima prateleira e um tiver altura $a$ e o outro $b$, com $a < b$, quem deve ficar com a caneca?