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

Baderous

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

Mensagens Recomendadas

Baderous

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

Partilhar esta mensagem


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

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Tharis

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Baderous

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Baderous

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Tharis

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

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:


"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
Jeronimus Linuxius

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

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:


"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
Jeronimus Linuxius

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jeronimus Linuxius
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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jeronimus Linuxius

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
vbmaster

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jeronimus Linuxius

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Jeronimus Linuxius
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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
MisirLou

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

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.


"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
MisirLou

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.

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.