Search found 22 matches

by SilentStrike
Fri Aug 18, 2006 10:29 pm
Forum: Algorithms
Topic: distinct substring
Replies: 1
Views: 1624

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...
by SilentStrike
Sat May 07, 2005 3:25 pm
Forum: Algorithms
Topic: All distance minimum difference
Replies: 1
Views: 974

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 ...
by SilentStrike
Mon Apr 18, 2005 12:21 am
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4725

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.
by SilentStrike
Thu Mar 24, 2005 7:05 pm
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4725

Was it a 32 bit overflow problem?
by SilentStrike
Mon Mar 21, 2005 7:36 pm
Forum: Volume 108 (10800-10899)
Topic: 10838 - The Pawn Chess
Replies: 11
Views: 4725

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.
by SilentStrike
Wed Jan 26, 2005 8:45 am
Forum: Volume 100 (10000-10099)
Topic: 10068 - The Treasure Hunt
Replies: 31
Views: 6209

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...
by SilentStrike
Tue Dec 28, 2004 5:36 pm
Forum: Algorithms
Topic: New algorithms website
Replies: 3
Views: 1558

That looks like a pretty cool site. Maybe I'll comment on a few of my favorite problems.
by SilentStrike
Mon Dec 27, 2004 9:10 am
Forum: Volume 3 (300-399)
Topic: 331 - Mapping the Swaps
Replies: 11
Views: 5851

asdfasdfasdfasdfaf

Thanks :).

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

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 
by SilentStrike
Wed Nov 24, 2004 3:13 am
Forum: Volume 5 (500-599)
Topic: 506 - System Dependencies
Replies: 17
Views: 6625

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

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

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.
by SilentStrike
Sat Oct 16, 2004 3:43 am
Forum: Algorithms
Topic: calculate n choose k
Replies: 5
Views: 1871

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...
by SilentStrike
Mon Jun 21, 2004 5:20 pm
Forum: Volume 1 (100-199)
Topic: 116 - Unidirectional TSP
Replies: 226
Views: 36108

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

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...

Go to advanced search