OJ Board

Is the problem just count the number of distinct substrings? I don't know about suffix arrays, but I do know an O(n^2) solution using tries. You can put each subsring in a trie in O(n^2) time. As you are building the trie, you can count new substrings. For example, ABABACA insert A insert AB [keep p...

My friend recently had an algorithms final exam. I got him all prepped up for dynammic programming, covering the classic examples, and then quite a few dp problems I've seen here, but the teacher gave him this problem as a dynammic programming problem, and I don't even know how to solve it. You are ...

I wrote up my solution to the Pawn Chess problem on Algorithmist.

The 32 bit overflow problem is basically that you might overflow an int when doing bit arithmetic to pack a state into a 32 bit int.

Was it a 32 bit overflow problem?

I had a bug because I was trying to encode the states into a 32 bit integer, and there was some problems in storing the pawn in the bottom right (most signficant two bits in my integer). If you are encoding into an int, try using 64 bits for safety.

I am doing a breadth first search in the original ascii map, and then making a 12x12 graph, and then doing a O(2^n*n^2) dp in the derived graph. I think the algorithm is fine. I get the correct answer (except for a different, but still seemingly valid path) for the sample input. Are there any specia...

That looks like a pretty cool site. Maybe I'll comment on a few of my favorite problems.

asdfasdfasdfasdfaf

Thanks .

I am sure that makes it a LOT easier.

Consider the number of swap maps for 3 9 1 5.
It seems to me that there are two, like shown. But the sample output says there is only 1.

Does anyone have any really nasty input? I passed all the input on the forum. Does the order of removal matter (Is removing A then B then C the same as A then C then B, so long as B and C are not dependant on one another)? I know that I can change one line in my program so that it outputs the same t...

Are there any uva problems about parsing HTML or XML? They seem to be a little bit popular in the regional ACMs, so I'd like a problem or two to practice on.

I have The "Programming Challenges" manual in front of me, it says there is a GNU g++ Integer class (p 103). Does such a thing really exist? I googled for documation, but didn't find anything.

This works. The computation takes n^2 time, but you only have to do it once, and I doubt you need to store that many. [cpp] #include <iostream> using namespace std; static long choose(int n, int m) { if(m > n/2) return choose(n, n-m); long t = 1; for(int i=1; i<=m; i++) t = (t * (n-m+i))/i; return t...

Here is a test case that my original program failed on. Maybe yours will too. 10 10 9 0 9 9 9 9 9 9 9 9 9 9 0 9 2 2 1 1 1 1 9 9 9 2 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 9 9 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 Correct Answer i...

I reversed it. Instead of trying to find minimum sum from left to right, it goes from right to left. Now it works. I have no clue why, I think they should both give the same answer. Here is the working solution. // http://acm.uva.es/p/v1/116.html #include <iostream> #include <climits> using namespac...