SPOJ - mblast

[Warrior]

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

[mogers]

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

[mogers]

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

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

[Warrior]

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

[mogers]

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

[mogers]

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.

[pcaldeira]

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.

[mogers]

Warrior, não tinha visto o teu edit.

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

[Warrior]

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

[mogers]

Falei com o pcaldeira no irc, ele tinha uma ideia errada 😞

[Warrior]

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

[mogers]

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 😞

[Warrior]

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(😄 (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"

[Warrior]

Lá arranjei tempo e fiz o mblast.

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