Hi, http://codeforces.net/contest/222/submission/12429658 My submission is failing test 15, and I cannot figure out why. I find the primes, then go through the numbers in the numerator and denominator. For each, I decrement it if possible and then print out whatever the numerator/denominator is after reduction.

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree.

So far, I've figured out that from the start node, there will be n children, each that can have n/2 children at most (since the 2nd layer will pick from min(n, max) which will be n/2 at most), and so the 2nd layer will have n/4 children at every node at most, giving the tree a height of at most log(n).

We can better this, the first level will have n nodes. The second level will have at most 0+1+2+..+lim+lim-1+...1 nodes, and so on (where lim is ceil(n/2)). That gives n^2 nodes at each level, a total of log(n) levels, with O(n) work being done at each node. So, the complexity I get is O(n^3 log(n)).

But, I am not sure of my calculations, especially because clearly getting an upper bound for the partition function is not an easy problem (this paper: http://link.springer.com/article/10.1007%2Fs11139-007-9022-z#page-1 lists it as < c^(root(n)) ). Since that is exponential, my analysis must be wrong, but I'm missing where.

Can someone help?

The code is at: http://community.topcoder.com/stat?c=problem_solution&rm=310853&rd=14552&pm=11308&cr=22673583

http://apps.topcoder.com/wiki/display/tc/SRM+527

For P8XGraphBuilder, I am not able to understand the proof of the "evil theorem" by dolphinigle

After going through the tutorial and seeing that an O(m*n) algorithm would pass and there was something to do with a "right" array, I coded up a solution that TLEd and then optimized it over XYZ attempts to this:

http://codeforces.net/contest/376/submission/5630035

which still TLEs. A friend optimized it to traverse in column major: http://codeforces.net/contest/376/submission/5631054

which passes. But, when I do the same:

http://codeforces.net/contest/376/submission/5631820

TLE! Any explanations?

Edit: Solved... (change char[] to string)