CodeChef December Long Challenge - Problem Course Selection

In the beginning of the month, I enjoyed participating in CodeChef's December Long Challenge. I was pretty proud to get 33^rd place out of 5726 contestants.

The hardest challenge was the problem Course Selection.

We want to attend N courses over M semesters. There are K course prerequisites (a, b) - we must take course a before b. We're also given a matrix X where X[i][j] is the grade (0..100) obtained if we take course i at semester j or -1 if we can't take the course in that semester.
What is the maximum average grade we can obtain?

It is guaranteed it is possible to take the N courses. Constraints:

• 0 <= N, M, K <= 100
• -1 <= X[i][j] <= 100  

For 20% of the points, a course has at most one prerequisite.

Alterações no blog

Olá de novo!

Não escrevia há muito tempo. Para além das habituais limitações de tempo, estive limitado a escrever devido a ter sido juri de vários concursos ao longo dos últimos meses. Assim, seria inconveniente escrever sobre algo que pudesse aparecer num desses concursos.

Um desses concursos foi o South Western European Regional Contest 2014. Podem ver no site o conjunto de problemas, dicas sobre a resolução e soluções do juri.

Por fim, estive a pensar no formato do blog. Penso que escrever em português é um pouco limitativo. Assim, devo continuar a escrever conteúdos introdutórios em Português mas escrever em Inglês sobre problemas de concursos internacionais.

Final ONI 2005: Problema B - A máquina do Professor ONI

Tem sido difícil arranjar tempo para escrever no blog. Hoje continuo a análise de problemas, desta vez sugiro o problema B da final de 2005 - A máquina do Professor ONI.

Neste problema, temos uma máquina que é constituída por um conjunto de tubos que se bifurcam em L níveis (1 < L < 20). No final dos tubos do último nível, existem baldes, numerados a partir de 1. Existe uma patilha em cada bifurcação. Quando lançamos uma bola no início do primeiro tubo, esta segue a orientação das patilhas. Inicialmente, todas as patilhas estão orientadas para a direita, mas quando uma bola passa numa patilha, a sua orientação inverte-se (direita -> esquerda e vice-versa).

Exemplo de uma máquina com 2 níveis e o resultado do lançamento de 4 bolas.

Assim, o objectivo do problema é saber, após o lançamento de N bolas (1 ≤ N ≤ 1 000 000) numa máquina com L níveis, em que balde é que a N-ésima bola cai.

Final ONI 2005: Problema A - Futebol

Já estão apurados os finalistas das Olimpíadas de Informática 2014. A final é já na próxima semana :)

Mas hoje vou continuar a análise dos problemas que tenho vindo a fazer. Começo a final de 2005, ano do meu 12º, com o problema A - Futebol.

Neste problema, é-nos dada a dimensão de um terreno rectangular com Y linhas e X colunas (1 ≤ Y, X ≤ 1000). Em cada célula do mapa existe relva ou uma árvore. Queremos construir um campo de futebol com L linhas e C colunas. Em que posição do mapa devemos construir o campo, de modo a termos de cortar o mínimo de árvores possível?

Exemplo do enunciado: mapa com 5 linhas e 8 colunas, para um campo de futebol 2x3 basta cortar 1 árvore

Qualificação ONI 2005: Problema C - Descobrindo Anagramas

O último problema da qualificação das ONI 2005 chama-se Descobrindo Anagramas.

Uma classe de anagramas é um conjunto de palavras com as mesmas letras mas por outra ordem. Exemplo: caras, casar e sacar são anagramas, fio e foi formam outra classe.

Dado um texto com no máximo 20 000 palavras distintas, pretende-se saber quantas classes de anagramas existem.

Nos dias de hoje, esta este problema muito frequente em entrevistas de emprego.

Qualificação ONI 2005: Problema B - Dizimação Completa

O problema B da qualificação das ONI 2005 chama-se Dizimação Completa.
Dados A e B com 0 < A < B e B ≤ 1024, o problema consiste em determinar a representação do número A / B. Alguns números têm representação exacta, mas outros têm dizimas infinitas.
Dos que não têm representação finita, alguns têm uma parte fixa e outros não.

Exemplos:

• 1 / 2 = 0.5
• 127 / 128 = 0.9921875
• 1 / 7 = 0.142857142857... não tem parte fixa e o período “142857” repete­-se indefinidamente.
• 19 / 44 = 0.43181818... a parte fixa é “43” e a parte periódica é “18”.

Assim, o objectivo é apresentar o número no formato "parte_fixa#período".

Qualificação ONI 2005: Problema A - Tiro ao Alvo

Agora passamos para as ONI 2005. Desta vez, temos disponíveis os problemas da qualificação.
O problema A chama-se Tiro ao Alvo e é provavelmente dos problemas mais simples que já vi nas ONI.

São-nos dadas as coordenadas do centro de N (<= 100) círculos e o respectivo raio e até 10000 pontos correspondentes a dardos. O objectivo é determinar a pontuação de cada dardo: o número de círculos que contêm esse dardo, agregar o número de dardos com a mesma pontuação e mostrar o output ordenado por pontuação.

Análise
O problema envolve simplesmente testar cada dardo contra cada um dos círculos, usando a equação do círculo (x-x₀)² + (y-y₀)² <= r².
Note-se que este algoritmo tem uma complexidade na ordem de 100*10 000 = 1 000 000 operações, sendo seguramente suficientemente eficiente.
Só podem existir N+1 (no máximo 101) pontuações diferentes, por isso nem é necessário utilizar um algoritmo muito eficiente para a ordenação.