## Search found 83 matches

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...
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...
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...
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!
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).
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?
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?
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.
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,...
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 ...
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...
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...
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 ...
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.
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).