Hey everyone. Yesterday I found problem UVa 10679 — I Love Strings!!, solved it using C++ Strings and KMP, and got a runtime of 1.080/3.000s. I found this rather high so I looked for the problem on the web and found on Algorithmist that this problem perfectly suits Aho-Corasick, so I found this guide and solved the problem based on that, but I'm getting TLE. After this I was a little bit confused, but maybe such implementation is just slow. Then I checked the Problem Stats and found that morris821028's solution is ranked 17 with a runtime of 0.016, so I thought he must have implemented Aho-Corasick in a (much) faster way. Right after this I looked for his solution: turns out he used KMP, just like me, but with C-Style strings instead...

Are C-Style Strings really this faster or is this just an especial case?

Hey everyone. I'm trying to solve a problem from one of my country's old national contests: UVa 12319. What I did is to build both graphs, run Floyd-Warshall's on both and then check if it's valid or not. Here's my code (boolean p is to print some debug info).

I'm getting WA as veredict. Any help? Thanks!

Hey everyone. I was looking at the code in CP3 book to solve the TSP using top-down DP in O(n^2*2^n) and was trying to print the path, but it seems impossible to me.

I thought about creating something like a "parent" array and then reconstruct, but couldn't.

This is the code:

static void tsp() {
// n = graph's number of vertices
memo = new double[n][1 << n];
for (int i = 0; i < n; ++i)
	for (int j = 0; j < 1 << n; ++j)
		memo[i][j] = Double.MIN_VALUE;
double distance = tsp(0, 1);
// Build ath - pending
System.out.println("Distance:" + distance);
}

static double dp(int pos, int bitmask) {
	if (bitmask == (1 << n) - 1)
		return graph[pos][0];
	if (Double.compare(memo[pos][bitmask], Double.MIN_VALUE) != 0)
		return memo[pos][bitmask];
	double ans = Double.MAX_VALUE;
	for (int nxt = 0; nxt < n; ++nxt)
		if (nxt != pos && (bitmask & (1 << nxt)) == 0)
			ans = Double.min(ans, graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt)));
	memo[pos][bitmask] = ans;
	return ans;
}

Any help? Thanks!

Got it

Guys the judge is giving different answers. It's happened like 3 times now but I fixed them by removing ternary operators. Here's an example:

submission link

Any help?

Thanks!