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

Baderous

1º. Concurso de Programação Portugal-a-Programar - Discussão

50 mensagens neste tópico

Tópico de Discussão do 1º. Concurso Aberto de Programação Portugal-a-Programar

Este tópico está reservado à discussão do ProblemSet e soluções dos problemas por parte dos users.

Os criadores dos problemas não avançarão com análises nem soluções neste tópico porque a análise completa será lançada em breve.

Regras:

- O código tem de ser incluído no proprio fórum através de Geshi, e não de links (que se podem quebrar) ou no Pastebin do P@P com a opção Guardar Para Sempre;

- Cada solução (independentemente dos comentários) deve ser acompanhada de um texto a explicar por alto.

Start your discussion! :D

(Tharis)


Foquei-me principalmente nos dois problemas mais difíceis, o D e o C, e apesar de não ter conseguido resolver completamente nenhum deles, penso que não estive muito longe e ainda aprendi alguma coisa. Venha o próximo! :thumbsup:

O C?!?! Esse era o mais fácil!! Foi o único que eu fiz! xD Também só me lembrei de ver que existiam outros problemas para além do A, quando o mogers postou o link ali atrás :x

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O C?!?! Esse era o mais fácil!! Foi o único que eu fiz! xD Também só me lembrei de ver que existiam outros problemas para além do A, quando o mogers postou o link ali atrás :x

Caro Baderous, a tua solução resolve o problema com 500,000 pessoas em menos de 1s? :thumbsup:

Era isso a que o pcaldeira se estava a referir quando falava na dificuldade. Não no simples facto de fazer um programa que resolva correctamente, mas de forma pouco eficiente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tsc tsc, tou pa ver.... :thumbsup:

3 do CIC nos 15 primeiros. nada mau na minha opiniao :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

3 do CIC nos 15 primeiros. nada mau na minha opiniao :thumbsup:

Permite-me discordar. 3 do CIC que pelo menos passaram nos Sample Inputs. Aquela não é a classificação final, os testes a que os programas estavam sujeitos eram os Sample Inputs. Hoje ou amanhã sai a classificação final com os programas testados por todos os testes.

EDIT

Mas por favor, usem o tópico de discussão de problemas para o seu efeito. Este tópico não é para discutir os problemas nem resoluções.

http://www.portugal-a-programar.pt/forums/topic/0-find-topic/?do=findComment&comment=240160

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Caro Baderous, a tua solução resolve o problema com 500,000 pessoas em menos de 1s? :thumbsup:

Era isso a que o pcaldeira se estava a referir quando falava na dificuldade. Não no simples facto de fazer um programa que resolva correctamente, mas de forma pouco eficiente.

Isso aí já é outra coisa :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ora bem... para começar vou colocar aqui a minha solução do F (que não tenho tempo agora para explicar todas), que gostaria de saber, se alguém me conseguisse dizer, exactamente se usei algum método conhecido, embora não tenha tido consciência disso.

F - http://paste.portugal-a-programar.org/pastebin.php?show=3093

Basicamente o que fiz foi, receber todas os dados de um caminho até que não houvessem mais (já que não era dada informação sobre isso). Depois, como queríamos os caminhos desde o 1 ao N, o que fiz foi: Para cada caminho a -> b de peso x, em que a == 1 procurava um outro caminho b -> c de peso y. Ou seja, um caminho que tivesse como origem o destino do primeiro caminho analisado. Tendo um caminho a->b(x) e b->c(y) adicionava ao fim do array de caminhos um caminho a->c(x+y). Fazia isto para todos os caminhos começados em 1. No final ordenei o array de caminhos de modo a que em cima ficasse os caminhos 1->N e de menor peso. Depois era só printar o caminho percorrido que ia sendo actualizado cada vez que se adicionava um novo caminho ao final do array.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não bastava fazer um Djisktra Shortest Path, onde a origem fosse 1 e o destino fosse o N, recolhendo os vértices e os pesos, apresentando o resultado no fim? Eu esse vi já no fim, mas pareceu-me que era esta a resolução.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não bastava fazer um Djisktra Shortest Path, onde a origem fosse 1 e o destino fosse o N, recolhendo os vértices e os pesos, apresentando o resultado no fim? Eu esse vi já no fim, mas pareceu-me que era esta a resolução.

Sim, podia ser... Mas existe outro algoritmo do tipo muito mais fácil e rápido de implementar, que funciona porque o limite é pequeno.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não bastava fazer um Djisktra Shortest Path, onde a origem fosse 1 e o destino fosse o N, recolhendo os vértices e os pesos, apresentando o resultado no fim? Eu esse vi já no fim, mas pareceu-me que era esta a resolução.

Pois, eu o Djisktra nunca implementei, mas acho que o meu algoritmo é bastante lógico e não sei se não é um Djisktra modificado, porque ao que sei, o próprio Djisktra é algo bastante óbvio, ou pelo menos, o que alguém faria se tivesse de resolver o problema "manualmente".

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, podia ser... Mas existe outro algoritmo do tipo muito mais fácil e rápido de implementar, que funciona porque o limite é pequeno.

Podias ter dito qual era :x

vbmaster, podes ver na edição 12 da revista Programar a explicação do algoritmo de Floyd Warshall no artigo do Warrior. Neste caso não bastava saber só o valor da distância, mas também a path percorrida :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Certo, portanto o que eu fiz não foi nada disso, pois não?

Foi o quê? Brute-force?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estive a fazer o C cá pra comigo... O algoritmo que usei foi:

Há uma lista de pessoas. Para cada pessoa que se recebe da entrada, retira-se da lista (pela ordem inversa de que foram inseridas, i.e. do mais recente para o mais antigo), aquele pessoal que é mais baixo do que a pessoa em análise, e vai-se os contando. Quando acabam as pessoas mais baixas, a pessoa em análise é inserida no fim (i.e. no lugar das que foram retiradas da lista).

Depois, conta-se (no mesmo contador que há pouco) o pessoal que é da mesma altura que a pessoa em análise e está na lista (a partir do sítio onde se parou), mas não se os elimina. Quando acabam as pessoa da mesma altura, soma-se 1 ao contador, mas só caso ainda haja mais gente na lista (i.e. encontramos uma pessoa mais alta do que a que está a ser analisada, e por isso não dá para ver "para além" dessa pessoa, mas dá para a ver).

Por outras falavras: vai-se mantendo num "pseudo-stack" as pessoas já analisadas que ainda são visíveis a partir do ponto onde se está, e em cada passo vai-se eliminando aquelas que ficam "tapadas" pela nova pessoa (e contando-as). Não sei se repararam, mas no stack as pessoas mais perto do topo são as mais baixas, e vão sempre crescendo.

Não faço ideia se é eficiente porque não tenho problemas grandes. No entanto, sempre é melhor do que simplesmente andar às voltas nos dados de entrada.

Ainda mostrava o código, mas eu escrevi em Java, e enfiei para lá um anti-padrão completamente descarado, e não quero que gozem comigo! :-) (foi só porque queria retornar uma queue não modificável...)

Para dizer a verdade, demorei mais tempo nisso do que a programar o algoritmo.

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Certo, portanto o que eu fiz não foi nada disso, pois não?

Foi o quê? Brute-force?

Sim, acho que é um brute force :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso é o C, o D só um fez.

Corrigido.

Por falar no D (só agora é que li o enunciado). No enunciado diz que as rainhas se podem mover na diagonal, mas só numa das direcções ortogonal. É mesmo assim ou é um erro?

Aparte disso, não percebi muito bem o problema. Parece-me que qualquer deles pode evitar que o outro ganhe infinitamente. Provavelmente, percebi mal o problema...

O B é um union-find de caras. Tirando ser preciso mapear os produtos para inteiros e implementar o ADT, não tem nada de especial.

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas já que estamos nesse o meu C, foi o seguinte:

C - http://paste.portugal-a-programar.org/pastebin.php?show=3094

O algoritmo inicial que fiz foi o seguinte (não é o que está nesse código, já explico porquê). Resolvi-o por programação dinâmica. Basicamente fazemos uma matriz de N po N pessoas e na diagonal pomos os valores de altura de cada pessoa. Nas posições que estiverem juntas (tipo a passoa 2 com a 1, ou a pessoa 4 com a 3) coloco o valor 0: deste modo

alturas:

1 5

2 2

3 4

4 1

5 3

  1  2  3  4  5

1 5  X  X  X  X

2 0  2  X  X  X

3    0  4  X  X

4        0  1  X

5            0  3

depois para cada posição que sobra coloco o maior valor entre o valor acima, e o valor acima e à direita uma casa, portanto:

  1  2  3  4  5

1 5  X  X  X  X

2 0  2  X  X  X

3 2  0  4  X  X

4 2  4  0  1  X

5 4  4  1  0  3

Esta é a matriz final, depois basta para cada posição (a,:thumbsup: exceptuando a = b, ver se a altura de a e a altura de b são maiores ou igual ao valor na sua posição na matriz, se sim, soma um ao resultado final.

O código que meti aí em cima é exactamente igual mas reduzindo a memória. Como a matriz é sendo actualizada precisando apenas do valor da row de cima, só mantenho uma matriz de [2][N] para reduzir de uma memoria O(N^2) para O(2n).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Mas já que estamos nesse o meu C, foi o seguinte:

(snip)

Tens a certeza? Tenta lá este:

10

1

2

2

1

1

2

1

2

2

2

No meu deu 23 e no teu deu 29. Contei-as também à mão (por outro método) e deu-me 23.

Além disso, eu meu foi mais rápido num problema grande (10000 pessoas), a não ser que as pessoas tenham todas a mesma altura (assim fica muito mais lento, mas é possível aplicar a heurística e fazer o cálculo com análise combinatória quando as pessoas têm todas a mesmo atura :-)).

Ah... e usei a máquina virtual (por acaso, nem sequer sei compilar Java para código máquina).

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vê lá se não me enganei no raciocínio:

|                    |

|  - -    -  - - - |

| -    - -  -      |

+ + + + + + + + + + + +

| 0 1 2 3 4 5 6 7 8 9 |

1. (0,1)

2. (1,2)

3. (1,5)

4. (1,7)

5. (1,8)

6. (1,9)

7. (2,3)

8. (2,4)

9. (2,5)

10. (2,7)

11. (2,8)

12. (2,9)

13. (3,4)

14. (3,5)

15. (4,5)

16. (5,6)

17. (5,7)

18.(5,8)

19 (5,9)

20. (6,7)

21. (7,8)

22. (7,9)

23. (8,9)

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Corrigido.

Por falar no D (só agora é que li o enunciado). No enunciado diz que as rainhas se podem mover na diagonal, mas só numa das direcções ortogonal. É mesmo assim ou é um erro?

Aparte disso, não percebi muito bem o problema. Parece-me que qualquer deles pode evitar que o outro ganhe infinitamente. Provavelmente, percebi mal o problema...

O B é um union-find de caras. Tirando ser preciso mapear os produtos para inteiros e implementar o ADT, não tem nada de especial.

JJ

Existe a mesma restrição para a horizontal e a vertical, e é exactamente essa restrição que faz com que não seja possível criar ciclos infinitos.

Essa restrição garante que as rainhas em cada movimento se aproximem sempre de (0,0), e nunca se afastam ou mantenham a distância.

Se a isso aliarmos a obrigatoriedade de jogar (não podemos passar a jogada), o jogo tem sempre fim.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens a certeza? Tenta lá este:

Certo... ainda sou verdinho a dp e esta está toda engatada, mas a ver se corrijo o erro.

Anyway, não vejo porque não participaste, dado que a avaliação do mooshak é um dado precioso sobre a validade ou eficiência do nosso algoritmo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Existe a mesma restrição para a horizontal e a vertical, e é exactamente essa restrição que faz com que não seja possível criar ciclos infinitos.

Ah... ok, não me tinha lembrado dessa. Lembro-me de ter achado estranho as coordenadas terem o K a subtrair, mas na altura não reparei que isso era importante.

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Anyway, não vejo porque não participaste, dado que a avaliação do mooshak é um dado precioso sobre a validade ou eficiência do nosso algoritmo.

Algoritmos nunca foi o meu forte...

Mesmo assim, para a próxima participo.

Pensei que fosse assim mais tipo maratona à la projecto de IAED.

JJ

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Permite-me discordar. 3 do CIC que pelo menos passaram nos Sample Inputs. Aquela não é a classificação final, os testes a que os programas estavam sujeitos eram os Sample Inputs. Hoje ou amanhã sai a classificação final com os programas testados por todos os testes.

sim eu sei. inda assim 5/4 exercicios secundário axas mau? -.-

btw: o d nem tentei. bastou ver qem o fez dixe logo q nao :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

btw: o d nem tentei. bastou ver qem o fez dixe logo q nao :P

Que pensamento errado :P  Devias ter tentado pelo menos sacar uns pontos com uma solução de brute force.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

brute force e mt trolha. e mesmo q tentasse o brute n cnsgia. preferi tentar o B, ja q so tinha 90 mins ate ao fim da prova. e pensar q submeti o exercicio ao ultimo min sem ele ordenar xD. tipo:

temp=a

a=b

a=temp <- hm... pq sera q isto n ordena xD. axo q o strcmp n ta a funcionar direito LOL

edit

pro D:

so mesmo cin entrada do exemplo cout saida do exemplo XD.

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