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

Warrior

SPOJ - mblast

Mensagens Recomendadas

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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 :thumbsup:

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pcaldeira    0
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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
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).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
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..

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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 :(

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
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(: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"

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


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade