A neat probability puzzle

Howdy, it's been a while since I last posted. I saw a neat puzzle on Quora that I'd like to share:

Three people enter a room. Each person is assigned a hat uniformly at random: either red or blue. Each person can see the hats of the two other people, but they can't see their own hats. Each person can either try to guess the color of their own hat or pass. All three do it simultaneously, so there is no way to base their guesses on the guesses of others. 

If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose.
One more thing: before the contest, the three people have a meeting, during which they decide their strategy. What is the best strategy to maximize their odds of winning a prize?

Selecting values from a stream at random

Saw an interesting question today at CareerCup:

Given a stream of pairs (id, weight), write a function that selects an id at random, with probability proportional to its weight (compared to the total weight sum when the stream has ended). The stream size is unknown in advance and you're allowed O(1) memory. 

Example: if the stream was {(1,2),(2,2),(3,4),(4,10)}, then id 2 would be returned with probability 1/9.

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.

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.

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.

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

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.

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)

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?

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.

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?

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.