domingo, 28 de dezembro de 2014

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 33rd 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.

terça-feira, 20 de maio de 2014

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.

quinta-feira, 1 de maio de 2014

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

segunda-feira, 31 de março de 2014

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: carascasar e sacar são anagramas, fio 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.

domingo, 30 de março de 2014

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".

quarta-feira, 26 de março de 2014

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-x0)2 + (y-y0)2 <= r2.
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.

terça-feira, 25 de março de 2014

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.

domingo, 23 de março de 2014

Final ONI 2004: Problema C - Em busca dos números perdidos

O último problema da final das ONI 2004 é bem mais interessante do que os outros. Este problema chama-se Em busca dos números perdidos.

Neste problema, são-nos dados 2 números parcialmente definidos, e.g. "?3" e "?", e temos de determinar quantas maneiras possíveis existem de substituir os '?' por um digito 0-9, de modo a que a soma dos 2 números seja um número primo (e.g. "03" + "0" = 3 que é primo).

Os números parcialmente definidos têm até 4 caracteres, i.e. "????" + "????" é um input válido, assim como "1234" + "5678" também. Existem até 100 casos de teste em cada execução.

Final ONI 2004: Problema B - Analisador de Textos

O problema B das finais das ONI 2004 chama-se Analisador de Textos.

Neste problema, é-nos fornecido um texto composto por L (<= 10 000) linhas de até 100 caracteres e temos de produzir uma de 4 possíveis estatísticas:
  1. Calcular o número de palavras no texto e o número de palavras diferentes.
  2. Contar as ocorrências de cada letra do alfabeto no texto.
  3. Listar as palavras por ordem de frequência decrescente.
  4. Listar as palavras por ordem de comprimento decrescente.
Não há mais de 60000 palavras no texto, nem mais de 5000 palavras diferentes. Cada palavra tem no máximo 30 letras.

Final ONI 2004: Problema A - Base Lunar

Em 2004, as finais nacionais das ONI passaram para o formato actual: 3 problemas para resolver em 4 horas. O problema A destas finais foi o Base Lunar.

Neste problema, temos um mapa lunar de dimensão máxima 20x20 quadrículas e um conjunto de N (<= 50) crateras. As crateras são círculos e são-nos fornecidas as coordenadas do seu centro e raio. Uma quadrícula considera-se dentro da cratera se o centro da quadrícula estiver contido no circulo.
Disto isto, o objectivo é determinar qual é a maior linha horizontal e vertical de quadrículas não abrangidas pelas crateras.

sábado, 22 de março de 2014

ONI 2003 - Alcunhas

O segundo problema das finais das ONI 2003 chama-se Alcunhas. Neste problema, temos um dicionário com N palavras (N <= 1000) com até 30 letras. Posto isto, é dado um número indeterminado de nomes de pessoas na mesma linha separados por espaços e temos de terminar quais os nomes cujas iniciais formam palavras do dicionário. Exemplo: as iniciais de "Rita Inês Costa Almeida" formam a palavra "rica".

sexta-feira, 21 de março de 2014

ONI 2003 - Pizzapolis

A edição deste ano das Olimpíadas Nacionais de Informática (ONI) está prestes a arrancar. Estive a olhar para a página com os problemas de edições passadas e reparei que não existe uma página de discussão da maioria dos problemas. Como a análise aos problemas pode ser útil para quem está a praticar, decidi tentar fazê-la aqui no blog, começando no ano do meu 10º ano - 2003. Ao contrário de outros posts, a minha intenção é descrever as ideias principais e não postar o código, pois é importante que quem esteja a treinar seja capaz de implementar essas ideias por si.

O problema A da final nacional de 2003 chama-se Pizzapolis. Neste problema, estamos perante uma cidade com estradas perpendiculares umas às outras (chamamos ruas às estradas horizontais e avenidas às verticais). Existem milhares de pizzarias, situadas no cruzamento de uma rua com uma avenida, mas Pizzapolis contém 100 ruas e 100 avenidas, numeradas de 0 a 99.
Assim, dada a localização (rua e avenida) e a produção diária de cada pizzaria, o objectivo é determinar quais são as ruas e/ou avenidas com produção máxima de pizzas.

terça-feira, 18 de março de 2014

Check iO: um jogo educativo para aprender/practicar Python

Olá!

Não tenho tido tempo para escrever no blog. No entanto, gostava de divulgar um site que me parece muito interessante: http://www.checkio.org


Este site funciona como um jogo de plataformas. Começamos na plataforma Home e para acedermos a outras plataformas temos de resolver exercícios de programação. Cada exercício tem um número de pontos associado e tem de ser resolvido recorrendo a Python 2.7 ou 3.3.

A parte mais interessante do site é que nos permite ler o código de outras pessoas após resolvermos os desafios. Assim, dá para aprender bastante para quem não for muito fluente em Python como eu.

A título de exemplo, um dos exercícios iniciais é escrever uma função que devolve a transposta de uma dada matriz. O meu código para resolver o exercício foi o seguinte:

1
2
3
4
5
6
7
def checkio(data):
    L, C = len(data), len(data[0])
    transp = [[0] * L for i in xrange(C)]
    for i in xrange(L):
        for j in xrange(C):
            transp[j][i] = data[i][j]
    return transp

Contudo, bastava usar a função standard zip et voilà:

1
2
def checkio(data):
    return zip(*data)

quinta-feira, 30 de janeiro de 2014

Jogo da Ponte (SPOJ - WAYHOME)

Na semana passada, vi um problema engraçado no SPOJ chamado WAYHOME e decidi resolvê-lo, sendo o meu problema #698 para o ranking (759 resolvidos no total).
O problema baseia-se num puzzle que já tinha ouvido falar e que dá para fazer aos amigos:
Um grupo de pessoas pretende atravessar uma ponte usando uma lamparina. A ponte é perigosa e só 2 pessoas podem atravessá-la ao mesmo tempo. As pessoas caminham a velocidades diferentes, por isso, se 2 pessoas estão a atravessar a ponte, deslocam-se à velocidade da mais lenta. Além disso, está escuro, por isso uma das pessoas tem de levar a lamparina enquanto atravessam a ponte. 
Dadas as velocidades das pessoas, qual é o tempo mínimo para passar todas as pessoas de um lado para o outro? E.g. 3 pessoas com velocidades 1, 1 e 2, demoram 4min a atravessar (ver figura seguinte). Se forem 4 pessoas com velocidades 1, 2, 4, 8, demoram 15min. Porquê? E se forem N pessoas, que abordagem garante o menor tempo possível?

domingo, 19 de janeiro de 2014

Pesquisa Binária - Parte 4: Uma pergunta de entrevista tramada

Para fechar este ciclo sobre a pesquisa binária, sugiro uma pergunta de entrevista:
Dados 2 arrays de inteiros ordenados de forma crescente, determina o K-ésimo número mais pequeno do conjunto dos 2 arrays em tempo sublinear e com O(1) de memória extra.

quinta-feira, 16 de janeiro de 2014

Pesquisa Binária - Parte 3: Problema EKO - SPOJ

O último post foi dedicado a alguns fundamentos sobre a pesquisa binária. Às vezes não é óbvio que podemos utilizar este método de pesquisa e obter um algoritmo eficiente. Considerem o problema EKO do SPOJ como exemplo:
Temos uma floresta com 1 000 000 de árvores e queremos obter pelo menos M (<= 2 000 000 000) de madeira. Podemos cortar todas as árvores a uma certa altura inteira, ficando com o que for cortado. A que altura devemos cortar as árvores de modo a obter pelo menos M de madeira e o mínimo desperdício?

segunda-feira, 13 de janeiro de 2014

Pesquisa Binária - Parte 2: Fundamentos

No último post, falei um pouco sobre um método de pesquisa chamado Pesquisa Binária. Pegando na pesquisa num dicionário como exemplo, procurei demonstrar que nós próprios utilizamos este método intuitivamente. Enquanto que o outro post foi mais dedicado a código, neste post pretendo explorar um pouco os fundamentos que nos permitem usar este método de pesquisa.

terça-feira, 7 de janeiro de 2014

Pesquisa Binária

Um dos problemas mais frequentes no dia-a-dia é a procura de informação. Dependendo do tipo de pesquisa, nós vamos descobrindo e utilizando truques para agilizar esta pesquisa. Um exemplo da nossa infância é a procura de uma palavra no dicionário. Como é que nós procuramos o significado da palavra "inócuo" no dicionário?

Suponhamos que o dicionário tem 1000 páginas. Uma abordagem comum é abrirmos o dicionário no meio, 500ª página. Digamos que calhamos numa página cujas palavras começam por "L". Isto significa que "inócuo" tem de estar para a esquerda no dicionário pois "I" vem antes do "L".
Assim, podemos repetir o processo mas considerando apenas a primeira metade das páginas. Desta vez vamos à 250ª página e suponham que esta página tem palavras começam por "F". Deste modo, sabemos que "inócuo" tem de estar para a direita - iríamos para a 375ª página a seguir. Após repetir o processo, vamos encontrar (eventualmente) uma página referente à letra "I". De seguida, continuamos com a 2ª letra da palavra a procurar - "n" em "inócuo" - e assim sucessivamente até encontrar a palavra.

Exemplo da redução sucessiva do espaço de pesquisa numa pesquisa binária
A procura no dicionário é provavelmente intuitiva para toda a gente e pode até parecer estranho sistematizar este processo. No entanto, é esta sistematização que nos permite aplicar este método num programa. No exemplo anterior, começamos com um dicionário de 1000 páginas e fomos reduzindo o intervalo de páginas a procurar (espaço de pesquisa) para metade em cada iteração: 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. Reparem que necessitamos de procurar apenas 10 páginas em vez de 1000 para encontrar a palavra.

Este método tem o nome de Pesquisa Binária (Binary Search no TopCoder). Visto que reduzimos o espaço de pesquisa para metade em cada iteração, a complexidade temporal deste método é O(log N): log2(1000) ~ 10. O único requisito da pesquisa binária é que exista uma ordem no input, seja ele um dicionário (palavras ordenadas alfabeticamente), um array de números ordenados ou outra.
Implementação em C++ da pesquisa de um número num array ordenado de forma crescente (retorna o índice no array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Se existirem valores repetidos iguais a "valor", retorna um qualquer.
int PesquisaBinaria(int* valores, int n, int valor) {
    int esq = 0, dir = n-1;
    while (esq <= dir) {
        int mid = (esq + dir) / 2;
        if (valores[mid] == valor) {        // encontrou!
            return mid;
        } else if (valores[mid] < valor) {  // está na parte direita
            esq = mid+1;
        } else {                            // está na parte esquerda
            dir = mid-1;
        }
    }
    return -1;  // inexistente
}

2 problemas relacionados já referidos em posts anteriores são:
  • Procurar o menor número maior ou igual a um valor dado - função lower_bound em C++
  • Procurar o menor número maior do que um valor dado - função upper_bound em C++
Este problema pode ser abordado com pesquisa binária. A diferença para a pesquisa binária tradicional é que não procuramos um número especifico. Não terminamos a pesquisa precocemente, mas encurtamos o espaço de pesquisa até 1 elemento.

Notem que a diferença entre as duas funções é apenas uma condição com < e outra com <=. Caso não exista solução, as funções devolvem n, o número de elementos do array.
No caso do LowerBound, se existirem múltiplos valores iguais ao valor a procurar, retorna o menor índice no array com esse valor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Procura o menor número maior ou igual ao valor dado num array ordenado
int LowerBound(int* valores, int n, int valor) {
    int esq = 0, dir = n-1;
    while (esq <= dir) {
        int mid = (esq + dir) / 2;
        if (valores[mid] < valor) {  // está na parte direita
            esq = mid+1;
        } else {
            dir = mid-1;
        }
    }
    return esq;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Procura o menor número maior do que o valor dado num array ordenado
int UpperBound(int* valores, int n, int valor) {
    int esq = 0, dir = n-1;
    while (esq <= dir) {
        int mid = (esq + dir) / 2;
        if (valores[mid] <= valor) {  // está na parte direita
            esq = mid+1;
        } else {
            dir = mid-1;
        }
    }
    return esq;
}

Existem outras aplicações da pesquisa binária. Por exemplo: como encontrar a raiz quadrada de um número sem recorrer a funções standard?