ibra's blog

By ibra, history, 4 years ago, translation,

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)

• +146

 » 4 years ago, # |   0 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   -96 Inb4 >rated?
•  » » 4 years ago, # ^ |   +10 ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -72 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.
 » 4 years ago, # |   0 Will there be hacks? Will all submissions be tested by system tests during the contest?
•  » » 4 years ago, # ^ |   +25 No hacks. ACM ICPC rules
 » 4 years ago, # |   +30 Now, there is no option for teams :)
•  » » 4 years ago, # ^ |   +8 Fixed now. Thanks.
 » 4 years ago, # |   0 Will there be live stats board?
•  » » 4 years ago, # ^ |   +5 results of Buuble cup onsite will be revealed after the competition.
 » 4 years ago, # |   +7 1 PC per team?
•  » » 4 years ago, # ^ |   -22 No matter
 » 4 years ago, # |   +6 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... :(
•  » » 4 years ago, # ^ |   +10 Well, I promised a simple rage post but instead I tried to put my Bubble Cup experience in a bigger picture.
 » 4 years ago, # |   0 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   +2 i hope i will enjoy . this is my first time :)
 » 4 years ago, # |   +5 what is the difficulty of problems ?
•  » » 4 years ago, # ^ |   +8 Difficulty is that both divisions can participate. If you competed in last year's mirror, than i would say that difficulty is the same
 » 4 years ago, # |   0 Is it a rated contest?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18
•  » » 4 years ago, # ^ |   0 NO it's not.
•  » » » 4 years ago, # ^ |   0 how can i register now for this contest?
 » 4 years ago, # | ← Rev. 2 →   +7 very hard problem set. matter of satisfaction that it is unrated.
•  » » 4 years ago, # ^ |   0 Yeah :D but as it is online mirror, so there is no way of being rated :D
 » 4 years ago, # |   +8 How to solve the first problem?
•  » » 4 years ago, # ^ |   +3 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 I am asking about problem A, not C.
•  » » » » 4 years ago, # ^ |   0 i'm very sorry. i miss understood.
•  » » 4 years ago, # ^ |   0 You just need to use magic numbers!20534967
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +8 What do you mean by magic numbers?During the contest, we came up with a summation similar to the following: where Fi is the ith Fibonacci number. Is this correct? If yes, how to implement it? :/
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 It can be proved simply using recursion the answer is , where s(n, k) is the coefficient of xk in the expansion of x(x - 1)...(x - n + 1) (Stirling numbers of the first kind). We precalculate s(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 be O(k2).
•  » » » 4 years ago, # ^ |   0 Can you please provide any link where I can learn about these numbers?
 » 4 years ago, # |   +8 How to solve problem G ? :\
•  » » 4 years ago, # ^ | ← Rev. 4 →   +18 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.
•  » » » 4 years ago, # ^ |   0 Why is it fast enough?
•  » » » » 4 years ago, # ^ |   0 Something like 'Because it is about flows'. My MCMF with stupid Ford-Bellman got AC in 30 ms.
•  » » » » » 4 years ago, # ^ |   0 Our too. But it worked 0.5s on our maxtest.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 Thank you very much , got it :D
 » 4 years ago, # |   0 How to solve problem D ?
•  » » 4 years ago, # ^ | ← Rev. 6 →   +2 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 100where ^ 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.
•  » » » 4 years ago, # ^ |   0 Thank you, got it
•  » » » 4 years ago, # ^ |   0 Could you, please, elaborate a bit more. Why xor of pile sizes must be zero?
•  » » » » 4 years ago, # ^ |   0 Sprague-Grundy theorem.
•  » » » » » 4 years ago, # ^ |   0 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]
•  » » » » » » 4 years ago, # ^ |   0 a^a = 0 (xor operation)a^0 = a ((j^k)^k)=j
•  » » » » » » » 4 years ago, # ^ |   0 Wow, I feel very stupid now.I am sorry, but I still don't understand how this dp works :(
•  » » » » » » » » 4 years ago, # ^ |   +1 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 i-th pile have size 0 and xor of [i — 1] pile sizes equals to (j xor 0). i-th pile have size 1 and xor of [i — 1] pile sizes equals to (j xor 1). ... i-th pile have size 1 and xor of [i — 1] pile sizes equals to (j xor x). Facts are independent, so total probability is simply sum of probabilities.
•  » » » 4 years ago, # ^ |   +4 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]
•  » » » » 4 years ago, # ^ |   0 Yes, thanks!
»
4 years ago, # |
-36

include<math.h>

using namespace std;

int factorial(int n) { if(n==1) return 1; else return n*factorial(n-1); }

int main() { int k,l,r; int p,q; int numWays=0, total=0; cin>>k>>l>>r;

for(int length=l; length<=r; length++)
{
p=length+1;
q=0;
while(p>=q)
{
numWays+=factorial(p)/(factorial(p-q)*factorial(q));
p--;
q++;
}
total+=factorial(numWays)/(factorial(numWays-k)*factorial(k));
}

cout<<total;

return 0;

}

This code for the A part exceeded time limit. So how do you solve part A?

 » 4 years ago, # |   +5 How to solve problem E ?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 4 years ago, # ^ |   0 thanks very much
 » 4 years ago, # |   0 How to solve H?
 » 4 years ago, # |   0 Can someone please tell me why my same code for D get TLE and AC in different compilers? Thanks!
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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. :PI fixed the size but it still doesn't help is eliminating the TLE on C++14 compiler.http://codeforces.com/contest/717/submission/20535200EDIT: Sorry, I see it now. Thanks for the help! :)
 » 4 years ago, # |   +3 I do like the problems~ so interesting! and it's really lucky to get into the top50~ thanks for the competition ^_^
•  » » 4 years ago, # ^ |   0 XD
 » 4 years ago, # |   +5 Problem H: Why does randomly dividing trainers into teams and then randomly dividing teams into two conferences work?
•  » » 4 years ago, # ^ |   +6 wait for editorial, all explanations will be there
•  » » 4 years ago, # ^ |   +18 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.
•  » » 4 years ago, # ^ |   0 Because the expected number of "crossing" edges in a random team and conference distribution is equal to .
•  » » » 4 years ago, # ^ |   0 Doesn't the expectation depend on input i.e. wishlist of each trainer and hate pairs?
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   +5 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.