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

Warrior

SPOJ - mblast

14 mensagens neste tópico

Estava eu a tentar resolver este problema:

https://www.spoj.pl/problems/MBLAST/

(para poder passar o mogers no ranking..)

Quando depois de ter o código escrito vejo o sample 2 com o output 5.

Ainda antes de correr o meu programa sabia que ele ia responder 6 (e assim fez), de modo que.. como é que a resposta pode ser 5?

mogers: é um erro no enunciado?

PS: na miup não me vou esquecer de ler o enunciado COMPLETO antes de começar a programar..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quando depois de ter o código escrito vejo o sample 2 com o output 5.

Ainda antes de correr o meu programa sabia que ele ia responder 6 (e assim fez), de modo que.. como é que a resposta pode ser 5?

mogers: é um erro no enunciado?

Não. A resposta é (denotando espaços por '#'):

kuiv#

###ua

k com # = 1

u com # = 1

i com # = 1

v - u = 1

# com a = 1

Total 5

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu achei o Tourist bastante complicado. Só consegui resolver os meus erros com a ajuda do André Pinto :P

edit: pfff, depois de 2 dias a matutar neste problema, finalmente consegui resolvê-lo :(  Já agora, fazes ideia como é ? :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Assim de repente, parece-me um problema de fluxo.

Podes identificar facilmente os casos impossíveis usando um dfs, (tendo um digrafo, começas em - passas por todas as arestas e chegas ao +? com um m tão pequeno até podes fazer quadrático, estar aresta a aresta se é possível). Acho que não há nenhum caso impossível que fique de fora (ou vice-versa)

Agora não tenho a certeza, parece-me um problema de max flow com demands em cada edge, podes colocar um lower bound.

O problema é que como queres uma capacidade infinita por edge, queres calcular o mínimo flow possível.

Suponho que o google pode ajudar em encontrar um "graph minimum flow with lower bound on edges"

Edit: http://pdos.csail.mit.edu/~petar/courses/karger05algorithms/6854j-sol4.pdf

Problema 4, o enunciado está aqui http://74.125.77.132/search?q=cache:J0ZuKcMo4WcJ:pdos.csail.mit.edu/~petar/courses/karger05algorithms/ps4.ps+minimum+flow+with+lower+bound&cd=1&hl=pt-PT&ct=clnk&gl=pt&client=firefox-a

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"Problema de fluxo" é muito vago. Mas sim, tem a ver com um problema de circulação num grafo o que corresponde a uma generalização de maximum flow. Eu não encontrei grande coisa online. Mas com uma discussão no topcoder e a consulta dum livro ("Graphs, Networks & Algorithms") lá percebi como formular o grafo.

É um tipo de problemas interessante. Quando tiveres tempo, recomendo :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Precisar de criar 2 nós: "supersource" e "supersink".

Depois, ligas a supersource a todos os vértices do grafo antigo com capacidade igual ao somatório das lower bounds dos edges que chegam ao vértice. De modo análogo, ligas todos os vértices antigos ao supersink com capacidade igual ao somatório das lower bounds dos edges que saem desse vértice.

Por fim, adicionas um edge de capacidade infinita desde o old sink (t) para a old source (s). Se maxflow( supersource, supersink ) == Somatório_Todas_LowerBounds, o problema tem solução.

Para determinar o mínimo de fluxo podes fazer binary search na capacidade do edge t -> s pois este determina o fluxo da circulação. Há um método para determinar isto sem a binary search mas ainda não procurei como é, só vi no topcoder que existe.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu já não programava desde a ronda 2 do GCJ, mas como quero ver se participo na miup online (mas a sério), estive a ler esses problemas que postaram... e o tourist parece-me fácil. Não sei se o li bem/se o meu algoritmo vai funcionar, vou implementar e já digo alguma coisa. Btw, se puderem aparecer no IRC hoje, quero ver se arranjo uma hora ou duas para treinar um bocado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Warrior, não tinha visto o teu edit.

pcaldeira, não posso treinar hoje, mas posso aparecer no irc.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só li o tourist agora, não me parece assim tão evidente, o facto dele ir e vir complica significativamente (afinal é esse o problema).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto parece-me muito DP, mas dá para se reduzir a um grafo, não sei se há algum algoritmo a aplicar neste caso.

Já tenho 3 problemas para pensar..

O mblast resolveste n^2? Fiz uma solução n^3 que dá TLE e outra n^2 WA que não sei onde está o erro..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O mblast fiz em N^2 com dp. Não tou a ver tricky cases... bug a inicializar a dp? Vê as cenas mais parvas (acontece a todos).

Yep, Tourist também é DP. Como tenho alguma dificuldade com DP achei-o dificil :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A minha ideia (inicial) para o mblast é fazer uma matriz m[ a ][ b ] que diga a distância mínima entre duas substrings s1(0, a) e s2(0, :(. (na verdade é com s2(0, b-1) para poder comparar s1(0, a) com a string vazia.

Cada uma dessas posições era calculada achando o minimo entre os m[a-1][k], e depois igualando s1(a) com s2(:D (acrescentando ou a diferença, ou dois espaços, em cima e em baixo)

Para isso preciso de percorrer todos os (a, b, k), o que dá n^3. A minha solução n^2 consiste em ignorar o último ciclo, e funciona em todos os testes que fiz, mas foi um pouco "improviso"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Lá arranjei tempo e fiz o mblast.

Vou pegar noutro problema agora, mas ainda vou ter que pensar nele.

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