Bumping. Hurry up to register.

This was a great contest! Although I am somewhat salty that I had a solution for the third problem in div2, here, http://ideone.com/172siu, but could not figure out how to submit it.

How to solve div1 600?

Is there an easy slower solution to div1 600 I'm missing? I had (what I thought was a cool solution) that ran in , but apparently the author only wanted the from Google.

I wonder, is it a programming contest, a maths contest, or a googling contest???

I was looking at Div 2 1000 after the contest, and after I read the problem, I was pretty damn sure I read the exact same problem before. ( that I couldn't solve : P )

With some googling, I found the exact same problem here : http://codeforces.me/gym/100221/attachments/download/1767/20052006-winter-petrozavodsk-camp-andrew-stankevich-contest-17-en.pdf

Please someone tell me it's different and there is something I can't get between them :D, otherwise how original? Seriously, that would really be a joke...

My solution to div1 600:

We want to calculate , where s(n, k) denotes Stirling numbers of the first kind.

By using , where S(n, k) denotes Stirling numbers of the second kind, we just need to calculate for all 0 ≤ l ≤ m.

We know , and (x^a)^(b) = a(a - 1)(a - 2)... (a - b + 1)x^a - b, where (x^a)^(b) denotes the m-th derivative of x^a. So we just need to calculate (x(x + 1)(x + 2)... (x + n - 1))^(l)_x = 1, let u = x - 1, it becomes ((u + 1)(u + 2)(u + 3)... (u + n))^(l)_u = 0.

For convenience let f(u) = ((u + 1)(u + 2)(u + 3)... (u + n)). Consider Taylor's series at u = 0(Maclaurin's series), i.e.

We just need to expand f(u), and take the coefficient of x^l, multiply it by l!. By the formula above we know it's |s(n + 1, l + 1)|.

Overall, the formula is:

Hello, I was a writer this time, it's my second round at topcoder. Thanks to cgy4ever for help in preparing problems.

Here's a short editorial and authors code:

div2-easy, TreeAndVertex
Answer is maximal degree. http://pastebin.com/K0nkNvbp

div2-medium, SegmentsAndPoints
Sort points and segements, then greedy. http://pastebin.com/FEu7WPpP

div2-hard, BracketSequenceDiv2
Dynamic programming: d[i][c] = number of non-empty sequences with balance i and last element c (c is '(' or ')'). Add one bracket and change d[i][c] accordingly.
http://pastebin.com/aiEwh1jV

div1-easy, BracketSequenceDiv1
O(2^N / 2) meet-in-the-middle or O(n³) dynamic (d[i][j] number of cbs one can form using s[i:j]). The last is much easier to implement :) .
http://pastebin.com/mM9hi8hu

div1-medium, CyclesNumber
This problem is my personal favorite. Detailed solutions are explained in much detail by jiry_2 and matthew99 (btw, I used the same approach as matthew99 while creating problem).
Expected way to solve was something like this:

• Hmm, is hard to count, what about ?
• is number of ways to choose a permutation and m different cycles from it
• The last sum is c(n + 1, m + 1) (could you prove it combinatorically? Proof is short and nice, in my opinion)
• Find that s(m, t) such that somehow (m is small, one can find s(m, t) by setting k = 1, 2, ..., m in this order, O(m³) overall).
  http://pastebin.com/m5BHKh64

div1-hard, XorPuzzle

Solution always exists, except case n = 2^k and .
The way to find it is better explained by pseudocode:

for i = 0, 1, ...
  u = i
  while a[u] ^ b[u] != c[u]:
    find v such that a[v] ^ b[u] = c[u]
    swap(a[v], a[u])
    if v > i:
       break
    else:
      swap(b[v], b[i + 1])
      u = v

Could you prove it works?
http://pastebin.com/9vQ2TMDi

I apologize for everyone who knew similar problems, hope you enjoyed the round anyway ^_^

I find my approach to Div1Easy as pretty neat, backtrack with memoization which runs in http://ideone.com/5Nlctr

It's

if (SZ(s) - to_cons < SZ(acc)) {
  return 0;
}

that makes it , not O * (2ⁿ).
"acc" keeps word of nonclosed brackets and it can't be longer than .

Can someone help say what is wrong with my attempt at the Div1Easy? It passes all small examples I try by hand, but for the biggest example it gives a WA of 3520.

Code is http://ideone.com/m79V8Y

I know there are better solutions but this is what I came up with: DP on position, number of open round left parens (Lr), number of open square left parens (Ls), and which is the most recent open sequence (0=round and 1=square).

Thanks!

I solved div1. 600 in fairly different way.(I didn't know Stirling numbers before....).

Suppose for a permutation P, we have n circle, and we would like to calculate n^m. We can write down as (c1 + c2 + c3 + .. + cn)^m. We can expand it as n^m tuples (c1', c2', c3', ... cm'). Here ci' can be c1 ~ cn. For a fixed m, final answer is number of different tuples (c1', c2', ... cm'), with one restriction: ci' == cj' or no common element between ci' and cj'. We can see that we only need to consider no more than 300 circles.

We can first calculate DP[N][M] using DP, number of permutations for 1 — N, which has M circles. (Which is actually Stirling number in first kind...). Then We can write final solution F(N, M) as:

Here H[a][M] means: number of distinct m-tuples using 1 ~ a, and each number appears at least one time, which can be calculated using inclusion-exclusion principle.

By simplify above format, it changed to:

We can maintain for needed N. Total complexity is O(NM + M^3).

AC Code: http://ideone.com/cqBGdF

My solution has a large intersection with jiry_2's one, however at the time of writing that post I still don't know what this |s(n + 1, k + 1)| stands for, I used dp to count that (so no prior knowledge about Stirling numbers was neeeded).

If by dp[n][m] we denote numbers of pairs (permutation P on n elements, m cycles within P) then we get formula

(just take a cycle that 1 belongs to and let its length be k), so if we denote $D[n][m] = \frac{dp[n][m]}{n!}$ then we get

which can be easily computed. My code is here: http://ideone.com/M6ampK $O(nm + m^2)$.

And I have also computed those coefficients which turn out to be S(n, k)k! in a more direct way (it's split array) (so again no Stirling numbers :P).

Can someone explain the meet-in-the-middle approach for Div-1 Easy?