Discussão Geral

TIUP 1ª etapa aftermath

TIUP 1ª etapa aftermath

by Ricardo Silva -
Number of replies: 22
Tão? foi bom?
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by João Guerra Martins -
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.
In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Tiago Santos -
 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
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Hélio Dolores -
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-)
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Gil Costa -

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  ;)

In reply to Gil Costa

Re: TIUP 1ª etapa aftermath

by João Guerra Martins -
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?
In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Hélio Dolores -
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. :-)
In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Gil Costa -

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...

In reply to Gil Costa

Re: TIUP 1ª etapa aftermath

by Hélio Dolores -
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.
In reply to Gil Costa

Re: TIUP 1ª etapa aftermath

by Ricardo Silva -
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).
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Gil Costa -
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.
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by João Rico -
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 ..
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Ricardo Silva -
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
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by João Guerra Martins -
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
In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Gil Sousa -
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
In reply to Gil Sousa

Re: TIUP 1ª etapa aftermath

by Ricardo Silva -
dulllrrr <- é um poligono ? a mim parece-me uma linha ...
In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Tiago Santos -
 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
In reply to Tiago Santos

Re: TIUP 1ª etapa aftermath

by João Guerra Martins -
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
In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Hélio Dolores -

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).
=)

In reply to Ricardo Silva

Re: TIUP 1ª etapa aftermath

by Gil Costa -

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.

In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Tiago Santos -
    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
In reply to Tiago Santos

Re: TIUP 1ª etapa aftermath

by Gil Costa -

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.

In reply to João Guerra Martins

Re: TIUP 1ª etapa aftermath

by Ricardo Silva -
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).