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?
Mostrar mensagens com a etiqueta concursos de programação. Mostrar todas as mensagens
Mostrar mensagens com a etiqueta concursos de programação. Mostrar todas as mensagens
quinta-feira, 5 de dezembro de 2013
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.
segunda-feira, 21 de outubro de 2013
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 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?
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?
quarta-feira, 18 de setembro de 2013
Preparação para concursos de programação
Estamos no início do ano lectivo e isso também significa que a nova temporada de concursos de programação (mais escolares) também está prestes a iniciar-se.
Os alunos do ensino básico e secundário são elegíveis para as Olimpíadas Nacionais de Informática (ONI) e têm a hipótese de serem seleccionados para representar Portugal nas Internacionais, International Olympiad in Informatics (IOI) 2014, em Taiwan. Por seu turno, os alunos universitários poderão competir na Maratona Inter-Universitária de Programação (MIUP) já em Outubro, de modo a qualificarem-se para o South Western European Regional Contest (SWERC), concurso da nossa zona europeia que permite o acesso à final mundial do International Collegiate Programming Contest (ICPC) da ACM.
Independentemente do nível de ensino, a pré-condição fundamental para participar é saber programar. A maioria dos concursos suportam as linguagens C, C++, Java e Pascal. Assim, o primeiro passo é escolher uma delas, estudá-la e praticar para se ser tão proficiente quanto possível.
O C++ é a linguagem mais popular e é a minha linguagem favorita. No entanto, um dos "erros" mais comuns é a falta de conhecimento da Standard Template Library, particularmente os diversos algoritmos já disponíveis na biblioteca algorithm (sort, lower_bound, upper_bound, next_permutation, etc).
Os problemas colocados nestas provas devem ser resolvidos com um programa desenvolvido pelos concorrentes. Para além destes programas serem obrigados a dar as respostas correctas, existem também restrições quanto ao tempo disponível para calcular as respostas e à memória (do computador) disponível.
Assim, os concorrentes devem encontrar as ideias certas para resolver os problemas de forma eficiente, isto é, encontrar o Algoritmo certo para resolver os problemas e implementá-lo usando uma linguagem de programação.
Infelizmente, não conheço muitos recursos em português apropriados para a aprendizagem de algoritmos. As ONI criaram um espaço chamado Academia ONI que contém alguns artigos: "Noções Básicas de Análise de Algoritmos", "Tipos de Problemas" comuns em concursos e "Pesquisa Completa" de soluções. O forum Portugal-a-Programar contém uma secção de Algoritmia e Lógica, da qual recomendo um artigo sobre Grafos.
Dada esta escassez, convém dominar o inglês e explorar tanto os livros como a internet.
A Ciência da Computação é uma área muito vasta. Existem diversos tipos de algoritmos diferentes. Este conhecimento está tipicamente melhor estruturado nos bons livros:
Contudo, muitas vezes, quem está a começar nestas coisas não tem ainda vontade de estudar um livro, especialmente os mais jovens (eu também não tinha!). Existem outros tipos de recursos:
À medida que os conhecimentos são adquiridos e fortalecidos, é importante exercitar estes conhecimentos. Existem diversos judges online como o Sphere Online Judge. Estes judges disponibilizam um conjunto vasto de problemas e os utilizadores podem resolve-los livremente como treino.
Além dos judges, existem outros sites como o TopCoder, o Codeforces e o CodeChef que organizam competições de treino (normalmente há pelo menos 1 por semana) e é publicado um editorial depois de cada concurso que explica como se poderiam resolver os exercícios.
O post já vai longo, mas já deu certamente para perceber uma coisa: é preciso trabalho, trabalho, trabalho. Tal como em tudo na vida, não existem fórmulas mágicas. No entanto, quem corre por gosto, não cansa :-)
Os alunos do ensino básico e secundário são elegíveis para as Olimpíadas Nacionais de Informática (ONI) e têm a hipótese de serem seleccionados para representar Portugal nas Internacionais, International Olympiad in Informatics (IOI) 2014, em Taiwan. Por seu turno, os alunos universitários poderão competir na Maratona Inter-Universitária de Programação (MIUP) já em Outubro, de modo a qualificarem-se para o South Western European Regional Contest (SWERC), concurso da nossa zona europeia que permite o acesso à final mundial do International Collegiate Programming Contest (ICPC) da ACM.
Independentemente do nível de ensino, a pré-condição fundamental para participar é saber programar. A maioria dos concursos suportam as linguagens C, C++, Java e Pascal. Assim, o primeiro passo é escolher uma delas, estudá-la e praticar para se ser tão proficiente quanto possível.
O C++ é a linguagem mais popular e é a minha linguagem favorita. No entanto, um dos "erros" mais comuns é a falta de conhecimento da Standard Template Library, particularmente os diversos algoritmos já disponíveis na biblioteca algorithm (sort, lower_bound, upper_bound, next_permutation, etc).
Os problemas colocados nestas provas devem ser resolvidos com um programa desenvolvido pelos concorrentes. Para além destes programas serem obrigados a dar as respostas correctas, existem também restrições quanto ao tempo disponível para calcular as respostas e à memória (do computador) disponível.
Assim, os concorrentes devem encontrar as ideias certas para resolver os problemas de forma eficiente, isto é, encontrar o Algoritmo certo para resolver os problemas e implementá-lo usando uma linguagem de programação.
Infelizmente, não conheço muitos recursos em português apropriados para a aprendizagem de algoritmos. As ONI criaram um espaço chamado Academia ONI que contém alguns artigos: "Noções Básicas de Análise de Algoritmos", "Tipos de Problemas" comuns em concursos e "Pesquisa Completa" de soluções. O forum Portugal-a-Programar contém uma secção de Algoritmia e Lógica, da qual recomendo um artigo sobre Grafos.
Dada esta escassez, convém dominar o inglês e explorar tanto os livros como a internet.
A Ciência da Computação é uma área muito vasta. Existem diversos tipos de algoritmos diferentes. Este conhecimento está tipicamente melhor estruturado nos bons livros:
- O meu preferido é o Introduction to Algorithms. Este pode ser considerado uma bíblia e é um pouco difícil de seguir mas é um recurso fenomenal.
- O Programming Challenges é um livro escrito especialmente para concursos e é encontrado facilmente online.
- Na disciplina de algoritmos na faculdade, era recomendado o Data Structures and Algorithm Analysis in C++, este não é tão completo mas o autor é bastante claro nas suas explicações.
- Outro livro muito recomendado é o Algorithm Design Manual, mas não o conheço.
Contudo, muitas vezes, quem está a começar nestas coisas não tem ainda vontade de estudar um livro, especialmente os mais jovens (eu também não tinha!). Existem outros tipos de recursos:
- O programa de treino da USACO é uma plataforma de treino para as olimpíadas de informática. Não conheço melhor recurso online para aprender algoritmos e estruturas de dados. Está dividido por módulos que contêm tanto textos de apoio como exercícios para aplicar os conhecimentos transmitidos nesses textos.
- Tutoriais curtos e objectivos. Eu recomendo vivamente os artigos referidos anteriormente em português, assim como os tutoriais do TopCoder.
- Existem cada vez mais cursos online. A disciplina de desenho e análise de algoritmos da Universidade de Stanford é oferecida no Coursera, estando dividida em parte 1 e parte 2.
À medida que os conhecimentos são adquiridos e fortalecidos, é importante exercitar estes conhecimentos. Existem diversos judges online como o Sphere Online Judge. Estes judges disponibilizam um conjunto vasto de problemas e os utilizadores podem resolve-los livremente como treino.
Além dos judges, existem outros sites como o TopCoder, o Codeforces e o CodeChef que organizam competições de treino (normalmente há pelo menos 1 por semana) e é publicado um editorial depois de cada concurso que explica como se poderiam resolver os exercícios.
O post já vai longo, mas já deu certamente para perceber uma coisa: é preciso trabalho, trabalho, trabalho. Tal como em tudo na vida, não existem fórmulas mágicas. No entanto, quem corre por gosto, não cansa :-)
Subscrever:
Mensagens (Atom)