ibra's blog

Bubble Cup finals mirror on Codeforces
By ibra, 9 years ago, In English

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

  • Vote: I like it
  • +309
  • Vote: I do not like it

Comments Comments (156)
| Write comment?
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

it's in gym?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      why unrated?

      I l<3ve rated contests.

      :( after about 1 week, we have an unrated contest :|

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
9 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Should a team use only one computer?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    yes (because onsite competitors will)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Ok, thanks for clarification.

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Time conversions

→ Reply
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -136 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Seems like you has'nt learnt English :D

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it -46 Vote: I do not like it

      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?

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Seems like you are really impolite.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Would you show picture of special T-shirts before the contest?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why doesn't ibra answer this question?

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    Herę are the competitors' shirts.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Are they just for onsite competitors?
      Or are they prizes?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it -76 Vote: I do not like it

I need upvotes PLZ :_(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    what benefit has if you got many upvotes?

    and never say "Please"!

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +57 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Well, how about keeping an option for out-of-competition for everyone? That can prevent troll-account, I think.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is just one of many mentioned issues, not worthwhile.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      no one say you must participating in this contest just

      go to sleep and drinking milk

      → Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wish winnig t-shirt for you

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

are the problems sorted by their difficulty ?

→ Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Why top rated team has 3 members ?

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What language can we use? only C++, C#, and Pascal?

→ Reply
»
9 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will the printed version like pdf be available?

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there any editorial after the contest? Thank you.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Sorry, I just left my computer in the hands of some friends of mine :/ You can downvote radoslav11 or JustInCase btw...

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -63 Vote: I do not like it

What's wrong with this countdown timer? :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I couldn't solve anything ;_;

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Just woke up now :/

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      how to recalculate this dp?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Waiting for the editorial....

→ Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I always check oeis for problem with one input :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Is there something special about test 5 in problem G?

EDIT: This is a tricky test. 

7 7
0 1 1
1 2 0
2 3 0
3 4 0
4 6 1
1 5 2
5 4 0
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    nothing special. just big random test

    → Reply
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +16 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +123 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          Why do you need to allocate that much memory? My solution requires time and O(n2) memory.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +16 Vote: I do not like it

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

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

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Police won't catch him in this case.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Is it the answer to my question?

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like 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.

                → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

what does "a bit" mean??

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Why does this work? 12873839

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply