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

yes (because onsite competitors will)

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

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

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

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

Why doesn't ibra answer this question?

Herę are the competitors' shirts.

what benefit has if you got many upvotes?

and never say "Please"!

+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?

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.

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

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

Come on...
Comma Counter

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

no

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

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.

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

Never do that.

It was radoslav11.

http://mirror.codeforces.com/settings/general

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.

Good way to be disqualified!

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 i turns, and we are at point j.

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

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).

вы правы. проглядел я это. извиняемся

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

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

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://mirror.codeforces.com/contest/575/submission/12870310

nothing special. just big random test

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

Скорее всего, что я неправильно понял условие, поэтому решил спросить.

Вор обязан сдвинуться с текущей вертикали, так что достаточно сделать 2 прохода по горизонталям. Пусть вор вначале был в четной вертикали, тогда мы его всегда поймаем при втором проходе, иначе — при первом

вор в каждый момент времени находится либо на четной либо на нечетное клетке, с каждым ходом эта четность чередуется.

Я сначала тоже подумал, что решения нет, но потом заметил, что вверх/вниз ходить нельзя.

Есть точно такая задача на Тимусе: Задача

Простое решение: 2000 ходов от 1 до 1000 и от 1000 до 1.

Доказать это решение можно вот как: при первом проходе от 1 до 1000 мы исключаем возможность начального положения преступника в нечетных клетках. Допустим после этого вор стоит в 999 клетке, а мы в 1000, тогда сделав повторный ход в 1000 мы изменим четность вора: он уйдёт в 998 клетку. И после этого вор никогда не сможет подойти к нам впритык, чтобы перепрыгнуть.

Очень известная и старая задача про мышку. например вот. Честно говоря, непонятно, как такие широко известные задачи попадают на контесты такого уровня.

Я прошелся по клеткам от (1,1) и (1,2) до (1000,1) и (1000,2), чтобы 100% поймать вора, так как проверка (х,1) и (х,2) делается с гарантией, что в столбцах до х вора нет, он идет направо. Но почему-то неправильный ответ. Тогда еще прошелся в обратном направлении от 1000 до 1 и он ловится. Сейчас я понял, почему он не ловился в первом проходе и ловился во втором. Я сделал случайно два раза проверку (1000,1) и (1000,2), и вор попадается из-за четности-нечетности :)

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 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.

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)

oooo     #ooo     o#oo     ,o#o     #,o,     ,#,o     ,,#,     ,,,,
oooo ... #ooo ... o#oo ... ,o#o ... #,o, ... ,#,o ... ,,#, ... ,,,,

Thanks to the first pass, the thief is forced to be in even/odd columns alternately on even/odd seconds.