### ibra's blog

By ibra, 4 years ago, ,

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

• +309

 » 4 years ago, # |   +12 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   +7 it's in gym?
•  » » 4 years ago, # ^ |   +24 no it will be a usual contest, just not rated. Will be added to "Contests" very soon
•  » » » 4 years ago, # ^ |   -8 why unrated?I l<3ve rated contests.:( after about 1 week, we have an unrated contest :|
•  » » » » 4 years ago, # ^ |   0 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, ...)
•  » » » » » 4 years ago, # ^ |   0 :( 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.
•  » » » » » » 4 years ago, # ^ |   0 This comment answers your question perfectly http://codeforces.com/blog/entry/20072?#comment-249338
•  » » » » » » » 4 years ago, # ^ |   0 thank you for help and support.so, no way!
 » 4 years ago, # |   +54 Should a team use only one computer?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +17 yes (because onsite competitors will)
•  » » » 4 years ago, # ^ |   +24 Ok, thanks for clarification.Btw. onsite teams consist of 3 people, not 1-2. So argument "because onsite competitors will" is not so strong.
•  » » » » 4 years ago, # ^ |   +7 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."
 » 4 years ago, # |   +23
 » 4 years ago, # |   -16 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.
•  » » 4 years ago, # ^ |   0 We expect that only the strongest teams may close problem set before end of contest (although the may not)
 » 4 years ago, # |   -136 knightL — russia, Simferopol?????? Seems like this guy hasn't visited geography lessons, because of his addiction to problem solving
•  » » 4 years ago, # ^ |   -11 Seems like you hasn't solved problems, because of your addiction to geography lessons, according to your logic XD
•  » » » 4 years ago, # ^ |   -9 Seems like you has'nt learnt English :D
•  » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -46 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?
•  » » 4 years ago, # ^ |   +1 It seems you haven't either. Here is "Codeforces". Not "Geographyforces".
•  » » » 4 years ago, # ^ |   -44 Seems like you don't understand the irony about geography lessons
•  » » » » 4 years ago, # ^ |   -8 Seems like you are really impolite.
•  » » 4 years ago, # ^ |   +46
•  » » 4 years ago, # ^ |   +57 Please don't bring up the Ukraine vs Russia issue here at CF.
 » 4 years ago, # |   +34 Would you show picture of special T-shirts before the contest?
•  » » 4 years ago, # ^ |   +3 Why doesn't ibra answer this question?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +22 Herę are the competitors' shirts.
•  » » » 4 years ago, # ^ |   +4 Are they just for onsite competitors? Or are they prizes?
•  » » » » 4 years ago, # ^ |   0 T-shirts we will send will look like kostka posted, except it will not have your name in the back
 » 4 years ago, # |   -76 I need upvotes PLZ :_(
•  » » 4 years ago, # ^ |   -55 when I say down votes plz => people get down vote | | => up vote = down vote when I say up votes plz => people get down vote |
•  » » » 4 years ago, # ^ |   -16 Don't say "plz"
•  » » 4 years ago, # ^ |   -19 what benefit has if you got many upvotes?and never say "Please"!
 » 4 years ago, # |   0 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?
 » 4 years ago, # |   +38 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.
•  » » 4 years ago, # ^ |   +21 +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?
•  » » » 4 years ago, # ^ |   +1 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!!
•  » » 4 years ago, # ^ |   +4 Good Idea! Since we don't have any other CF round coming, I would support that
•  » » 4 years ago, # ^ | ← Rev. 3 →   +57 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.
•  » » » 4 years ago, # ^ |   -11 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 =)
•  » » » 4 years ago, # ^ |   -8 Well, how about keeping an option for out-of-competition for everyone? That can prevent troll-account, I think.
•  » » » » 4 years ago, # ^ |   0 This is just one of many mentioned issues, not worthwhile.
•  » » » 4 years ago, # ^ |   -9 no one say you must participating in this contest just go to sleep and drinking milk
•  » » » » 4 years ago, # ^ |   +1 ...you dont know him!
 » 4 years ago, # |   -7 after 2 week we have a contest. LOL!!!
 » 4 years ago, # |   0 wish winnig t-shirt for you
 » 4 years ago, # |   +4 Gosh ... I love CF's T-shirts, wish winning T-shirt for you!!!
 » 4 years ago, # |   0 When the contest will be added to the contest list in Codeforces?
 » 4 years ago, # |   +23 Right now, I couldn't register for contest as a team, only as an individual. Am i missing something?
•  » » 4 years ago, # ^ |   0 I have similar problem. Can I re-register like a team? (I register individual by mistake).
•  » » » 4 years ago, # ^ |   +6 Yes, I forget to setup team registration. Just unregister and register later.
•  » » 4 years ago, # ^ |   +6 Sorry, forget to setup team registration. You can unregister and register again later with your team.
 » 4 years ago, # |   0 Nice! so can i join individual or only teams ? and when will be the next round? Thanks
 » 4 years ago, # |   0 i am new here how can i join in the competition
 » 4 years ago, # |   0 How difficult this contest will be? Will it be in the same difficulty with a Div1 contest?
 » 4 years ago, # |   -27 Rated+T-Shirt= very goodUnrated+T-Shirt = goodJust Rated = Rated+T-Shirt — (Unrated+T-Shirt) = very good — good = very So it shows that we have very rated contests without T-Shirt!!!!! :-)
•  » » 4 years ago, # ^ |   0 OK. I understand that it is not funny.
 » 4 years ago, # |   +10 Shouldn't it be "Bubble" instead of "Buble"? (in contests page)
•  » » 4 years ago, # ^ | ← Rev. 2 →   -10 Come on... Comma Counter
 » 4 years ago, # |   +3 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.
•  » » 4 years ago, # ^ |   0 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
 » 4 years ago, # |   +1 are the problems sorted by their difficulty ?
•  » » 4 years ago, # ^ |   0 no
 » 4 years ago, # |   +38 Why top rated team has 3 members ?
 » 4 years ago, # |   +3 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   +4 Auto comment: topic has been updated by ibra (previous revision, new revision, compare).
 » 4 years ago, # |   0 What language can we use? only C++, C#, and Pascal?
•  » » 4 years ago, # ^ |   +3
•  » » » 4 years ago, # ^ |   0 thanks :) I was afraid of that we can't use Java or other languages.
 » 4 years ago, # |   +20 How do I compete if my team member is in a different location?
 » 4 years ago, # |   +6 Will the printed version like pdf be available?
 » 4 years ago, # |   +4 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 ??
•  » » 4 years ago, # ^ |   +12 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 It's more clear now thank you. but, how are the judges going to be sure that this condition is satisfied
•  » » » » 4 years ago, # ^ |   +20 god is watching you
 » 4 years ago, # |   +4 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) ?
 » 4 years ago, # |   +3 Is there any editorial after the contest? Thank you.
•  » » 4 years ago, # ^ |   +3 There will probably be a booklet published here just like 5 previous years.
 » 4 years ago, # | ← Rev. 4 →   0 Sorry, I just left my computer in the hands of some friends of mine :/ You can downvote radoslav11 or ivokaragyozov btw...
•  » » 4 years ago, # ^ |   +11 Never do that.
•  » » 4 years ago, # ^ |   +7 It was radoslav11.
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   0 Where can I choose my Bubble Cup t-shirt's size?
•  » » 4 years ago, # ^ |   +3
 » 4 years ago, # |   -63 What's wrong with this countdown timer? :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18 There is no wrong. You can register in any time before the end of the contest
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 If you think just a little, you can understand what it means.
•  » » » 4 years ago, # ^ |   -22 If you think just a little, you can understand that was a joke
•  » » » » 4 years ago, # ^ |   -14 not enough... I need more downvotes... Let be this post cold as ice, bitches.
•  » » » » » 4 years ago, # ^ |   -11 still not enough
 » 4 years ago, # |   +21 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...
 » 4 years ago, # |   0 There is a good way to win 3 thirts.. Just make 2 new accounts.. And participate with them..
•  » » 4 years ago, # ^ |   +118 Good way to be disqualified!
 » 4 years ago, # |   -6 I couldn't solve anything ;_;
 » 4 years ago, # |   +6 Just woke up now :/
 » 4 years ago, # |   0 Editorial?
 » 4 years ago, # | ← Rev. 2 →   +20 How to solve F? Especially interested in O(n) solution.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +18 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +18 how to recalculate this dp?
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +8 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]
•  » » » 4 years ago, # ^ |   0 Why did you consider only those 2*n+1 points? Is it never beneficial to move to any other point?
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +8 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. :)
 » 4 years ago, # |   +6 How to solve G?
•  » » 4 years ago, # ^ |   0 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 10i where i is number of city visitedthen do dijsktra again and repeat procedure..terminate if path of last 2 dijsktra match
•  » » 4 years ago, # ^ |   0 Hint: minimizing distance is very close to minimizing the number of vertrice passed, as 10 >= maxlen = 9
•  » » » 4 years ago, # ^ |   0 didn't see path length condition .. not that I would be solving it accepted on seeing that :P
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 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).
 » 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, # |   -17 http://codeforces.com/contest/575/submission/12868120 Турист скопипастил венгерский алгоритм с e-maxx-a. Вот уж от кого не ожидал.. даже названия переменных такие же, а уж про пробелы в фориках я молчу.. Больше не мой кумир
•  » » 4 years ago, # ^ |   0 Разве это запрещено правилами контеста?
•  » » » 4 years ago, # ^ |   +3 Я тем же вопросом задавался, но командой решили, что раз на онсайте нельзя было, то и мы не стали.
•  » » 4 years ago, # ^ |   +30 Может просто e-maxx скопипастил код tourist =)
 » 4 years ago, # |   +1 Waiting for the editorial....
 » 4 years ago, # |   +19 I always check oeis for problem with one input :)
•  » » 4 years ago, # ^ |   0 Can you explain how to derive that formula or some easier way to solve it.
 » 4 years ago, # |   0 Anyone solved "B. Bribes" using Heavy Light Decomposition(HLD) ?
•  » » 4 years ago, # ^ |   +8 I attempted, but it was TL. Spent most of the time implementing it :(.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +3 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
•  » » » 4 years ago, # ^ |   +8 But you use HLD only for finding LCA, isn't it?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Yes; I don't use it for counting illegally traversed edges or anything else like that.
 » 4 years ago, # | ← Rev. 3 →   +5 Is there something special about test 5 in problem G?EDIT: This is a tricky test. 7 70 1 11 2 02 3 03 4 04 6 11 5 25 4 0
•  » » 4 years ago, # ^ |   +11 nothing special. just big random test
 » 4 years ago, # |   +17 A just Matrix multiplication with corner cases, isn't it?
•  » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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!
 » 4 years ago, # |   0 How to solve C?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » 4 years ago, # ^ |   +35 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.
•  » » » » 4 years ago, # ^ |   +8 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 ;)
•  » » » » 4 years ago, # ^ |   0 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.?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 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.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +123 This solution can be optimized if you notice that the Hungarian algorithm allows rows to be added one by one, in O(n2) 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(2n·n2).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.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   +17 Why do you need to allocate that much memory? My solution requires time and O(n2) memory.
•  » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 btw this is exactly the author's (mine) solution =)And yes, problem H was born out of this problem =)
 » 4 years ago, # | ← Rev. 2 →   0 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?
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ |   0 Did you ever solve a similar problem before or you came up with the idea when you just saw this problem?
•  » » » » 4 years ago, # ^ |   0 Yes, very similar problem has been given before, and available here — http://acm.timus.ru/problem.aspx?num=1789
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 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?
•  » » » » 4 years ago, # ^ |   0 Police won't catch him in this case.
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » 4 years ago, # ^ |   0 I don't know what confused me so much, now I get it. Thanks!
•  » » 4 years ago, # ^ |   +5 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.
•  » » » 4 years ago, # ^ |   0 I did. I either don't understand the question, or I don't understand the solution.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Is it the answer to my question?My question was designated to @microtony and to @Xellos :)
•  » » » » » 4 years ago, # ^ |   0 No, I meant I already tried a smaller board, and I didn't get the solution.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 4 years ago, # ^ |   +1 Let's say the thief starts at 998 Police Thief 998 1000 999 1000 998 999 997 999 998 998 999 <-- 998 1000 997 999 997 1000 As you can see you'll never catch it.
•  » » » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » » » 4 years ago, # ^ |   0 The police don't move, they go to the districts you choose by helicopter.
•  » » » » » » » » » 4 years ago, # ^ |   0 microtony Thanks. But what about the situation I mentioned here
 » 4 years ago, # | ← Rev. 2 →   +6 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 :)
•  » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 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)
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +8 I see, but my solution is O(N) :)
•  » » » » 4 years ago, # ^ |   0 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 — just O(20) and not O(N / 20).Then, we can find the new subset of positions where the thief can be for N = 105 in N / 20 variable assignments (=) and O(20) more complex actions. Together with the O(20·220) precomputation above, it's an O(M(N / 20 + 20) + 2·220) algorithm for the whole problem, and the part with O(MN / 20) is exactly MN / 20 assignments, so it should be fast.If we had 2 rows, we'd need half as wide chunks (width 10, but still 220 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.
 » 4 years ago, # |   +16 "Post with editorial, results and T-shirts will be posted a bit later"what does "a bit" mean??
•  » » 4 years ago, # ^ |   +136 A bit means a single binary value, either 0 or 1.
 » 4 years ago, # |   +11 Why does this work? 12873839
•  » » 4 years ago, # ^ |   +5 Во-первых,можно заметить, что уходить в другую сторону от отрезка где будет гореть лампочки бессмысленно. Мы либо можем остаться на своем месте, либо приблизиться к отрезку где горят лампочки. Допустим, что мы можем уменьшить штраф, если пойдем в другую сторону. Понятно, что в текущем ходе, мы только увеличим штраф, если пойдем в другую сторону, а если это необходимо для будущего хода, то тогда мы можем просто стоять на месте, и когда наступить момент, что мы можем уменьшить штраф, то мы его уменьшаем. Во-вторых, если например, мы стоим левее от отрезка где горят лампочки, то нам уходить правее чем li, тоже ничего хорошего не даст. Допустим, что нам нужно идти правее от li для уменьшение штрафа в будущем, тогда мы можем просто стоять на место до наступление момента, когда мы сможем уменьшить штраф. Аналогично, если мы стоим правее. Теперь, можно хранить отрезок (ll, rr), чтобы в этом отрезке штраф для всех точек были равны и принимало минимальное значение штрафа после i-го хода.В таком случае, мы никак не ухудшаем ответ.
•  » » » 4 years ago, # ^ |   0 Is there O(n) solution for this problem? I made O(n) and have WA on test 5. What special is in this test?