Hi Codeforces!

As you already know from previous post, Bubble Cup is a programming competition organized by Microsoft Development Center Serbia for eight year in a row. And the finals is coming!

This year we came up with a wonderful idea to have an online mirror of the finals on Codeforces! We would like to thank MikeMirzayanov and Codeforces team for their work and support in making this happen.

**The online competition will be held on 6th of September, Sunday 11-00 AM (Moscow time).** The competition will last for five hours and it will run with the standard **ACM ICPC rules**. This will be a team contest on Codeforces, with teams consisting of up to three people. Amount of problems(7-10) will be anounced later.

Contest was mainly prepared by employees of MDCS (+ special thanks to knightL and Milanin for great help).

This contest will be unrated (mostly because rules of this contest and not usual for Codeforces (and it is first time we organize this kind of mirror).

10 best teams will receive our special **T-shirts** (each team member) +10 t-shirts will be handed out randomly to other participants of the top 100.

**UPD please pay attention to that we updated maximal possible number of people in a team**

**Post with editorial, results and T-shirts will be posted a bit later**

**UPD Link to results and editorial post**

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).it's in gym?

no it will be a usual contest, just not rated. Will be added to "Contests" very soon

why unrated?

I l<3ve rated contests.

:( after about 1 week, we have an

unratedcontest :|I will tell you a secret: I love rated contests too (I guess everyone does). I was disappointed when heard that we will have to make it unrated too. But this contest is really very different from usual contests (team contest, 5 hours, ACM rules, ...)

:( so, no way?

it isn't possible to make it rated?

what is the problem?

yeah, I know, it's unusual but I think it isn't a big problem.

if some one can solve 2 problems in 2 hours, he can solve 3 or 4 in 5 hours, and the team isn't problem, any one can have a team. he can join a good team!!.

and ACM rules are not so unusual.

if there is a way that make this contest rated, please do.

great thanks,sorry for my bad English.

This comment answers your question perfectly

http://codeforces.com/blog/entry/20072?#comment-249338

thank you for help and support.

so, no way!

Should a team use only one computer?

yes (because onsite competitors will)

Ok, thanks for clarification.

Btw. onsite teams consist of 3 people, not 1-2. So argument "because onsite competitors will" is not so strong.

Also onsite competitors are, of course, in one location and also we will not be competing directly against them anyway (so why should their rules restrict us when our team members might not be in the same place?). Perhaps it would be best to do what vk cup finals mirror did:

"Note that during the round the team is allowed to use only one computer. This means that you may code/use console/succeed in solving problems in any other manner by using only one computer at time. The only thing that is allowed from two computers is reading the statements."

Time conversions

5 hours and just 7-10 problems? It seems to me that this problems should be really hard, or some teams can close problemset very fast.

We expect that only the strongest teams may close problem set before end of contest (although the may not)

knightL — russia, Simferopol?????? Seems like this guy hasn't visited geography lessons, because of his addiction to problem solving

Seems like you hasn't solved problems, because of your addiction to geography lessons, according to your logic XD

Seems like you has'nt learnt English :D

Let's check who has written a respond...of course, it's a russian guy! So, man, have you already called putin to claim "введи войска", because your "native brother" is been humiliated by ukrop?

It seems you haven't either. Here is "Codeforces". Not "Geographyforces".

Seems like you don't understand the irony about geography lessons

Seems like you are really impolite.

Please don't bring up the Ukraine vs Russia issue here at CF.

Would you show picture of

special T-shirtsbefore the contest?Why doesn't ibra answer this question?

Herę are the competitors' shirts.

Are they just for onsite competitors?

Or are they prizes?

T-shirts we will send will look like kostka posted, except it will not have your name in the back

I need upvotes PLZ :_(

when I say down votes plz => people get down vote | | => up vote = down vote when I say up votes plz => people get down vote |

Don't say "plz"

what benefit has if you got many upvotes?

and never say "Please"!

I want to participate in this competition with a friend, how does it work? We both register and then only one of us logs in and we use one laptop with only one logged in session?

Would someone mind elaborating on the reasons that the Bubble Cup mirror will not be rated? While I still plan on participating, I find I tend to enjoy rated contests more than un-rated ones, because I feel that more is at stake.

+1. Rating is a cool motivation and in my opinion such unusual contests should be rated to. It won't be similar to CF-round but what's wrong with that?

Mr. Mike can play a trick by announcing them as rated first and then turning them unrated later! Enjoyment should not be put to stake!!

Good Idea! Since we don't have any other CF round coming, I would support that

I don't like weird rated contests, they are doing weird things with ratings. Especially when all those 1 and 2 persons teams are included. Moreover it is long, 5 hours. Pretty far from typical CF round, I wouldn't appreciate having it rated. Moreover for me it will be 1-6AM, so I will probably participate, but will go to sleep in the middle, probably I'm not the only one, who can participate in a proper subset of those 5h, rating this will prevent me from participating or maybe I will use troll-account which you also don't want to :P.

Another argument could be that this contest will not be "Codeforces approved" in a meaning that CF staff has not anything to do with preparing problems, that's kinda like 'outsourcing evaluating own rating', not something company would like to do :P. CF rating should be based on CF-created contests.

In terms of motivation you have T-shirts here.

EDIT: Little clarification, by 'weird' of course by no means I meant something negative. I just meant that there are many factors which cause that this contests is significantly different than typical CF round.

Totally agree with first paragraph.

About second: as far as I know (this is second contest I participate in preparing of) Codeforces team do not help to prepare problems, mostly reviewing, translating, advising. From this point of view, you can be sure, problems were reviewed by Codeforces team and approved.

About T-shirts. I haven't seen T-shirts competitors will get, but I got mine as author and it is awesome — probably the best T-shirt I have ever got from competitions (I guess/hope competitiors' T-shirts will be almost the same =)

Well, how about keeping an option for out-of-competition for everyone? That can prevent

troll-account, I think.This is just one of many mentioned issues, not worthwhile.

no one say you must participating in this contest just

go to sleep and drinking milk

...you dont know him!

after 2 week we have a contest. LOL!!!

wish winnig t-shirt for you

Gosh ... I love CF's T-shirts, wish winning T-shirt for you!!!

When the contest will be added to the contest list in Codeforces?

Right now, I couldn't register for contest as a team, only as an individual. Am i missing something?

I have similar problem. Can I re-register like a team? (I register individual by mistake).

Yes, I forget to setup team registration. Just unregister and register later.

Sorry, forget to setup team registration. You can unregister and register again later with your team.

Nice! so can i join individual or only teams ? and when will be the next round? Thanks

i am new here how can i join in the competition

How difficult this contest will be? Will it be in the same difficulty with a Div1 contest?

Rated+T-Shirt= very good

Unrated+T-Shirt = good

Just Rated = Rated+T-Shirt — (Unrated+T-Shirt) = very good — good = very So it shows that we have very rated contests without T-Shirt!!!!! :-)

OK. I understand that it is not funny.

Shouldn't it be "Bubble" instead of "Buble"? (in contests page)

Come on...

Comma Counter

There were a lot of questions about how difficult this contest will be.

Well, I am not sure =). It will have both difficult and easy problems, both for Div1 and Div2 participants. I think couple of top teams may solve all the problems before time ends.

Would be better if this contest is for three members for each team, like acm-icpc!

The official rules says that : http://www.bubblecup.org/Rules-and-Instructions1

are the problems sorted by their difficulty ?

no

Why top rated team has 3 members ?

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).What language can we use? only C++, C#, and Pascal?

http://codeforces.com/help?locale=en#q4

thanks :) I was afraid of that we can't use Java or other languages.

How do I compete if my team member is in a different location?

Will the printed version like pdf be available?

Hey,

I registered as a team, but the problem is that we live far away from each others so each member will read and solve problems on a standalone machine, but submission's will be sent from one machine only.

Is this ok with contest rules ??

It's not about submitting from the same computer. It's about working on only one computer in each moment. So not being in the same place is ok as long as you communicate with each other and there is no moment when two of you work with computers at the same time.

It's more clear now thank you. but, how are the judges going to be sure that this condition is satisfied

god is watching you

I have one question :

It's certain that all top 10 teams won't contain three members. Will you give extra t-shirts for top 100 participants ( 30 — all top 10 users) ?

Is there any editorial after the contest? Thank you.

There will probably be a booklet published here just like 5 previous years.

Sorry, I just left my computer in the hands of some

friendsof mine :/ You can downvote radoslav11 or JustInCase btw...Never do that.

It was radoslav11.

If its a team contest, that too 5 hours long, it is not fair to everyone if the contest is rated. On a lighter note, as far as motivation goes, not getting a negative rating change is enough motivation for me.

Where can I choose my Bubble Cup t-shirt's size?

http://codeforces.com/settings/general

What's wrong with this countdown timer? :)

There is no wrong. You can register in any time before the end of the contest

If you think just a little, you can understand what it means.

If you think just a little, you can understand that was a joke

not enough... I need more downvotes... Let be this post cold as ice, bitches.

still not enough

It's pretty bad that it is rather impossible to get a penalty for wrong solution for problem D. There is only one test there...

There is a good way to win 3 thirts.. Just make 2 new accounts.. And participate with them..

Good way to be disqualified!

I couldn't solve anything ;_;

Just woke up now :/

Editorial?

How to solve F? Especially interested in O(n) solution.

All possible locations consists of points {initial point, Lstart points, Lend points}.

To obtain best result, in each turn it is sufficient to move to one of the 2*n+1 points suggested above. So, this dynamic programming works:

dp(i, j) = minimum summed cost, if we already made

iturns, and we are at pointj.how to recalculate this dp?

dp[i][j] = distance between light[i] and point x[j] +

min of

min(dp[i-1][k]+x[j]-x[k], where x[k]<x[j]) or

min(dp[i-1][k]+x[k]-x[j], where x[j]<x[k])

Let's calculate first part, second part is quite similar.

We need to find, min {dp[i-1][k] — x[k]} + x[j] and where x[k] < x[j].

So we just keep minimum value of dp[i-1][k] — x[k] we found so far.

Why did you consider only those 2*n+1 points? Is it never beneficial to move to any other point?

Let say that we have two lights (5..7), (9..10). And you are at point 0.

So if you move to point 5, you will have free cost for light, but distances is increased by 5. But if you don't move then cost for light will increase by 5, but distance won't. So you could use option 1.

Something like that. :)

How to solve G?

looks like dijsktra + dynamic programming, i have a brute force solution which may be slow and wrong.

do dijsktra once .. make sure u multiply the path weights by 10

^{i}where i is number of city visitedthen do dijsktra again and repeat procedure..

terminate if path of last 2 dijsktra match

Hint: minimizing distance is very close to minimizing the number of vertrice passed, as 10 >= maxlen = 9

didn't see path length condition .. not that I would be solving it accepted on seeing that :P

Let's make BFS from node 0. d[v] — distance from 0 to v. For simplicity initially let's suppose there is no leading 0 in answer. In this case, we are sure that answer has length d[n — 1]. For each distance starting from d[n — 1] to 0 we will find set of optimal nodes. d[n — 1] it is only node n — 1. For next distance we will take the nodes which are reachable by the most cheapest edge (greedily).

To work with leading 0's we just make another bfs from n-1 by only 0 edges and start previous algorithm on some set of nodes which are reachable from n-1 by 0 edges and has smallest distance from node 0.

Complexity O(n + m).

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).http://codeforces.com/contest/575/submission/12868120 Турист скопипастил венгерский алгоритм с e-maxx-a. Вот уж от кого не ожидал.. даже названия переменных такие же, а уж про пробелы в фориках я молчу.. Больше не мой кумир

Разве это запрещено правилами контеста?

Я тем же вопросом задавался, но командой решили, что раз на онсайте нельзя было, то и мы не стали.

Может просто e-maxx скопипастил код tourist =)

Waiting for the editorial....

I always check oeis for problem with one input :)

Can you explain how to derive that formula or some easier way to solve it.

Anyone solved "B. Bribes" using Heavy Light Decomposition(HLD) ?

I attempted, but it was TL. Spent most of the time implementing it :(.

Here's my LCA implementation using HLD. It ran in 873 ms, out of 1000. (Only noticed that just now.)

[edit: Using scanf instead of cin, it runs in around 300 ms]

http://codeforces.com/contest/575/submission/12870310

But you use HLD only for finding LCA, isn't it?

Yes; I don't use it for counting illegally traversed edges or anything else like that.

Is there something special about test 5 in problem G?

EDIT:This is a tricky test.nothing special. just big random test

A just Matrix multiplication with corner cases, isn't it?

Yes It's the worst problem I've ever seen. I wrote 6 kilos and still searching the bugs...I also made a segment tree to help

Me really too lazy to write segment tree but my TLE5 says I have to write it.

Or Partitial multiplications.

P.S. Yeeeeaaahhhhh, finally got AC!

How to solve C?

Let's say you know that the first N/2 people should go clubbing on Friday and the rest on Saturday. This becomes a simple case of the assignment problem which can be solved in O(N^3) using the Hungarian algorithm. Since there can be N Choose N/2 different combinations of which N/2 people should go clubbing on Friday, just check all possible combinations and run weighted bipartite matching and take the maximum. Complexity is N Choose N/2 * N^3 = 10^9 when N = 20, which passes with some optimizations.

If that is intended solution problem is very bad. It's even more than 10^9 (1.5 * 10^9). I tried that solution and when it timed out I gave up because I thought there must be smarter solution in which I dont have to optimize execution time.

In the end I just optimized memory consumption of simple DP approach. It needs 2^20 ints which is 4 megabytes and it's too much. Because maximum sum possible is up to 2e7 we can use 26 bit ints instead and spend around 3.5 megabytes. I got accepted but I like it even less than hungarian algorithm solution.

I agree. If this is the intended solution, the time limit should have been at least 3 seconds. Nevertheless, I enjoyed solving the problem for some reason.

Your solution is nice, but if this is the author's solution, I have nothing else to say ;)

Huh, in high school I somehow got hardcoded in my mind that we always have to leave at least ~4MB safety buffer, because it can disappear from some mysterious reason like included libraries, whatever, I haven't ever really delved into that. I even experienced that I tried to upsolve one problem with ML 32MB and I used 28MB and I was getting MLE and couldn't get rid of it. So in this problem I was afraid of allocating more than 1MB and now you say that you used 3,5MB and got AC.

Do you know something more on this subject? Maybe because of some reason 0,5MB buffer here was sufficient or maybe CF computes usage of memory based on memory used directly by us and exclude that used indirectly through some libraries etc.?

I don't know anything exact. I guess it depends on libraries included, compiler used and environment in which program is ran. Also it's not easy to measure it so we get all kinds of overheads on different judges. For example on SPOJ for C++ programs it's usually around 2.5MB and here on CF (I used custom invocation for this during the round) it's few KB. But yeah, what you said sounds right, it seems like CF manualy excludes some memory not allocated directly by us.

This solution can be optimized if you notice that the Hungarian algorithm allows rows to be added one by one, in

O(n^{2}) each. The complexity becomes if the combinations are generated using recursion.edit: actually this may be a wrong bound if the number of valid prefixes at each recursion depth doesn't behave exponentially, but at least it is not worse than

O(2^{n}·n^{2}).edit: now I've realized the connection of this problem with problem H, which is pretty funny :) According to OEIS the total number of valid prefixes is , so the bound is correct.

Indeed, I observed that but tried with the simpler approach at first which got accepted in 1.95 s. It can be precisely N Choose N/2 * N^2 if you can allocate the same amount of memory.

Why do you need to allocate that much memory? My solution requires time and

O(n^{2}) memory.My bad, I thought of generating all valid subsets iteratively. If implemented recursively as in your solution, it becomes O(N^2) in memory. Sorry I just realized that now since I didn't think much about it after getting accepted in N^3.

btw this is exactly the author's (mine) solution =)

And yes, problem H was born out of this problem =)

Someone please explain solution of D. I saw some accepted solutions, and I don't get it. Sorry, if this is a very easy question, but I just don't get it .

edit : How can we catch the thief in two line-sweeps?

If currently the thief is at an odd position, next hour he will be at an even position. First assume the thief is at odd position. If we check position 2, that means the thief could only be at even position >= 4. So next hour we check position 3, thief cannot choose to go left because we'll be checking that, he is forced to go to 5. Continuing that we check until position 999. After checking position 999 we check 999 again. This forces the thief to fall onto us.

That's half of the story. If the thief was at odd position initially, we would have caught it. But what if the thief is at even position initially?

Notice that after (999 — 2 + 1) + 1 hours, the initially even position thief would now be at odd position. Therefore we can simply repeat the above process again.

That makes the total number of hours required 999 * 2 = 1998.

Did you ever solve a similar problem before or you came up with the idea when you just saw this problem?

Yes, very similar problem has been given before, and available here — http://acm.timus.ru/problem.aspx?num=1789

x-police,o-thief,#-unoccupied. I am thinking about this:

at time t=tn

....x#.......

....xo.......

at time t=tn+1

....#x.......

....ox.......

assuming police uses helicopter to reach the cities, the thief easily gets away, doesn't he?

Police won't catch him in this case.

microtony Thanks a lot for clearing that up. The poblem says...

"Output is given in chronological order (i-th line contains districts investigated during i-th hour) and should guarantee that the thief is caught in no more than 2015 hours, regardless of thief’s initial position and movement."

So, what did the problem actually mean? I am totally confused now.

I think you don't understand the problem? It is a output-pnly task. The sample output only illustrates the format and is a "Wrong answer".

The problem asks you to output a strategy that catches the thief all the time, not something that doesn't work or works some of the time.

I don't know what confused me so much, now I get it. Thanks!

Draw pictures for e.g. a 4x2 board instead of 1000x2, it's pretty clear from that. (

`#`

is a cell we just blocked,`,`

a cell where the thief can't be,`o`

a cell where he can be)Thanks to the first pass, the thief is forced to be in even/odd columns alternately on even/odd seconds.

I did. I either don't understand the question, or I don't understand the solution.

Is it the answer to my question?

My question was designated to @microtony and to @Xellos :)

No, I meant I already tried a smaller board, and I didn't get the solution.

My solution failed 12866559

I tried to solve this by deploying police in similar way one above each other but keeping them for 2 hours and then moving forward from one end to another so that thief if try to cross he will be caught. Since he has no move as (x,y-1) or (x,y+1) he cannot alternate at same x this will force thief to one end and he will be caught.

How he escaped from (1,1) i am not able to undestand.as i am coming from 1000 column he can move only in city.

Someone please explain my approach is wrong or i understood the problem totally wrong

UPD-Understood the cause of failure.Let's say the thief starts at 998

As you can see you'll never catch it.

microtony So, not only does police catch thief while investigating the city the thief is in, but also when he is crossing them? This was not in the problem statement.

The police don't move, they go to the districts you choose by helicopter.

microtony Thanks. But what about the situation I mentioned here

Problem D actually appeared in a contest 5 years ago on Timus.

Also writing the checker for this problem is more interesting, when constraints are 10^5. This problem also appeared in mentioned contest. There was randomized DP that passed during that contest (but more tests were added later). Though there is a very beautiful deterministic solution :)

Well... I noticed that this problem was similar to one on Timus when it was too late to change anything. I've actually solved both these problems long time ago, though it seems I have not-so-beautiful solution with bitmasks for the second one.

Bitmasks was the first thing I thought of as well for the second one :D.

Coincidentally, I solved a slightly similar problem to this D with an arbitrary tree and one person yesterday.

Uhm, what is this bitmask solution you guys are talking about?

My solution for 2nd problem was going backward & maintain possible positions of the thief (separatedly for odd & even positions)

I guess it must be pretty similar solution. Let's have an array of bits pos[N]. pos[i] equals one iff a thief can be at position [i]. After an attempt to find him at v we set pos[v]=false. and pos on next step equals to (pos<<1 or pos>>1). He will get away if there is at least one non-zero bit after all steps. The complexity is N^2/64.

I see, but my solution is O(N) :)

Subproblem that we want to solve in something like

O(N/something): there are some allowed moves (small, at most +-1 in each coordinate), a set of possible positions of the thief and we want to know that set after the thief moves.We'll split the array into chunks of size... let's say 20. For each of them and each subset of possible positions of the thief, we can calculate what new subset this would turn into if we only considered possible positions of the thief in it (basically the solution for our subproblem for

N= 20); of course, there are still 2 positions outside it that can influence the subset it'd turn into, but checking them is fast — justO(20) and notO(N/ 20).Then, we can find the new subset of positions where the thief can be for

N= 10^{5}inN/ 20 variable assignments (`=`

) andO(20) more complex actions. Together with theO(20·2^{20}) precomputation above, it's anO(M(N/ 20 + 20) + 2·2^{20}) algorithm for the whole problem, and the part withO(MN/ 20) is exactlyMN/ 20 assignments, so it should be fast.If we had 2 rows, we'd need half as wide chunks (width 10, but still 2

^{20}subsets), so it'd be slower, but that problem has one row. I'm pretty sure there wouldn't be any trouble even with a slower judging system."Post with editorial, results and T-shirts will be posted a bit later"

what does "a bit" mean??

A bit means a single binary value, either 0 or 1.

Why does this work? 12873839

Во-первых,можно заметить, что уходить в другую сторону от отрезка где будет гореть лампочки бессмысленно. Мы либо можем остаться на своем месте, либо приблизиться к отрезку где горят лампочки. Допустим, что мы можем уменьшить штраф, если пойдем в другую сторону. Понятно, что в текущем ходе, мы только увеличим штраф, если пойдем в другую сторону, а если это необходимо для будущего хода, то тогда мы можем просто стоять на месте, и когда наступить момент, что мы можем уменьшить штраф, то мы его уменьшаем. Во-вторых, если например, мы стоим левее от отрезка где горят лампочки, то нам уходить правее чем

l_{i}, тоже ничего хорошего не даст. Допустим, что нам нужно идти правее отl_{i}для уменьшение штрафа в будущем, тогда мы можем просто стоять на место до наступление момента, когда мы сможем уменьшить штраф. Аналогично, если мы стоим правее. Теперь, можно хранить отрезок (ll,rr), чтобы в этом отрезке штраф для всех точек были равны и принимало минимальное значение штрафа послеi-го хода.В таком случае, мы никак не ухудшаем ответ.Is there

O(n)solution for this problem? I made O(n) and have WA on test 5. What special is in this test?