## Search found 83 matches

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

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:
**3886**

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:
**1588**

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:
**8046**

- Tue Apr 04, 2006 1:15 am
- Forum: Volume 110 (11000-11099)
- Topic: 11021 - Tribles
- Replies:
**15** - Views:
**5480**

- Mon Apr 03, 2006 2:44 pm
- Forum: Volume 110 (11000-11099)
- Topic: 11025 - Mr. And Mrs. Hamilton
- Replies:
**21** - Views:
**8046**

- Mon Apr 03, 2006 12:27 pm
- Forum: Volume 110 (11000-11099)
- Topic: 11025 - Mr. And Mrs. Hamilton
- Replies:
**21** - Views:
**8046**

- Mon Mar 27, 2006 12:43 pm
- Forum: Algorithms
- Topic: WHat is the best heapsort
- Replies:
**2** - Views:
**1195**

- Sat Mar 25, 2006 11:44 pm
- Forum: Volume 110 (11000-11099)
- Topic: 11019 - Matrix Matcher
- Replies:
**43** - Views:
**18099**

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:
**18099**

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:
**18099**

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:
**18099**

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:
**5704**

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:
**18099**

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

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:
**8965**