Search found 22 matches
- Fri Aug 18, 2006 10:29 pm
- Forum: Algorithms
- Topic: distinct substring
- Replies: 1
- Views: 1726
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: 1034
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: 5035
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.
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: 5035
- Mon Mar 21, 2005 7:36 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10838 - The Pawn Chess
- Replies: 11
- Views: 5035
- Wed Jan 26, 2005 8:45 am
- Forum: Volume 100 (10000-10099)
- Topic: 10068 - The Treasure Hunt
- Replies: 31
- Views: 6913
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: 1616
- Mon Dec 27, 2004 9:10 am
- Forum: Volume 3 (300-399)
- Topic: 331 - Mapping the Swaps
- Replies: 11
- Views: 6204
- Mon Dec 27, 2004 2:31 am
- Forum: Volume 3 (300-399)
- Topic: 331 - Mapping the Swaps
- Replies: 11
- Views: 6204
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.
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: 6942
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: 834
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: 1282
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: 2111
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: 42600
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: 42600
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...