Search found 83 matches

by david
Mon May 15, 2006 11:54 am
Forum: Volume 110 (11000-11099)
Topic: 11027 - Palindromic Permutation
Replies: 18
Views: 10881

There's no need for DP here. You can easily compute how many permutations of a string start by a given letter, which allows you to determine what the first character of the nth permutation will be, and you can proceed likewise for the remaining letters. The resulting algorithm has O(string size^2) t...
by david
Thu Apr 13, 2006 11:19 pm
Forum: Volume 110 (11000-11099)
Topic: 11023 - Multisets and Sequences
Replies: 10
Views: 3805

PostPosted: Thu Apr 13, 2006 9:21 pm Post subject: Algorithm Is there an algorithm that, given a set (1,2,3,4,5,...), gives it's n-th permutation in lexicographical order, without needing to compute all permutations before it? There is a trivial linear-time algorithm for that if all elements are di...
by david
Wed Apr 05, 2006 12:34 pm
Forum: Algorithms
Topic: Problem with sum of seqence
Replies: 5
Views: 1548

This problem is NP-complete, so there's not much you can do if you want an exact solution and think that the straightforward (but exponential-time) dynamic programming solution will take too long. Anyway I think the constraints are not high enough to preclude using the dp solution (of course this de...
by david
Wed Apr 05, 2006 1:28 am
Forum: Volume 110 (11000-11099)
Topic: 11025 - Mr. And Mrs. Hamilton
Replies: 21
Views: 7916

What I find funny about all this is the fact that he made a wrong submission to his own problem!
by david
Tue Apr 04, 2006 1:15 am
Forum: Volume 110 (11000-11099)
Topic: 11021 - Tribles
Replies: 15
Views: 5382

First try to compute the probability that all descendants of one tribble will be dead after m generations, and then the general problem is easily solved. (As an aside, I had also to make use of the fact that the answer must be accurate only to within 10^-6 to avoid TLE during the contest).
by david
Mon Apr 03, 2006 2:44 pm
Forum: Volume 110 (11000-11099)
Topic: 11025 - Mr. And Mrs. Hamilton
Replies: 21
Views: 7916

Then why isn't vertex 3 part of the output?
by david
Mon Apr 03, 2006 12:27 pm
Forum: Volume 110 (11000-11099)
Topic: 11025 - Mr. And Mrs. Hamilton
Replies: 21
Views: 7916

I can't make sense out of the output given for the sample input.
How come you can visit vertex 1 inmediately after vertex 2, if there is no edge connecting both?
by david
Mon Mar 27, 2006 12:43 pm
Forum: Algorithms
Topic: WHat is the best heapsort
Replies: 2
Views: 1174

Considering the standard heapsort algorithm has complexity O(n log n), and furthermore this cannot be improved upon, I have no clue what you may be talking about.
by david
Sat Mar 25, 2006 11:44 pm
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 17844

If your hash function depends of i and j, how do you compute yout X*1 patterns in a constant time? I think for each column you must compute the first whole X*1 pattern and for the next ones in the same column in a constant time. Am I right? And if the answer is yes, how do you compute this? Thanks,...
by david
Sat Mar 25, 2006 5:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 17844

Hello, So the solution is based on hashing the patern? What if we have the same hash for a different set of letters ot this is impossible? It is perfectly possible, but it is not likely that the judge test data will contain a case that will cause such a solution to fail. The hashing solution would ...
by david
Sat Mar 25, 2006 5:28 pm
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 17844

I just tried your method and got AC in 7 secs. Make sure your arithmetic part is computed correctly. You're right, that's enough to get AC. I mistakenly took X and Y to be the pattern width and height, respectively (this choice of letters in the problem statement may be a bit misleading). Anyway, I...
by david
Fri Mar 24, 2006 3:15 am
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 17844

Let c [j] be the character of the shorter string, I define its hash value as: Summation over all valid i,j: c [j] * (3 ^ (i*100+j)) mod 2^32 (x^y denotes x to the power y instead of bitwise-XOR.) Are you sure you didn't mean, for example, c [j] * (32 ^ (i*100+j)) mod 2^32 ? The hash function you wr...
by david
Wed Mar 22, 2006 6:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11020 - Efficient Solutions
Replies: 14
Views: 5622

I think this is a good problem. Binary search trees are an ubiquitous idea in computer science, and I don't think C++ programmers have such a great advantage here, since we cannot directly manipulate a balanced tree, but are limited to use the interface for a set (whose underlying implementation is ...
by david
Mon Mar 20, 2006 2:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 17844

11019 - Matrix Matcher

What, exactly, is a "character" for this problem?
It seems there are characters not in the 'a'-'z' or 'A'-'Z' range.
by david
Sun Mar 19, 2006 3:05 pm
Forum: Volume 110 (11000-11099)
Topic: 11012 - Cosmic Cabbages
Replies: 29
Views: 8815

andrews1:
Your algorithm is incorrect. Consider, for instance, points (1, 1, 0), (3, 3, 0), (2, 1, 0), (0, 4, 0).

Go to advanced search