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.

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.

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

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): log₂(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?

Exemplo de entrevista para Engenheiro de Software na Google

No mês passado, concorri a um estágio de verão na Google. O processo foi relativamente rápido (3~4 semanas), visto que já estagiei na Google no ano passado, e para minha satisfação, recebi a desejada oferta para estagiar no próximo verão em Nova Iorque :)

Para quem estiver interessado em concorrer a uma posição na Google, este post exemplifica uma entrevista para a posição de Engenheiro de Software (Amazon, Apple, Facebook, Microsoft, usam estilos semelhantes). São apresentadas possíveis questões e a forma como eu responderia, para além de alguns comentários sobre o raciocínio (em itálico). Notas prévias:

1. Esta é apenas a minha visão do funcionamento das entrevistas e não necessariamente a da Google.
2. Não pretendo, de modo algum, afirmar que esta é a melhor forma de responder a estas perguntas. Estas são simplesmente as respostas que eu daria e o tipo de raciocínio que utilizaria.
3. Estas perguntas não foram tiradas das minhas entrevistas, mas são exemplos representativos.

Estas entrevistas, quer sejam feitas por telefone ou presencialmente, têm uma duração de 45 minutos e podem ser tipicamente divididas em 4 partes:

1. Quebrar o gelo
2. Coding - perguntas para as quais temos de implementar a nossa solução
3. System Design - perguntas mais genéricas para discussão aberta
4. Espaço para fazer perguntas ao entrevistador

A única parte obrigatória é a parte 4. De resto, as entrevistas podem tocar em perguntas de cada parte ou focar-se só nas partes 2 ou 3. Uma regra de ouro é não estar muito tempo calado, mas procurar explicar ao máximo aquilo em que estamos a pensar. Caso contrário, o(a) entrevistador(a) não faz ideia se percebemos bem a pergunta ou se estamos com dificuldades.

MIUP 2013 - Um problema de Grafos

Não tive oportunidade de escrever no blog nas últimas semanas. Para compensar, hoje vou falar de um problema um pouco mais difícil do o habitual: o problema B da MIUP 2013 - Say Geese.

Objectivo do problema:

Dado um grafo não-dirigido com N (<= 11) vértices e E (<= 45) arestas (edges), quantos subconjuntos de arestas formam um grafo conexo?

MIUP 2012 Problema C - Um algoritmo ganancioso

A Maratona Inter-Universitaria de Programação (MIUP) 2013 é já no próximo sábado.
A minha última participação foi em 2009 (equipa LuscoFusco) e não tenho seguido com muita atenção as últimas edições da prova. Dada a proximidade da MIUP deste ano, estão disponíveis para treino os problemas de alguns concursos, incluindo os da MIUP 2012. Eu decidi ir resolver os problemas for fun.

Penso que os problemas são equilibrados, com um nível de dificuldade adequado e incluindo alguns problemas com casos particulares para distinguir as equipas com mais atenção ao detalhe. A única critica negativa que faço é ao problema D onde penso que não é claro no enunciado que os carros a colocar num ferry têm de ser consecutivos no input (e isso faz toda a diferença na solução).

O problema que gostei mais foi o problema C - Humanitarian Logistics. Sucintamente, temos N caixas de alimentos, cada uma com um tempo de validade T_i (em dias) e um valor V_i. Em cada dia, podemos escolher uma das caixas cuja validade não tenha expirado para distribuir pela população. O objectivo é minimizar o desperdício, isto é, o valor das caixas cuja validade expira antes de serem entregues, e imprimir os índices (de ordem no input) das caixas que serão entregues por ordem crescente de índice.

Os limites são 1 ≤ N ≤ 100,000;  1 ≤ T_i ≤ N;   1 ≤ V_i ≤ 100,000. Como resolver o problema de forma eficiente?

Follow-up: número de pares de números cuja soma é <= S

No último post, apresentei algumas abordagens para verificar se existem 2 números num array cuja soma é S. Por fim, sugeri um follow-up: e se fosse para contar o número de pares de números cuja soma é menor ou igual a S?

Para começar, a abordagem O(N²) precisa apenas de uma pequena alteração para contar os pares:

1 2 3 4 5 6 7 8

long long ContaPares(int* valores, int N, int S) { long long resultado = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] <= S) resultado++; return resultado; }

Note-se que se o array tiver uma dimensão considerável, e.g. ~100 000, o resultado pode exceder facilmente os 32 bits dos ints. Por outro lado, um programa com complexidade 100000²  é lento. Só esta função demoraria cerca de 15 segundos no meu computador.

Ordenação ajuda?
Como queremos os pares menores ou iguais a S, ordenar volta a parecer fazer sentido. Voltando ao exemplo dado no último post, o array ordenado fica -3, -2, 1, 5, 6, 7, 10 e S = 12.
Para o número -3, precisamos de saber quantos números existem menores ou iguais a S - (-3), ou seja, 15.
Para -2, seria quantos <= 14,
Para 1, quantos <= 11,
etc.

Se viram os links dados no último post, isto pode ser feito de forma eficiente com pesquisa binária. Assim, basta procurar qual é o índice do primeiro número do array ordenado maior do que S - número_actual e contar quantos números existem entre o número actual e esse índice.
No caso do C++, basta usar a função upper_bound().

1 2 3 4 5 6 7 8 9 10 11

long long ContaParesNlogN(int* v, int N, int S) { sort(v, v+N);  long long resultado = 0; for (int i = 0; i < N; i++) { // v+i+1 porque procuramos a partir da posição i+1 // caso não exista nenhum número > S-v[i], pos = N int pos = upper_bound(v+i+1, v+N, S-v[i]) - v; resultado += pos - (i + 1); } return resultado; }

Temos a ordenação e é feita uma pesquisa binária para cada um dos N números. Assim, o tempo de execução é O(N log N).

De modo análogo ao problema anterior, podemos voltar a eliminar a pesquisa binária. Se -3 + 10 for maior do que S, então o 10 não vai formar um par válido com nenhum outro número e pode ser descartado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

long long ContaParesNlogNv2(int* v, int N, int S) { sort(v, v+N); long long resultado = 0; int a = 0, b = N-1; while (a < b) { // descarta números que formam pares inválidos. while ((b > a) && (v[a] + v[b] > S)) b--; // conta os pares (a,a+1), (a,a+2), ... (a,b) = b - a pares resultado += b - a; a++; } return resultado; }

O ciclo while exterior tem, no máximo, N-1 iterações. Cada iteração do ciclo while interior descarta um número do fim do array e retira uma iteração ao ciclo exterior porque decrementa b. Assim, o tempo de execução é O(N). Contudo, o tempo total continua dominado pelo O(N log N) da ordenação.

E hashing?
Como vimos no post anterior, as hash tables são muito úteis. No entanto, não podem ser usadas em todas as situações. Para contar o número de pares de forma eficiente, precisamos de usar a ordem dos números. As hash tables são excelentes para inserir, eliminar ou pesquisar elementos, mas não nos dizem nada sobre a ordem dos números e são inúteis para este problema.

O(N) é possível?
No caso de arrays já ordenados, sim. Basta usar o método referido acima.
Para arrays não ordenados, estamos limitados pela ordenação. No caso de termos números inteiros, temos:

• Counting Sort: pode ser utilizado quando sabemos que os números estão contidos num intervalo pequeno (e.g. entre 0 e 1000, -100 e 100 ou 1000 e 9999).
• Radix Sort: depende do número de bits K necessário para representar todos os números e é bastante útil em algumas situações. O tempo de execução é O(K * N) e é considerado linear se K for considerado uma constante (K é independente do valor N).

Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

No último post, usei o seguinte problema como exemplo:

Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

A solução mais óbvia é testar todos os pares de números e foi demonstrado que o seguinte algoritmo tinha um tempo de execução O(N²).

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int S) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == S) return true; return false; }

A notação Ó-grande significa que o tempo de execução do algoritmo é no máximo proporcional a N².
Agora o desafio é: como fazer melhor para podermos suportar mais de 10000 números?

A importância dos algoritmos para um engenheiro de software

Estou muito satisfeito por estar a ajudar a renovar as equipas que vão representar a FEUP nos concursos de programação da ACM. Há muitos alunos novos que estão a ver este "mundo" pela primeira vez e foi giro ver a sua reacção no concurso interno que fizemos esta semana :-)

No entanto, apesar deste interesse inicial dos alunos, uma pergunta natural é: porque é que isto é importante? Ou, por outras palavras, porque é que eles hão de despender parte do seu tempo livre a aprender mais sobre algoritmos, estruturas de dados e tudo o resto que está relacionado com os concursos?

Parte da resposta já foi dada noutros sítios. Neste post vou apenas realçar algumas das razões.
Eu sugiro a leitura do tutorial do TopCoder sobre a importância dos algoritmos e o artigo da Academia ONI sobre a análise de algoritmos.

Antes de mais.. o que é um algoritmo?
Um algoritmo pode ser definido como uma sequência de passos que transforma um dado input (um valor ou conjunto de valores) no resultado pretendido - output - sendo este tipicamente um valor ou conjunto de valores.
Na prática, um engenheiro de software gasta grande parte do seu tempo a implementar algoritmos. Para cada parte do projecto de desenvolvimento de software, existem um conjunto de desafios e é necessário definir qual vai ser a abordagem para os ultrapassar. Estes desafios podem ser coisas simples como ler um ficheiro de texto e apresentar a informação ao utilizador ou coisas mais avançadas como o processamento de giga, tera ou mais bytes de dados para determinar alguma estatística.

Análise do tempo de execução de algoritmos
Imaginem que têm este problema: dados N números inteiros, existem 2 números que somados dão um número S?
Uma solução natural é testar todos os pares de números e verificar se a sua soma dá S. Exemplo em C++:

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int soma) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == soma) return true; return false; }

O código é simples e tudo indica que dá a resposta certa. No entanto, um factor importante na vida real é saber se esta performance chega para as nossas necessidades. Qual é a quantidade máxima de números que este algoritmo suporta se o nosso programa tiver no máximo 1 segundo para executar?

Para responder a esta pergunta, é necessário analisar o tempo de execução do algoritmo apresentado. A notação mais popular para representar o tempo de execução (ou complexidade temporal) é a notação Ó-grande e é expressa em função do tamanho do input. Neste caso, é em função do número N de elementos do array.

Para cada número do array (ciclo i), é verificada a sua soma com todos os outros números (ciclo j). Assim, para cada iteração do ciclo i, o ciclo j tem N-1, N-2, N-3, .., 1, 0 iterações.
O número total de iterações é a soma dos números [0, N-1] que é a soma da conhecida progressão aritmética de passo 1, igual a N*(N-1)/2 = (N² - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,

• O((N² - N) / 2) = O(N² / 2), ignoramos o factor N porque este é dominado pelo factor N²
• O(N² / 2) = O(N²), ignoramos o factor 1/2 visto que é uma constante.

Deste modo, conseguimos uma definição compacta para a complexidade temporal do algoritmo proposto (ler os links dados para mais detalhes): O(N²). O processo pode parecer complexo ou envolvendo muita matemática mas na verdade é tipicamente muito simples porque ignoramos as constantes e outros factores dominados (e.g. o N acima).

Agora que sabemos qual é o tempo de execução, falta-nos estimar o N máximo para que o programa execute no máximo em 1s. O meu portátil tem um processador com frequência de 2.53 GHz, isto significa que o processador executa cerca de 2.53 * 10⁹ instruções por segundo. No entanto, o processador não está 100% dedicado ao nosso programa e aquilo que programamos é tipicamente traduzido em mais do que uma instrução do processador.

A experiência diz-nos que uma estimativa razoável é considerar que 100 milhões de operações são executadas em 1 segundo. Como o nosso programa tem um tempo de execução O(N²), o nosso programa pode processar √10⁸ = 10000 números em 1s. A tabela seguinte contém algumas estimativas do tempo de execução em função do tamanho do input (ver análise de algoritmos).

Nota: como diz no artigo, estes tempos consideram apenas ciclos que demoram um determinado tempo, ignorando o resto do programa. Daí a diferença de 1s para 0.1s, 1s é uma estimativa mais conservadora.

Exercício para o leitor: a solução apresentada é propositadamente ineficiente. Como fazer melhor do que 2 ciclos encadeados? Isto é, como fazer melhor do que O(N²)?

Impacto na vida real e no meu estágio na Google
Não há necessidade de reinventar a roda nestes posts. Volto a sugerir a leitura dos links referidos para obtenção de mais informação. Existem diversos tipos de algoritmos e conhecimento é poder.
Este conhecimento de determinados algoritmos ou técnicas pode permitir transformar uma ideia que parecia impossível (como vimos acima, um algoritmo poderia demorar centenas de anos ou mais até dar a resposta) numa feature bem real e popular que torna a nossa aplicação melhor do que a concorrência.

Muitos dos problemas dos concursos de programação são apresentados via uma história que pode parecer irrealista. No entanto, os algoritmos usados para resolver estes problemas são úteis para as situações que aparecem na vida profissional de um engenheiro de software.

As skills desenvolvidas ao participar nos concursos de programação são úteis no desenho e implementação de soluções para os desafios do software. Não só a parte dos algoritmos, mas também a capacidade de trabalho sob pressão, debugging e coding skills. Com a experiência destes concursos, e lendo soluções de outros concorrentes se possível (e.g. TopCoder, CodeChef), nós aprendemos a estruturar os nossos algoritmos da forma mais simples possível, resultando tipicamente em código bastante sucinto e eficiente.

Eu já resolvi alguns milhares de problemas online, seja em treino, seja por hobby. Assim, já enfrentei desafios muito diversos e também problemas semelhantes mas com restrições ou enquadramentos diferentes.
Deste modo, o meu cérebro foi treinado ao longo do tempo para analisar e identificar rapidamente quais são os requisitos e as restrições verdadeiramente importantes de diversas situações, seguido-se a identificação da solução mais apropriada para cada situação.
A consequência disto foi estar à vontade durante as entrevistas e conseguir um estágio na Google. Além disso, quer se queira, que não, parte do desenvolvimento de software é pouco desafiante e/ou repetitivo. A experiência adquirida ao resolver este tipo de exercícios permitia-me resolver as minhas tarefas muito rapidamente porque estava (tipicamente) perante problemas (mais fáceis ou mais difíceis) que já tinha enfrentado antes. Daí o ganho na produtividade.
Frequentemente, os meus superiores tinham de me arranjar outros projectos para me manter ocupado ("I have to find something to keep this guy busy"), enquanto que eles tentavam arranjar tempo para me fazerem code reviews :-)