Привет Codeforces!
Мы вернулись и как и в прошлом году, проводим Bubble Cup — соревнование по программированию организуемое силами Центра разработки Microsoft в Сербии (Microsoft Development Center Serbia) на протяжении последних 9 лет. И финал этого года уже на этой неделе!
Учитывая прошлогодний успешный опыт мы вновь решили провести зеркало этого финала на Codeforces! Мы хотели бы поблагодарить MikeMirzayanov и команду Codeforces за замечательную платформу, а также их поддержку в подготовке и проведении. Соревнование начнется 11-ого сентября в воскресение в 11-00 12-00 утра (по Московскому времени). Длительность контеста — 5 часов, будут использоваться правила ACM ICPC. Это будет командный контест на Codeforces, между командами (1-3) человек. Количество задач 9.
Контест подготовлен силами работников MDCS и участниками knightL и Milanin. + спасибо bayleef и vitar за помощь в тестировании.
В виду того что правила этого контеста не совсем обычны для Codeforces (и в виду того что это зеркало) контест будет нерейтинговым.
10 Лучших команд получат футболки (каждому члену команды) +10 футболок будут разданы случайно командам из топ-100.
Обратите внимание что время начала контеста 12:00 по Московскому времени
Автокомментарий: текст был обновлен пользователем ibra (предыдущая версия, новая версия, сравнить).
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
.
Недавно был переход какого-то региона РФ в другой часовой пояс вроде, но я как клятый москаль не следил за деталями конечно)
.
А какая часовая зона стоит на вашем компьютере? Либа, которая, правит время исключительно client-side, работает в вашем браузере на JS.
Если кликнуть на время, на timeanddate будет написано 12МСК.
.
Я живу в московском часовом поясе, и у меня время начала соревнования показано 12:00. Надеюсь, с этой путаницей скоро разберутся.
"Это будет командный контест на Codeforces, между командами (1-3) человек. Количество задач 9."
Эм, а почему тогда есть возможность зарегистрироваться ТОЛЬКО как индивидуальный участник?
Исправил, спасибо.
Now, there is no option for teams :)
Fixed now. Thanks.
Will there be live stats board?
results of Buuble cup onsite will 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.
Автокомментарий: текст был обновлен пользователем ibra (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
i hope i will enjoy :) this is my first time :)
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
А есть тут такие же как я одиночки, желающие объединиться в команду? Конечно сыгранности никакой, но, возможно, вместе наши шансы выше :)
"будут использоваться правила ACM ICPC"
Одновременно можно использовать только один компьютер на команду, я правильно понимаю?
да
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 Fi 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 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).
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 - 1][j
k] * p[k]
dp[i][j] =
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.me/contest/717/submission/20529231
TLE code: http://codeforces.me/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.me/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.