## Search found 22 matches

Fri Aug 18, 2006 10:29 pm
Forum: Algorithms
Topic: distinct substring
Replies: 1
Views: 1607
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...
Sat May 07, 2005 3:25 pm
Forum: Algorithms
Topic: All distance minimum difference
Replies: 1
Views: 958

### All distance minimum difference

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 ...
Mon Apr 18, 2005 12:21 am
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4634
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.
Thu Mar 24, 2005 7:05 pm
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4634
Was it a 32 bit overflow problem?
Mon Mar 21, 2005 7:36 pm
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4634
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.
Wed Jan 26, 2005 8:45 am
Forum: Volume 100 (10000-10099)
Topic: 10068 - The Treasure Hunt
Replies: 31
Views: 6103

### 10068 WA

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...
Tue Dec 28, 2004 5:36 pm
Forum: Algorithms
Topic: New algorithms website
Replies: 3
Views: 1538
That looks like a pretty cool site. Maybe I'll comment on a few of my favorite problems.
Mon Dec 27, 2004 9:10 am
Forum: Volume 3 (300-399)
Topic: 331 - Mapping the Swaps
Replies: 11
Views: 5768
asdfasdfasdfasdfaf

Thanks .

I am sure that makes it a LOT easier.
Mon Dec 27, 2004 2:31 am
Forum: Volume 3 (300-399)
Topic: 331 - Mapping the Swaps
Replies: 11
Views: 5768

### 331 - Mapping the Swaps

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.

Code: Select all

``````3 9 1 5
3 1 9 5
1 3 9 5
1 3 5 9
3 1 5 9
1 3 5 9
``````
Wed Nov 24, 2004 3:13 am
Forum: Volume 5 (500-599)
Topic: 506 - System Dependencies
Replies: 17
Views: 6579

### Large sample input? Tricky test case?

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...
Thu Nov 11, 2004 6:01 am
Forum: Other words
Topic: XML/HTML parsing problems?
Replies: 0
Views: 800

### XML/HTML parsing problems?

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.
Wed Nov 03, 2004 2:40 am
Forum: Other words
Topic: GNU g++ Integer class?
Replies: 1
Views: 1186

### GNU g++ Integer class?

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.
Sat Oct 16, 2004 3:43 am
Forum: Algorithms
Topic: calculate n choose k
Replies: 5
Views: 1836
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...
Mon Jun 21, 2004 5:20 pm
Forum: Volume 1 (100-199)
Topic: 116 - Unidirectional TSP
Replies: 226
Views: 35145

### Nice test case

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...
Sat Jun 19, 2004 6:34 pm
Forum: Volume 1 (100-199)
Topic: 116 - Unidirectional TSP
Replies: 226
Views: 35145
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...