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 Ti (em dias) e um valor Vi. 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 ≤ Ti ≤ N; 1 ≤ Vi ≤ 100,000. Como resolver o problema de forma eficiente?
segunda-feira, 21 de outubro de 2013
quarta-feira, 16 de outubro de 2013
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(N2) precisa apenas de uma pequena alteração para contar os pares:
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 1000002 é 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().
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.
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:
Para começar, a abordagem O(N2) 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 1000002 é 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).
domingo, 13 de outubro de 2013
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:
A notação Ó-grande significa que o tempo de execução do algoritmo é no máximo proporcional a N2.
Agora o desafio é: como fazer melhor para podermos suportar mais de 10000 números?
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(N2).
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 N2.
Agora o desafio é: como fazer melhor para podermos suportar mais de 10000 números?
sexta-feira, 11 de outubro de 2013
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++:
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 = (N2 - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,
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 * 109 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(N2), o nosso programa pode processar √108 = 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(N2)?
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 :-)
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 = (N2 - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,
- O((N2 - N) / 2) = O(N2 / 2), ignoramos o factor N porque este é dominado pelo factor N2
- O(N2 / 2) = O(N2), ignoramos o factor 1/2 visto que é uma constante.
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 * 109 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(N2), o nosso programa pode processar √108 = 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).
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(N2)?
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 :-)
Subscrever:
Mensagens (Atom)