Jump to content

Tópico dos problemas das finais das ONI 2010


gangsterveggies
 Share

Recommended Posts

Como não queria encher o Forum com uma data de post com uma data de problemas das ONIs passadas, decidi classificar tudo por anos e tirar as minhas dúvidas todas aqui  ?

A: http://www.dcc.fc.up.pt/oni/problemas/2010/final/probA.html

B: http://www.dcc.fc.up.pt/oni/problemas/2010/final/probB.html

C: http://www.dcc.fc.up.pt/oni/problemas/2010/final/probC.html

A: Já percebi a ideia. Acho engraçada. WA 92.

B: Já vi a sessão de discussão (http://www.dcc.fc.up.pt/oni/problemas/2010/final/discussao/solB.html), mas não percebo como "rodar" matriz... já tentei fazê-lo "manualmente", mas acabo por ter sempre WA...

C: Também já percebo a solução ótima e já implementei. Problema: ler o input e construi grafo. Eu percebi que é preciso usar um Sweep Line, mas não tenho a certeza de como fazê-lo... Se só para o de 2008(http://www.dcc.fc.up.pt/oni/problemas/2008/final/probA.html) tive imenso tempo até "dominar" o problema, não estou a ver a solução... (ou melhor estou a vê-la em papel, mas em código não sei bem... como no outro...).

Obrigado.

--

GangsterVeggies - DCC/FCUP

Link to comment
Share on other sites

Eu não percebo muito bem qual o teu problema. Tipo, no tutorial vem EXACTAMENTE o problema que tu estás a tentar resolver. Se quiseres posso deixar aqui código do sweep que resolve o problema, mas aconselhava-te a programá-lo tu próprio. Eu só percebi como é que a sweep line se aplicava a este exemplo quando comecei a escrever o código.

Link to comment
Share on other sites

ja resolveste o problema? eu sinceramente acho que esse tutorial não foi bem escrito porque parece-me uma descrição muito genérica e dificil para um novato perceber (é um pouco normal quando os autores são targets como o bmerry, não é fácil "descer à terra")

não tens nenhum livro de algoritmos? normalmente qualquer livro aborda o problema de encontrar os 2 pontos mais próximos de um conjunto de pontos e isso é feito com sweep line.

a ideia fundamental é algo do género:

- escolher um eixo (xx ou yy) para varrer (sweep) os pontos.

- saber qual é a distância DIST a considerar (no prob C é sempre constante, dada no input)

- ordenar os pontos 1º pela coordenada escolhida no 1º passo e em caso de empate pela outra coordenada

- processar os N pontos (exemplifico em xx)

--- para cada ponto P sabes que os possíveis pontos adjacentes só podem estar no quadrado ( P.x - DIST , P.y - DIST ) a ( P.x + DIST , P.y + DIST)

tenta pensar como fazer este último passo, notando que os pontos ja tão ordenados por xx

PS: a nota do enunciado que garante que existem poucos pontos adjacentes (salvo erro 20) é fundamental para garantir que este método não é O(N^2) porque, salvo erro, se fosse dado um grafo onde todos os pontos eram adjacentes entre si, esta construção teria necessariamente de ser O(N^2)

PS2: a distancia entre ( P.x - DIST , P.y - DIST ) e P é superior a DIST, mas penso que considerar este quadrado é a forma mais simples de implementar

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

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.