11381 - Elegant Strings

Monsoon · Post by **Monsoon** » Sat Jan 05, 2008 9:20 pm

What is answer for

1
adsdsf

are there any tricky testcases?

EDIT: bug found

sunny · Post by **sunny** » Sat Jan 05, 2008 9:33 pm

You mean where S/T may be a empty string?

Well there are no such cases in the input file.

sonyckson · Post by **sonyckson** » Mon Jan 07, 2008 6:46 pm

Hello!, any hint for this problem? i cant even figure out a way to get the minimum amount of strings possible by splitting T... Thanks!, Eric.

shanto86 · Post by **shanto86** » Mon Jan 07, 2008 7:56 pm

the problem can be reduced to a matching problem.

tobby · Post by **tobby** » Fri Jan 11, 2008 11:19 am

A matching problem? Matching what? Could you give more hints?

What I can think of is only a brute-force search....

rio · Post by **rio** » Fri Jan 11, 2008 11:28 am

Hint:
One match means you could reduce the numbers of substrings by one.

-----
Rio

tobby · Post by **tobby** » Fri Jan 11, 2008 11:34 am

Ah, so you mean using T as the nodes, and from S we get the edges? Then we need a mincost maxflow algorithm?

Monsoon · Post by **Monsoon** » Fri Jan 11, 2008 2:20 pm

tobby wrote:Ah, so you mean using T as the nodes, and from S we get the edges? Then we need a mincost maxflow algorithm?

I won't say anything new, but it much helps when you think about reduction to minimum cost path cover of DAG. In CLR there is solution to minimum path cover of DAG and when someone understand it right, this task should be fairly easy.

tobby · Post by **tobby** » Fri Jan 11, 2008 8:22 pm

I use the idea that I mentioned in my post and get accepted.

This task would be easy to those who have a well-coded mincost maxflow code in hand. I didn't have one, so I just apply the mcmf code in shygypsy.com.