• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

mogers

Maratona Inter-Universitária de Programação 2008

21 mensagens neste tópico

Chamada de Participantes

Caros colegas e amigos,

A Maratona Inter-Universitária de Programação (MIUP) é um concurso de programação para estudantes universitários que proporciona uma excelente oportunidade para estes testarem a sua capacidade de resolução de problemas. Para além do aspecto competitivo, a MIUP possibilita também o convívio e troca de experiências entre alunos e professores das Universidades e Politécnicos portugueses.

O concurso é disputado por equipas com (no máximo) 3 elementos e envolve uma prova de programação de 5 horas para resolução de 8 a 10 problemas com recurso às linguagens de programação C, C++, Java ou Pascal.

Os problemas são resolvidos num PC, disponível para cada equipa (com Linux e Windows disponúveis) e submetidos ao sistema de avaliação automática, Mooshak, desenvolvido na Universidade do Porto (http://mooshak.dcc.fc.up.pt/~zp/mooshak/). A classificação segue as normas do ICPC (International Collegiate Programming Contest), em que se ordenam as equipas por número de problemas resolvidos e, em caso de empate, pela soma dos tempos demorados na sua resolução. Também a eligibilidade dos concorrentes segue as normas ditadas por este organismo internacional (ver http://icpc.baylor.edu/icpc/regionals/eligibilitydecisiontree.pdf) .

A elaboração e escolha dos problemas originais está a cargo de uma comissão que engloba docentes de informática de todo o país:

- Filipe Araújo, Universidade de Coimbra

- Pedro Guerreiro, Universidade do Algarve

- Pedro Rangel Henriques, Universidade do Minho

- Luís Seabra Lopes, Universidade de Aveiro

- Ricardo Machado, Universidade do Minho

- Fábio Marques, Universidade de Aveiro

- Rui Mendes, Universidade do Minho

- Vasco Miguel Manquinho, Instituto Superior Técnico

- Arlindo Oliveira, Instituto Superior Técnico

- Luís Paquete, Universidade de Coimbra

- José Valente de Oliveira, Universidade do Algarve

- Francisco Câmara Pereira, Universidade de Coimbra

- André Restivo, Universidade do Porto

- Pedro Manuel Pinto Ribeiro, Universidade do Porto

- Fernando Silva, Universidade do Porto

- Paulo Sousa, Universidade de Lisboa

- Simão Melo e Sousa, Universidade da Beira Interior

- Delfim Torres, Universidade de Aveiro

Em cada edição da MIUP, tem se assistido a um grande entusiasmo e representatividade a nível nacional e a uma grande heterogeneidade nos problemas e nas equipas, de vários níveis, idades, vindas de várias instituições de ensino superior do país.

Este ano, a MIUP terá lugar no Departamento de Engenharia Informática da Universidade de Coimbra (FCTUC), situado no Polo II, a 25 de Outubro de 2008. A prova decorrerá as 10h e as 15h e o preço por equipa será de 45 euros. Cada instituição pode inscrever 2 equipas, havendo a possibilidade de inscrever uma terceira, em função da disponibilidade de lugares.

Vimos assim convidar-vos a participar na MIUP 2008. Estamos à vossa espera!

Pela MIUP'2008

Francisco Pereira

Quem vai participar na MIUP 2008?

Daqui do fórum, eu, o Drakcap e jcazevedo participamos na equipa Divide_N_Conquer (FEUP). O Warrior faz parte da equipa Theorem (FEUP). Quem mais? :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dia 25 é sábado... se houver prova online talvez participe, só para ter a noção de como funciona (mas claro que tentando fazer alguma coisa).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dia 25 é sábado... se houver prova online talvez participe, só para ter a noção de como funciona (mas claro que tentando fazer alguma coisa).

Same here! :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nice :P  Sim, costuma haver prova pública. Se for como no ano passado, imagino que consigam fazer 2-3 problemas pelo menos :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nice :)  Sim, costuma haver prova pública. Se for como no ano passado, imagino que consigam fazer 2-3 problemas pelo menos :P

Vai sonhando... Eu sou muito fraquinho! :P Ainda tenho de comer muita sopa!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podem resolver os do ano passado :P 

http://acm.ist.utl.pt/miup07/sessao2007/enX.html   em que X é a ordem do problema: de A a I.

Curiosamente eles tão praticamente por ordem de dificuldade (A é o mais fácil, I o mais dificil. A excepção é que o G é mais fácil do que o F :)) como podem ver pela classificação.

e a (SPOILER ALERT!) sessão de discussão dos problemas do prof Pedro Ribeiro. Que contem explicações sobre a resolução dos problemas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podem resolver os do ano passado :P 

http://acm.ist.utl.pt/miup07/sessao2007/enX.html   em que X é a ordem do problema: de A a I.

Curiosamente eles tão praticamente por ordem de dificuldade (A é o mais fácil, I o mais dificil. A excepção é que o G é mais fácil do que o F :)) como podem ver pela classificação.

e a (SPOILER ALERT!) sessão de discussão dos problemas do prof Pedro Ribeiro. Que contem explicações sobre a resolução dos problemas.

Já dou uma olhadela... Estou a acabar o USACO Contest! :P

EDIT: Só faltam 2 que não sei fazer optimamente, por isso, vou deixar de lado... :P Deixa lá ver os probs... :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tem lugar no próximo fim-de-semana a final nacional da Maratona Inter-universitária de Programação. Com transmissão online ao vivo a prova vai juntar 100 dos melhores programadores das escolas de engenharia informática de todo o país na resolução de 9 problemas que encontram na linguagem Java, Pascal, C ou C++ os veículos para serem resolvidos.

As trinta equipas que irão marcar presença na Faculdade de Ciências e Tecnologia da Universidade de Coimbra no sábado serão avaliados através do sistema automático Mooshak, de acordo com as normas do ICPC (International Collegiate Programming Contest).

À disposição dos participantes vão estar PCs com Linux e Windows a partir dos quais serão resolvidas as provas que abrem caminho à participação no SWERC - South Western European Regional Contest, uma prova internacional que reúne equipas do sudoeste da Europa, no próximo mês de Novembro.

A final da maratona inter-universitária tem lugar no departamento de engenharia informática do pólo II da FCTUC, entre as 10 e as 15 horas.

A organização garante que os desafios propostos aos concorrentes são de extrema complexidade. Os enunciados das provas foram redigidos por um grupo de investigadores de informática de várias instituições de ensino superior e baseiam-se em problemas reais.

http://mooshak.dei.uc.pt/~miup2008

http://swerc.eu/

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"100 dos melhores", essa é de rir, 100 dos que quiseram participar já que o único requisito é pertencer ao ensino superior ou ter pertencido no último ano.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Essa notícia tá pomposa :)  Como já tinha colocado aqui, vou participar.

A parte de ser uma "final" é que não percebo bem. Cada faculdade seleccionou as suas equipas por um critério a sua escolha, mas chamar a isto uma final... não houve eliminatórias :x

"100 dos melhores", essa é de rir, 100 dos que quiseram participar já que o único requisito é pertencer ao ensino superior ou ter pertencido no último ano.

É verdade a parte "100 dos que quiseram participar", mas na notícia diz que são alunos das "escolas" de engenharia informática. Não percebi essa parte do requisito...

Claro que estas provas não definem os melhores programadores. Isto é uma competição, é preciso gostar de estar sob pressão entre outras características. Conheço colegas muito bons no meu curso, mas que não participam porque não gostam de estar em competição.

A organização garante que os desafios propostos aos concorrentes são de extrema complexidade. Os enunciados das provas foram redigidos por um grupo de investigadores de informática de várias instituições de ensino superior e baseiam-se em problemas reais.

Esta parte é que não concordo. Talvez para o panorama nacional, os problemas sejam complicados, mas dizer de extrema dificuldade... não sei. Amanhã depois da prova posso dizer de minha justiça :)

Mas espero uma prova com muita qualidade. Pelo que sei, está a ser organizada com muito cuidado e os problemas estão +/- definidos desde julho o que dá para apanhar eventuais erros que costumam ser frequentes nas provas de treino universitárias.

edit: Fiquei foi muito admirado com a parte da transmissão online ao vivo  :eek:

edit2: ah, a transmissão online é só poder seguir no mooshak lol.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quando participei, juntamente com dois colegas, a minha universidade, ou politécnico neste caso, nem soube da nossa participação, fomos nós os 3 que pagamos os 40€ de inscrição e a gasolina para ir de Leiria até à Covilhã, por isso não houve grande critério de selecção :). Aliás, nós decidimos na quinta feira que no sábado íamos lá estar :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estou a participar e submeti para 2 problemas em que recebi Run Time Error... Não percebo porquê, mas pronto...

BTW, estive a programar em viagem, no carro... :)

Depois da prova, digam lá como correu e como é que se resolviam os probs... :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os vencedores (equipa de coimbra) fizeram "só" 5 problemas (o vencedor costuma fazer 6/7), o que atesta a dificuldade dos problemas. Os problemas foram um bocado mais dificeis do que o que esperava :) Mas tinha uns problemas giros. A solução do problema I surpreendeu-me bastante (depois tentem :)) :)

Nós (Divide_N_Conquer) fizemos 4 problemas e ficamos em 4º lugar. A equipa do Warrior, Theorem, também fez 4 problemas mas foi mais rápida e ficou em 3º lugar :P e os Lusco Fusco, também da FEUP ficaram em 2º.

A prova não correu muito bem à minha equipa. Muitas submissões erradas nos problemas. Temos que melhorar isso :P

O mais importante foi a qualificação para o SWERC em novembro :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Parabéns pela qualificação para o SWERC :cheesygrin:

Quanto ao concurso online, quando acordei já tinha começado e tive que sair a meio. Ainda fiz o problema mais fácil, mas não tive muita paciência para tentar mais problemas... Talvez fizesse o B (dijkstra?), o E (BFS; se não houvesse espaço DFS?) e, pouco provável, o A (ordenar os sets por número de elementos e arranjar uma forma eficiente de ver se um set está contido noutro, talvez com a função includes do stl set? - isto se percebi bem o problema, porque pelo que está escrito não percebi quase nada, foi só mesmo pela imagem).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Talvez fizesse o B (dijkstra?)

Sim, mas como os limites eram baixos (500x500) dava para fazer com bfs (como eu fiz e acho que a maioria fez com bfs). Basicamente, guardas o damage com que passas em cada posição e na bfs aceitas voltar a uma posição por onde já passaste se tiveres menos damage.

, o E (BFS; se não houvesse espaço DFS?)

O meu colega fez com bfs. Era suficiente porque não há muitos estados - 2^(3*3) = 512.

e, pouco provável, o A (ordenar os sets por número de elementos e arranjar uma forma eficiente de ver se um set está contido noutro, talvez com a função includes do stl set? - isto se percebi bem o problema, porque pelo que está escrito não percebi quase nada, foi só mesmo pela imagem).

O A era provavelmente o 2º problema mais fácil. O que nos levou tantas wrong answers e aos Theorem também, é que para nós a forma como o output era explicado dava a entender que as linhas do output deviam de vir por ordem lexicográfica. Mas não, a ordem dos conjuntos é que era lexicografica, ou seja: "1 5" vem antes de "1 10", coisa que se comparares como texto não é verdade.

Eram só 100 conjuntos, com 100 elementos. O(N^3) chega perfeitamente. Por isso, nem era preciso uma forma eficiente de ver se um conjunto está contido noutro. Usar o set era uma opção para um tempo melhor que o brute force (brute-force nisto chegava), mas como os sets já tão ordenados podes ver se o set mais pequeno está contido noutro em O( tamanho_conjunto_maior ) - já agora, o tamanho de um conjunto S, representa-se |S|.

Depois disto, precisavas de eliminar a transitividade. Também em N^3: para cada conjunto A, para todos os conjuntos B nos quais A está contido, se um conjunto C contém B, então também contém A, por isso elimina-se a ligação de A para C. Ou seja,  { 1 } está contido em { 1 , 2 } que está contido em { 1 , 2 , 3 }.

Os outros problemas eram bastante mais complicados. Posso dizer que no I, envolvia a geração de números aleatórios para se conseguir aproximar do resultado certo :x (e os vencedores tiveram a ideia certa! )

O C é um bocado complicado, até tive a ideia certa a 40 min do fim, mas não fui a tempo. Envolvia bastante código e a minha dfs estava a estourar a stack. Se tivesse conseguido colocar tudo o que queria no último artigo de grafos, até podiam tentar chegar lá :cheesygrin:

O D não li, mas acho que envolvia geometria a 3 dimensões.

O F era complicado de implementar. Era preciso uma estrutura de dados própria para se saber de forma eficiente que pontos estão a uma distância D de outro ponto. Tentei usar o set da stl mas não chega. Foi pena não ter na documentação que levamos uma implementação de uma Quadtree ou uma 2d-tree .

O G era de programação dinâmica. Pelos vistos um map da stl era suficiente para armazenar os resultados. Durante a prova pensei que um map não chegasse, mas também não sei bem se fazia o problema.

Quando a sessão de discussão de problemas do prof. Pedro Ribeiro tiver online, podem ver melhor :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estudantes da Universidade de Coimbra são os campeões da programação

Venceram a Maratona Inter-Universitária de Programação e vao representar Portugal, em Novembro, num concurso internacional

Uma equipa de estudantes da Universidade de Coimbra vai representar Portugal, em Novembro, num concurso internacional de programação de computadores, depois da vitória nacional conquistada no passado fim-de-semana.

A equipa do Departamento de Engenharia Informática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra (FCTUC), constituída pelos alunos Diogo Ferreira, João Oliveirinha e Pedro Correia, venceu a MIUP 2008 (Maratona Inter-Universitária de Programação).

A «Californication» conseguiu resolver cinco dos nove complexos problemas durante as cinco horas da prova, que tinha sido elaborada por um grupo de investigadores de informática de várias universidades e politécnicos portugueses e baseados em problemas reais que surgem nas empresas de informática ou na investigação.

A MIUP 2008 reuniu, no passado sábado em Coimbra, 100 dos melhores programadores das escolas de Engenharia Informática do país, agrupados em equipas, e envolveu a resolução de nove complexos problemas com recurso às linguagens de programação C, C++, Java ou Pascal.

«Os desafios eram altamente complexos. Os programadores foram confrontados com problemas que muitos engenheiros informáticos levariam vários dias a resolver», referiu o organizador da competição, Francisco Câmara Pereira, acrescentando que «ganhar uma MIUP, o principal evento de programação do país, é muito especial para o currículo de um programador, pois significa ter um leque alargado de empresas interessadas na sua contratação».

FEUP conseguiu segundo, terceiro e quarto lugares

A Maratona Inter-Universitária de Programação (MIUP) é um concurso de programação para estudantes universitários que proporciona uma excelente oportunidade de testarem a capacidade de resolução de problemas. Para além do aspecto competitivo, possibilita o convívio e troca de experiências entre alunos e professores das universidades e politécnicos portugueses, refere uma nota de imprensa da FCTUC.

Nesta competição classificaram-se em segundo, terceiro e quarto lugares equipas da Faculdade de Engenharia da Universidade do Porto, ficando no lugar imediato a Universidade do Minho. O Instituto Superior Técnico, de Lisboa, teve equipas nos 8º e 10º postos.

A equipa vencedora tem agora de enfrentar a SWERC ¿ South Western European Regional Contest, uma prova internacional que reúne equipas do sudoeste da Europa, a 23 de Novembro, em Nuremberga, Alemanha.

http://diario.iol.pt/tecnologia/programacao-universidade-estudantes-coimbra-miup-feup/1006520-4069.html

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A notícia está posta como sendo a MIUP a prova de apuramento para o SWERC, coisa que não é verdade. Cada universidade usa os resultados como quer, pois são as universidades que escolhem os seus representantes.

Faltava era uma noticia na tv :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já resolvi os problemas todos no pós-prova.

O D não era geometria a 3 dimensões, é praticamente ad-hoc. Os limites é que são um pouco justos.

O G é mais fácil do que parece e foi complicado implementar uma árvore em condições para o F :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora