Search found 251 matches

by serur
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...
by serur
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 (a^k+b^k+c^k)^{j_k}.
But how to handle the product of {P_k}^{j_k}'s ?
by serur
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 ...
by serur
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 finite supply of beads of each color? A tiny hint would be appreciated.
by serur
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.
by serur
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 :wink: lines long, pure C code.
Many thanks to Adrian and to Rujia!
by serur
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...
by serur
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

Code: Select all

s = a^n
the output size is

Code: Select all

(n-L-1) + (n-L-3) + (n-L-5) + ...,
which amounts to O(n^2). Now, given we can find all branching tandem repeats in O(nlogn), how
to handle non-branching tandem repeats?
by serur
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 ...
by serur
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.
by serur
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
by serur
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.
by serur
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).
by serur
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 ;)
by serur
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...

Go to advanced search