Discussão Geral

TIUP 1ª etapa aftermath

 
Picture of Ricardo Silva
TIUP 1ª etapa aftermath
by Ricardo Silva - quarta, 29 março 2006, 9:49
 
Tão? foi bom?
Eu?
Re: TIUP 1ª etapa aftermath
by João Guerra Martins - quarta, 29 março 2006, 9:52
 
Heheheh, nem deu para um. Estava com esperanças, admito... raios partam as wrong answers! Hehe!

Como correu ao resto do pessoal? Pelo que ainda vi através do mooshak, só duas ou três equipas conseguiram submeter provas.


Quais escolheram fazer? Nós tentámos a E, mas parece-me que talvez a C tivesse sido mais fácil. Afinal de contas, houve 16 submissões aceites para essa tarefa.
Picture of Tiago Santos
Re: TIUP 1ª etapa aftermath
by Tiago Santos - quarta, 29 março 2006, 10:06
 
 A tão nao foi! Então os Guerreiros resolveram o D, submetemos faltava 1 min. Deu Compile Time Error. E nós: "Será que falta uma linha no fim em branco?". E faltava. Corrigimos mas o tempo acabou. lol

Conclusão: A culpa foi do Sequeira porque apagou a ultima linha sem dizer nada e o outro Guerreiro chegou no inicio da prova e já vinha cansado e não teve cabeça para aquilo. Para o próximo TIUP vou sozinho e tá ganho!! :-D


Tiago
Picture of Hélio Dolores
Re: TIUP 1ª etapa aftermath
by Hélio Dolores - quarta, 29 março 2006, 10:28
 
humm resolvemos o D... depois tinhamos mais de 1 hora para tentar resolver o resto... fizemos 2 soluções.. para o E e para o C (senão me engano)... ficaram essas 2 a 90%... deviamos ter apostado só num problema... se tivessemos mais um PC.. :-/
... não foi mal de todo.. vamos ver  no proximo! =)

é no IST temos que ganhar! B-)
Picture of Gil Costa
Re: TIUP 1ª etapa aftermath
by Gil Costa - quarta, 29 março 2006, 11:37
 

Gostei do problema D (áreas)
Esse e o E eram os mais acessíveis. O C resolvia-se bem com gráfos (digo eu, q não sei nada de grafos misturado), mas isso só se dá no 3º ano.

Bom, não submetemos nenhum, as decisões no momento não foram as mais acertadas (pois + um pc é q era...), faz parte do "jogo". Mas demos luta e não estivemos mal.

Axo que a experiência foi positiva para todos! E pró mês q vem há mais frio  ;)

Eu?
Re: TIUP 1ª etapa aftermath
by João Guerra Martins - quarta, 29 março 2006, 11:54
 
Vai haver falta de participação dos alunos do primeiro ano... há teste de física. Talvez dê para aparecer na última horita, mas não deve dar para nada. Gostava de tentar de qualquer maneira se fosse possível.

Quanto à C... hmm, estava para aqui a pensar, a matriz não era muito díficil de fazer, acho eu, e depois disso não se podia fazer aquilo com uma função recursiva? Tipo, corre-se a função com argumento de uma coordenada, e ele vai verificar todos os pontos que são 1 à volta, e chama a própria função para esse ponto.

Teríamos de manter um vector com o percurso percorrido, de modo a não andarmos às voltinhas, mas os ciclos todos podiam parar assim que, às tantas chamadas da função, a coordenada onde tivéssemos sido levados estivesse na última linha.

Alguém implementou algo assim? Não demos matéria nenhuma em relação a isto, mas acho que talvez funcionaria assim! Dicas?
Picture of Hélio Dolores
Re: TIUP 1ª etapa aftermath
by Hélio Dolores - quinta, 30 março 2006, 12:00
 
sim recursivamente era boa ideia =) ... podes reparar num pormenor.. eles diziam que o ponto superior esquerdo aparecia sempre =P era esse o argumento da chamada inicial da função. :-)
Picture of Gil Costa
Re: TIUP 1ª etapa aftermath
by Gil Costa - quinta, 30 março 2006, 12:18
 

O ano passado em P2 houve um problema bastante parecido a este, o único que não consegui ter aceite. Nesta prova nem o tentei fazer mesmo por caisa disso. Reparaste nas dimensões máximas da matriz? Agora percorre-a recursivamente vezes e vezes até encontrares o melhor caminho! No problema do ano passado tentei fazer isso da fórma mais eficiente que consegui (mais ou menos como sujeres mas com umas optimizações..) e tive sempre time limit excedded.

Acredito que a solução passe pela recursividade, mas se já a minha solução não era imediacta e era de alguma eficiência (o melhor que soube inventar), a solução para o problema ou se pensa mesmo bem no assunto ou já se deu grafos...

Picture of Hélio Dolores
Re: TIUP 1ª etapa aftermath
by Hélio Dolores - quinta, 30 março 2006, 12:37
 
Ha muitas formas de resolveres o problema do TLE...
- checkpoints
- apagar caminhos inuteis
- flags
- etc...
mas segue a sugestão do ardoRic e dá uma olhada nos percursos em grafos (profundidade e largura).
Geralmente este tipo de problemas resolvem-se recursivamente e são faceis de identificar.
Picture of Ricardo Silva
Re: TIUP 1ª etapa aftermath
by Ricardo Silva - quinta, 30 março 2006, 12:16
 
Não valia a pena pensares em grafos (se bem que na realidade era um grafo).

Podias, como disse o colega, percorrer directamente o array com uma função recursiva.

Como o colega também disse, é claro que tem de haver algum cuidado para não se repetir caminho (senão a função recursiva andava para ali eternamente (ou até a stack acabar)).

Já agora, fazendo isto assim, o que se está a fazer é uma pesquisa em profundidade sobre o 'grafo', em que procuramos uma ligação entre a primeira linha e a ultima. Não bastava começar só no (1,1) (ou (0,0)), tem de se chamar a função para todos os pontos da primeira fila. Qualquer forma de percorrer o grafo era possivel (em largura, com heuristica, etc) mas achei a em profundidade mais simples, porque facilmente se faz numa função recursiva.

O código, com alguns truquezinhos de ultima hora para evitar check-bounds, ficou bastante simples, e se o professor estiver de acordo, posso disponibiliza-lo a quem quiser. (Até comento, para ajudar a compreensão do que se passa).
Picture of Gil Costa
Re: TIUP 1ª etapa aftermath
by Gil Costa - quinta, 30 março 2006, 12:26
 
Pensei que eras contra a exposição de soluções..
Mas axo que este caso seria interessante, até porque já o tentei uma vez o ano passado (similar). É boa altura para rever aquele problema e ver porquê que a minha implementação falhou.
Picture of João Rico
Re: TIUP 1ª etapa aftermath
by João Rico - quinta, 30 março 2006, 12:23
 
olhei pro C axei facil.. depois deramme a D p+ras maos.. pareceu facil.. mas blokeamos kuando xegamos ao calculo da area... nao conseguimos la chegar..

tou a pensar em fazer os problemas em casa... ^^ e incrivelmente o VS foi meu amigo e nao deu erros nenhuns... XDXD

proxima etapa tou la.. desde que nao coincida com nenhum teste ..
Picture of Ricardo Silva
Re: TIUP 1ª etapa aftermath
by Ricardo Silva - quinta, 30 março 2006, 9:56
 
Epah... não correu mesmo nada como esperavamos/queriamos...
Não conseguimos terminar nenhum dos problemas, apesar de estarmos perto da resolução de 2 deles e mais um a meio... enfim... na próxima recuperamos, vamos melhor preparados (foi a "estreia" de dois dos membros da equipa neste ambiente tambem...) e compensamos pelo 'desire' desta 1ª ronda (or so we hope)

Ricardo Silva
Caparica Xenomorphs
Eu?
Re: TIUP 1ª etapa aftermath
by João Guerra Martins - quinta, 30 março 2006, 6:04
 
Nada de soluções por enquanto!:D

Quero tentar fazer isso depois!

Já agora, acho que de repente cheguei ao das áreas. Então, para se ver se era poligono, era ver se chegado ao fim da string, a nova posição estava adjacente à inicial.

Depois... hmm, se se conseguisse meter aquilo para dentro de uma matriz (provavelmente nem é preciso), poder-se ia contar o número de "quadradinhos" entre dois pontos por onde passou a "caneta".

Não era assim tão terrível.


Realmente, Gil, tens razão. Com os tamanhos que eles dão, recursivamente a percorrer tudo é para esquecer. Mas na volta pode-se "apagar" todas as entradas que não levem a mais lado nenhum que o anterior. Ou seja: chama-se a função com a primeira entrada, e no fim de cada chamada à função, apaga-se o quadrado onde se estava. Assim por onde quer que ele vá, acaba por apagar o caminho. Assim escusamos de os repetir se tivermos matrizes que cruzam caminhos diferentes.

Isto é bué fixe:D
Picture of Gil Sousa
Re: TIUP 1ª etapa aftermath
by Gil Sousa - quinta, 30 março 2006, 6:13
 
Boas!

João sobre a parte de saber se é poligono..., basta isto:

numero de lefts == numero de rights
numero de ups == numero de downs

Se ele andar para a esquerda terá de voltar para a direita (voltar ao ponto inicial), tal como terá de acontecer na vertical..., bastava esta condição e tinhas o comprovativo de poligono ;)

abraços, Gil
Picture of Ricardo Silva
Re: TIUP 1ª etapa aftermath
by Ricardo Silva - quinta, 30 março 2006, 6:57
 
dulllrrr <- é um poligono ? a mim parece-me uma linha ...
Picture of Tiago Santos
Re: TIUP 1ª etapa aftermath
by Tiago Santos - quinta, 30 março 2006, 7:18
 
 Ta bem visto! O que nós fizemos foi começar na origem e ver se no fim acabamos na origem. Assim se o comando fosse 'd' faziamos x-0 e y-1, 'u' faziamos x-0 e y+1, 'l' faziamos x-1 e y-0 e 'r' faziamos x+1 e y-0. No fim tinha que dar (0,0). Mas pensando melhor só isso nao chegava...


Tiago
Eu?
Re: TIUP 1ª etapa aftermath
by João Guerra Martins - quinta, 30 março 2006, 8:54
 
Eu estava a sugerir algo como uma matriz (array bidimensional) porque o ponto final não precisava obrigatóriamente de estar no ponto inicial, podia estar em qualquer uma das coordenadas adjacentes que ainda contava como poligono, não?

Depois, com o vector bidimensional, seria facil percorrer todas as linhas e descobrir a área, mas ocupava-se muita memória com o vector todo (apesar de poder ser apenas vector de bool's).

Talvez mais eficiente fosse apenas escrever um vector de pares com todas as coordenadas, começando em (0, 0) por onde a 'caneta' tivesse passado, ordená-lo, e depois fazer cálculos bem rápidos sobre quantos pontos em cada linha. Mas tenho impressão que já disseram isto aqui.blush

De qualquer maneira há sempre casos particulares a "irritar":D
Picture of Hélio Dolores
Re: TIUP 1ª etapa aftermath
by Hélio Dolores - quinta, 30 março 2006, 9:35
 

Bem.. eu não quero para já dar a solução para o problema (até porque vai aparecer no concurso de p2 e perde a piada toda =P )

..em principio nao vao ter problemas de memoria, estejam descansados. penso que a ordenação não vos vai ajudar em nada, basta pensarem que com os mesmos traços conseguem figuras com areas diferentes (experimentem desenhar).
=)

Picture of Gil Costa
Re: TIUP 1ª etapa aftermath
by Gil Costa - sábado, 1 abril 2006, 2:47
 

dulllrrr <- é um poligono ? a mim parece-me uma linha ...

Ricardo, nota que "the pencil did not cross a previously drawn segment". Logo não existem casos onde se volte para traz (du, ud, rl e lr não existem), isso seria passar por cima do que já existe.

Picture of Tiago Santos
Re: TIUP 1ª etapa aftermath
by Tiago Santos - quinta, 30 março 2006, 6:27
 
    Era bem mais fácil do k isso. Desenha o poligno numa folha. Se contares o numero de vezes que sobe e desce tens o numero de quadrados. Quando andas mais do k uma vez para um lado (esquerda ou direita) guardas numa variável auxiliar. Quando voltares a subir ou descer somas o valar da variável auxiliar ao k já tinhas. Foi pena ter chegado à solução no ultimo minuto e ter submetido sem uma linha em branco no fim do ficheiro.  xx-P


Tiago
Picture of Gil Costa
Re: TIUP 1ª etapa aftermath
by Gil Costa - quinta, 30 março 2006, 7:16
 

Quando o concurso reabrir para o público (se é que ainda não abriu) tenta submeter a ver se a tua ideia estava correcta. (aliaz, este problema tb vai estar em P2 na próxima semana).

Penso que o cálculo da área não é imediacto. Durante a prova cheguei a um algoritmo geral que resultava teóricamente em qualquer caso (fiz desenhos de poligonos o mais estranhos possíveis e resultava em todos). Pena não ter implementado em tempo útil.
Mas não vou dizer nada em relação à minha ideia, tirava a piada de cada um descobrir por si.

Picture of Ricardo Silva
Re: TIUP 1ª etapa aftermath
by Ricardo Silva - quinta, 30 março 2006, 7:08
 
Quanto ao problema C, foi mais ou menos a isso que reduzimos o problema. Percorrer (sim, recursivamente ...) e ir 'apagando' os caminhos. Pode olhar-se para o que fizemos assim, pode.

Mas reparem ... dava para fazer recursivamente (tanto que nós fizemos).