Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

pcaldeira

TIUP 2010

Mensagens Recomendadas

pcaldeira

Apesar de não haver informação no site do evento, o TIUP 2010 foi confirmado e já existem datas para 2 das 4 provas que vão constituir o torneio este ano. A MIUP será em Évora, em Outubro.

Mais info em http://acm.ist.utl.pt/tiup/calendario.php

Eu e o pedrosorio vamos participar em equipa, provavelmente com mais um elemento cá do IST. Já está também inscrita a equipa Mess, com o vbmaster, triton e João Guerreiro. Mais alguém cá do p@p?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Para já, estou a pensar participar sozinho durante este semestre, visto que não devo poder participar no próximo ano.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Eu estou na alemanha para participar no robocup - german open, por isso não participo :x


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Como é que correu? Não sei onde é que estão os resultados...


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Como é que correu? Não sei onde é que estão os resultados...

Ganharam os Mess, 3 problemas resolvidos (também não sei onde estão os resultados lol).


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

E vocês?

Nós fomos fraquinhos, só resolvemos 1. Havia 2 triviais, um porque sim, o outro porque podias usar um algoritmo que supostamente não devia passar no tempo com aqueles limites.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Participei praticamente sozinho, o ivo (somos só dois) chegou quando já tinha resolvido 2..

O A era perfeitamente solúvel, só que horrivelmente chato. Não me admira que ninguém o tenha resolvido, não por ser difícil, mas porque dava um trabalho tremendo.

O B foi o que quase toda a gente resolveu, mas também era chatinho..

O C era DP, cheguei a casa e lembrei-me da solução.. típico.

O D era engraçado. Não sei como resolveu a maior parte das pessoas, eu usei o KMP para resolver em O(n^2 * log n), completamente dentro do worst case possível.

O E é o género de problemas que eu odeio. Não me admira que os Mess tenham sido os únicos a resolver. Congratz ao João Guerreiro (suponho que tenha sido ele a resolve-lo, parece taylor-made).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Triton

O A era perfeitamente solúvel, só que horrivelmente chato. Não me admira que ninguém o tenha resolvido, não por ser difícil, mas porque dava um trabalho tremendo.

Pelo que reparei nas equipas da minha sala, ninguém resolveu o A porque o processamento de input era bastante chato. Só no fim é que reparei que se pode usar Python, talvez seja mais fácil neste género de problemas. Curiosamente a solução do Judge foi em Perl (pelo que apareceu no Mooshak).

O E é o género de problemas que eu odeio. Não me admira que os Mess tenham sido os únicos a resolver.

Congratz ao João Guerreiro (suponho que tenha sido ele a resolve-lo, parece taylor-made).

Sim, foi ele que resolveu esse.


<3 life

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

O D era engraçado. Não sei como resolveu a maior parte das pessoas, eu usei o KMP para resolver em O(n^2 * log n), completamente

Não sei se é pelo facto de agora suportarem cada vez mais linguagens alternativas, o que pode levar a que tenham um time limit fixo independente da linguagem, mas a solução O(N^3) passou nas calmas e foi feita por nós em uns 10 minutos ou menos.

Btw, a nossa equipa (Mess) teve uma alteração, saíu o quickfire e entrou o triton, matenho-me eu e o joao guerreiro. :thumbsup:

P.S.: qual era o nome da vossa equipa?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pcaldeira

Não sei se é pelo facto de agora suportarem cada vez mais linguagens alternativas, o que pode levar a que tenham um time limit fixo independente da linguagem, mas a solução O(N^3) passou nas calmas e foi feita por nós em uns 10 minutos ou menos.

Btw, a nossa equipa (Mess) teve uma alteração, saíu o quickfire e entrou o triton, matenho-me eu e o joao guerreiro. :thumbsup:

P.S.: qual era o nome da vossa equipa?

Provavelmente os testes para esse problema eram fracos (diz o Warrior que é habitual no TIUP). Experimenta um teste com o pior caso e vê o tempo.

Já agora, estivémos a discutir o problema C no MSN e parece mesmo difícil. Se as caixas se pudessem repetir, a solução era feita com programação dinâmica, mas como não podem, o problema torna-se muito mais complicado.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

Btw, o problema E não foi tailor made porque já existem mais equipas com matemáticos aqui no IST (os não sei quê do Martelo), que também resolveram esse...

----

Sim, eu sei que a TIUP tem limites leves, nem me estava a vangloriar do desenrascanso do N^3... São estas cenas que provam na MIUP quem é que percebe mesmo do assunto.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Eu quando disse isso obviamente que não era "feito especialmente para vocês" mas mais no sentido que gostam de problemas de matemática (e estão habituados e percebem disso) ao contrário da maioria das equipas.

O problema do n^3 é que se a string for toda ela igual (como 1000 'a's consecutivos), nunca na vida passas no tempo limite de 1 segundo.

E não me parece que o uso de outras linguagens seja desculpa, porque n^3 é aproximadamente 100x mais lento do que n^2*log n, e nenhuma linguagem usada tem essa desvantagem relativamente a outra..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Pedro Ribeiro

Sim, eu sei que a TIUP tem limites leves, nem me estava a vangloriar do desenrascanso do N^3... São estas cenas que provam na MIUP quem é que percebe mesmo do assunto.

A única coisa que posso prometer é que enquanto eu for membro do Comité Científico da MIUP, se tiver o mínimo de tempo disponível, irei sempre tentar resolver todos os problemas e precisamente tentar apontar casos onde o limite não esteja ajustado à complexidade que se deseja para a solução: no caso deste problema, ou se baixava o limite para todos perceberem que O(N^3) passava, ou então usavam-se casos a tentar explorar todos os limites garantindo que O(N^3) não passava.

Nas TIUPs, os comités científicos são apenas locais. E este tipo de coisas começará a "melhorar" precisamente quando começaram a haver mais ex-concorrentes a ajudar, porque saberão o que é realmente estar do outro lado e quais são os pormenores (pormaiores) com que interessa ter muito cuidado.

Em todo o caso, o meu conselho como antigo concorrente, em qualquer concurso, é estar atento a quem vai resolvendo e se virem que tal, submetam solução que "não deveria passar" mas afinal passa. Se ganhasse um tostão de cada vez que me aconteceu isso em concurso... estava rico :thumbsup:

Finalmente, quero apenas dizer que criar os testes "ideais" é ainda uma "black art". Não é de todo fácil e nem todos os problemas se prestam a isso. Existem vários artigos científicos a falar disso, por exemplo: http://people.ksp.sk/~misof/publications/2006testing.pdf ("On the suitability of programming tasks for automated evaluation", escrito pelo misof)

Se tiverem curiosidade espreitem vários artigos científicos sobre competições de informática, nomeadamente Olimpíadas: http://www.mii.lt/olympiads_in_informatics/contents.htm

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Edo

Pois. Nós não submetemos o D antes porque não acreditámos que o N^3 passasse. Só depois de vermos as outras equipas a submete é que resolvemos arriscar.

O A pareceu-me ser brute force. Ainda começei a escrever uma solução mas depois fiquei aborrecido e não acabei (é o que acontece depois de se andar muito tempo no prolog).

Quanto ao E, bem nós não tinhamos nenhum matemático na equipa por isso passámos a frente.

O C também não resolvemos mas vou tentar um topological sort ou assim.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
hugopeixoto

Implementei isso como sendo a Longest Common Substring entre a string e ela própria, com uma modificação para forçar a que sejam disjuntas.

Assim por alto, a implementação foi qualquer coisa deste género:

for (int i = 0; i < n; i++)
  for (int j = i+1; j < n; j++)
    if (s[i] == s[j] && j-i > dp[i][j])
      dp[i+1][j+1] = 1 + dp[i][j]
    else
      dp[i+1][j+1] = 0

Ali dentro do if guardava sempre o máximo dp[i+1][j+1] e o maximal i para no fim saber qual o maior valor.

Partilhar esta mensagem


Ligação 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

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.