Hi Codeforces!

We strike back from last year to held **Bubble Cup** again — programming competition organized by **Microsoft** Development Center Serbia for last nine years in a row. And this year's final is on this weekend!

Due to last year's successful experience we decided to organize a mirror of this final on Codeforces again. We would like to thank MikeMirzayanov and Codeforces for this great platform and their help. Competition will start at 11-th of September at ~~11 AM~~ 12:00 (Moscow time). Contest will last for 5 hours and will go by ACM ICPC rules. It will be a competition for teams of 1-3 members. There will be 9 problems.

Contest was mainly prepared by employees of MDCS, knightL and Milanin. Additional thanks to bayleef and vitar for their help in testing.

This contest will be unrated (mostly because rules of this contest and not usual for Codeforces and it is still a mirror of onsite competition).

**10 best teams will get T-shirts (each member get one), +10 T-shirts will be distributed randomly to competitors from top 100.**

**Please pay attention to that contest will start at 12:00 (by Moscow time)**

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).Auto comment: topic has been updated by ibra (previous revision, new revision, compare).Inb4 >rated?

?

Greentext = quoting, inb4 = short for "in before"; full meaning: I expect someone to ask if it's rated because they're too lazy to read the whole blog post.

UPD: Explaining when asked for an explanation = downvotes. Yep, just a normal day in CF comments.

Will there be hacks? Will all submissions be tested by system tests during the contest?

No hacks. ACM ICPC rules

Now, there is no option for teams :)

Fixed now. Thanks.

Will there be live stats board?

results of Buuble cup

onsitewill be revealed after the competition.1 PC per team?

No matter

I thought that the mirror is going to be today. Now I have to wait until I can do a rage post about some amazing problems in the problemset... :(

Well, I promised a simple rage post but instead I tried to put my Bubble Cup experience in a bigger picture.

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).i hope i will enjoy . this is my first time :)

what is the difficulty of problems ?

Difficulty is that both divisions can participate. If you competed in last year's mirror, than i would say that difficulty is the same

Is it a rated contest?

Click Here

very hard problem set. matter of satisfaction that it is unrated.

Yeah :D but as it is online mirror, so there is no way of being rated :D

How to solve the first problem?

you have to reverse the given sequence at first. then multiply every term with non reverse one and at lust add all the product. thats the answer.

I am asking about problem A, not C.

You just need to use magic numbers!

20534967

What do you mean by magic numbers?

During the contest, we came up with a summation similar to the following:

where

F_{i}is the ith Fibonacci number. Is this correct? If yes, how to implement it? :/It can be proved simply using recursion the answer is , where

s(n,k) is the coefficient ofx^{k}in the expansion ofx(x- 1)...(x-n+ 1) (Stirling numbers of the first kind). We precalculates(k,j) easily. Hence it suffices to to be able to find for powers 0 ≤p≤k. This can be done using Binet's formula + binomial theorem + geometric series sum. Use a struct to add, subtract, pow, inv, etc for for this purpose. I won't go through the tedious work, but the complexity I think works out to beO(k^{2}).Can you please provide any link where I can learn about these numbers?

How to solve problem G ? :\

You can transform the problem in to :

Given some intervals, each interval cover some points and has a weight. Select a subset of the intervals such that the sum of weight is maximized and there isn't exist any point being covered more than x times.

And this is a classic min cost flow problem.

Node i represent position i in the crossword. Let the interval as from a to b with w weight.

So you should calculate each interval. If crossword[i .. j] equals the word, add interval (i, j + 1, points of the word).

First add edge with x capacity and 0 cost from source to node 0 and from node n to sink. Then add edge with infinite capacity and 0 cost from i to i + 1 for every i < n. Then for each interval add edge with 1 capacity and -w cost from a to b.

The answer is the negative value of min cost flow from source to sink.

This is correct because there is only x flow present. So it restricted each position will not be covered more than x times. And the flow tends to go to the negative edge, so it will give out the minimum value.

Why is it fast enough?

Something like 'Because it is about flows'. My MCMF with stupid Ford-Bellman got AC in 30 ms.

Our too. But it worked 0.5s on our maxtest.

It's O(n.Number_Of_Matches.x), As number of matches is <= nm, we have the total computations are at most 2.5e9 which is reasonable enough, considering how fast CF servers are these days.

Thank you very much , got it :D

How to solve problem D ?

To win the game, the xor of the pile sizes must not be zero. So we find the probability that xor of pile sizes is zero and subtract it from 1.

Consider dp[i][j] which denotes the probability to get xor j for first i piles. The straightforward recurrence is:

dp[i][j]=sum dp[i-1][j^k]*p[k] from k=0 to 100

where ^ is the bitwise xor operator.

But this is not good enough for the problem. We can do better. To calculate dp[i][j], divide i into two piles of size i/2. Then,

dp[i][j^k]+=dp[i/2][j]*dp[i/2][k]

Above is true when i is even. You need to modify it a little when i is odd.

Thank you, got it

Could you, please, elaborate a bit more. Why xor of pile sizes must be zero?

Sprague-Grundy theorem.

Ok, understood.

Now I have difficulties with the next thing below :)

Could you explain how this thing works:

dp[i][j] =dp[i- 1][jk] *p[k]a^a = 0 (xor operation)

a^0 = a

((j^k)^k)=j

Wow, I feel very stupid now.

I am sorry, but I still don't understand how this dp works :(

First player lose if xor of N pile sizes equals to 0.

So you want to know probability, that xor of i pile sizes equals to j

(Answer will be 1 — dp[n][0]).

This fact can be possible if

Facts are independent, so total probability is simply sum of probabilities.

I did the same, but then I thought we must multiply by n! because permutations will matter, so then I completely got confused about how to incorporate n! with fast expo.

btw, its

`dp[i][j^k]+=dp[i/2][j]*dp[i/2][k]`

Yes, thanks!

How to solve problem E ?

As there is always a solution and the size of it doesn't matter,

Do a normal DFS traversal , print each vertex you visit and change the color of it . Once you finish from a child print the current vertex again and change it's color because you will back to it , and if this child's color is pink then visit it again (without it's sub tree)

you have to stop at node 1 or one of it's children , after visiting the last child of node 1 if color[1] is pink then back to it otherwise stop at this child .

this code may help : 20538605

How to solve H?

Can someone please tell me why my same code for D get TLE and AC in different compilers? Thanks!

AC code: http://codeforces.com/contest/717/submission/20529231

TLE code: http://codeforces.com/contest/717/submission/20529203

Your p[100] array is too short, iterating k up to 128 causes undefined behavior.

The compiler does warn you about this. Use and read the warnings.

Yes, the array is short when x=100. I never iterate upto 128 for this array. I don't understand why it got accepted in C++11 compiler when the array size is not sufficient. :P

I fixed the size but it still doesn't help is eliminating the TLE on C++14 compiler.

http://codeforces.com/contest/717/submission/20535200

EDIT: Sorry, I see it now. Thanks for the help! :)

I do like the problems~ so interesting! and it's really lucky to get into the top50~ thanks for the competition ^_^

Problem H: Why does randomly dividing trainers into teams and then randomly dividing teams into two conferences work?

wait for editorial, all explanations will be there

Because pretty much anything in this problem works so you can either spend hours to solve it properly, which in this case is a solution with guaranteed probability, ir just try to submit anything and get AC.

Because the expected number of "crossing" edges in a random team and conference distribution is equal to .

Doesn't the expectation depend on input i.e. wishlist of each trainer and hate pairs?

Can someone tell me how to solve G ? I know that is a min cost flow problem but I don't know how to build the network.

Check out this amazing solution that I discovered for problem D!

Complexity:

O(XlogX)It will be featured in the BC 2016 booklet, along with the proof.