## Search found 251 matches

- Wed Jun 17, 2009 8:10 am
- Forum: Volume 115 (11500-11599)
- Topic: 11540 - Sultan's Chandelier
- Replies:
**3** - Views:
**2547**

### Re: 11540 - Sultan's Chandelier

For the testcase [[[],[]]],[],[[],[]] how many transformations do we have? I would have said 4: identity, 2 rotations of the bottommost [[],[]] subtrees and the product of the latter two transpositions. Thus we have one permutation with 8 disjoint cycles (colors^8), two permutations with 1 two-cycle...

- Mon Jun 15, 2009 6:38 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11255 - Necklace
- Replies:
**13** - Views:
**6095**

### Re: 11255 - Necklace

Well, the recursive formulas give us full control over {P_k}^{j_k}, that is, over

But how to handle the product of

*(a^k+b^k+c^k)^{j_k}*.But how to handle the product of

*{P_k}^{j_k}*'s ?- Sun Jun 14, 2009 7:14 am
- Forum: Volume 112 (11200-11299)
- Topic: 11255 - Necklace
- Replies:
**13** - Views:
**6095**

### Re: 11255 - Necklace

Let P_k = P(a,b,c) be the multivariate polynomial (a^k + b^k + c^k), 1 <=k <= n . Let A,B,C be the number of beads of each color, A+B+C = n . Let s be one of the 2n transformations, and let j_k = j_k(s) stand for the number of cycles of length k in the decomposition of s . Then we are asked to find ...

- Sat Jun 13, 2009 4:19 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11255 - Necklace
- Replies:
**13** - Views:
**6095**

### Re: 11255 - Necklace

It's all very well if one had infinite supply of beads of each color: just substitute `3' into the circular polynomial obtained by Polya enumeration.

But the point of this problem is: How to deal with

But the point of this problem is: How to deal with

*finite*supply of beads of each color? A tiny hint would be appreciated.- Tue Jun 09, 2009 5:16 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11572 - Unique Snowflakes
- Replies:
**36** - Views:
**12857**

### Re: 11572 - Unique Snowflakes

I got Ac with the above approach; however, the above post contains some FIXME's and therefore can't be considered a spoiler.

- Sat Jun 06, 2009 8:05 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10829 - L-Gap Substrings
- Replies:
**14** - Views:
**9492**

### Re: 10829 - L-Gap Substrings

Well, with Adrian's help I managed to get AC with an O(|GAP|n(logn)^2) algo, and I can't see as yet the way of shortening this to O(nlogn).

My code is 580 lines long, pure C code.

Many thanks to Adrian and to Rujia!

My code is 580 lines long, pure C code.

Many thanks to Adrian and to Rujia!

- Mon Jun 01, 2009 3:28 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11572 - Unique Snowflakes
- Replies:
**36** - Views:
**12857**

### Re: 11572 - Unique Snowflakes

the problem can be restated in terms of RMQ (range minima query) as follows: for each index i let idx be the index of the next occurence of the number a . If i is the last occurence of the number a , let idx = n (recall that we are using 0-based indexation). Now, for each i from 0 to n-1 check wheth...

- Sun May 31, 2009 11:30 am
- Forum: Volume 108 (10800-10899)
- Topic: 10829 - L-Gap Substrings
- Replies:
**14** - Views:
**9492**

### Re: 10829 - L-Gap Substrings

for the testcase the output size is
which amounts to O(n^2). Now, given we can find all branching tandem repeats in O(nlogn), how

to handle

Code: Select all

`s = a^n`

Code: Select all

`(n-L-1) + (n-L-3) + (n-L-5) + ...,`

to handle

**non**-branching tandem repeats?- Sat May 30, 2009 9:11 am
- Forum: Volume 108 (10800-10899)
- Topic: 10829 - L-Gap Substrings
- Replies:
**14** - Views:
**9492**

### Re: 10829 - L-Gap Substrings

I find all branching tandem repeats with gap 0 <= g <= L and length > L-g in O(L*n*log(n)). Specifically, for bbaabaaaaa$ my code finds pairs (6,10), (3,7), (8,10), (4,6), (7,9) and (2,6) but fails to find (6,8), because the corresponding tandem repeat (g = 0) is not branching. The question is: how ...

- Fri May 29, 2009 8:50 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10829 - L-Gap Substrings
- Replies:
**14** - Views:
**9492**

### Re: 10829 - L-Gap Substrings

Never mind, the question above is silly: we are asked to find the number of occurences, not the number of distinct substrings.

- Thu May 28, 2009 3:58 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10829 - L-Gap Substrings
- Replies:
**14** - Views:
**9492**

### Re: 10829 - L-Gap Substrings

to Adrian: did you store all the (i,D) pairs -- L-gap tandem repeats -- explicitly? I'm going to use an O(nlogn) algo for branching tandem repeats

- Thu May 28, 2009 12:01 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11475 - Extend to Palindrome
- Replies:
**32** - Views:
**14256**

### Re: 11475 - Extend to Palindromes

Consider the dual of the problem: find the largest suffix of the input text that is a palindrome.

text = abB, where B is the reverse of b. Then textTEXT = abBbBA, then you find the longest tandem repeat...

This leads to O(nlogn) solution which gets TLE + MLE.

text = abB, where B is the reverse of b. Then textTEXT = abBbBA, then you find the longest tandem repeat...

This leads to O(nlogn) solution which gets TLE + MLE.

- Wed Apr 08, 2009 1:08 pm
- Forum: Volume 8 (800-899)
- Topic: 802 - Lead or Gold
- Replies:
**20** - Views:
**11025**

### Re: 802 - Lead or Gold

I got AC with your LP formulation, as well. Of course, your approach is neat:

your just sum the residuals and change the order of summation and get the objective function (just dropping

a constant summand).

your just sum the residuals and change the order of summation and get the objective function (just dropping

a constant summand).

- Wed Apr 08, 2009 9:46 am
- Forum: Volume 8 (800-899)
- Topic: 802 - Lead or Gold
- Replies:
**20** - Views:
**11025**

### Re: 802 - Lead or Gold

Also I noticed that in CLR -- without Stein -- they give no description of simplex algo.

I guess you have an English version of CLRS that you brought from one of your innumerable

trips around the world

I guess you have an English version of CLRS that you brought from one of your innumerable

trips around the world

- Wed Apr 08, 2009 8:12 am
- Forum: Volume 8 (800-899)
- Topic: 802 - Lead or Gold
- Replies:
**20** - Views:
**11025**

### Re: 802 - Lead or Gold

After fixing that twice engaged i the code above got AC (I'll cut it). M-algoirithm is a well-known technique: http://www.math.cuhk.edu.hk/~wei/lpch3.pdf keywords: "artificial basis","augmented problem". It is possible to check whether the system of constraints is inconsistent by solving this "augme...