An inverse combinatorics week

The March 7 - March 13 week was quite busy with competitions. First off, Codeforces Round 345 featured problems from a contest for high school students in Moscow (problems, results, top 5 on the left). Tourist has continued his string of Codeforces victories, despite taking a bit longer than second-placed TooDifficult to solve all problems.

Just a few hours later, TopCoder SRM 684 featured problems by Adam 'subscriber' (problems, results, top 5 on the left). The deciding hard problem presented a very unusual challenge: given a formal description for counting some unknown combinatorial objects, find out which combinatorial objects are being counted and then come up with a faster way to count them.

Here's the problem statement: you're given an array of N<=50 positive integers, summing up to M<=1000. For each of N! possible permutations of the array, we compute the value M!/(a[0]+a[1])/(a[0]+a[1]+a[2])/.../(a[0]+a[1]+...+a[N-1]) - dividing M! by the product of partial sums of the permuted array, except the first one. What is the sum of those values over all N! permutations?

Coming up with the combinatorial description is pretty hard here, so let me give you a vert small hint: what if the first partial sum wasn't missing - in other words, if the above formula was also divided by a[0]? Which objects does such formula count?

To wrap up the week, Open Cup Grand Prix of Tatarstan presented teams preparing for the ICPC World Finals in Thailand one more chance to test their skills (results, top 5 on the left). Team Past Glory has earned another convincing victory, while team Dreadnought from Shanghai JTU was the first among the teams coming to Thailand - congratulations all!

Problem K was a nice mathematical puzzle. You're given two strings of 0s and 1s with at most 10000 characters in each. You're allowed to take any substring of a string which has an even amount of 1s, and reverse it. Can you obtain the second string from the first string?

I'm sorry for yet another long pause, and hope to get back into the rhythm soon, so check back for new posts!

Tweet