Блог пользователя arsijo

Автор arsijo, 8 лет назад, По-русски

Всем привет!

13 сентября в 19:35 MSK состоится рейтинговый Codeforces Round #371 для участников обоих дивизионов. Это наш первый раунд и надеемся, что не последний.

Задачи готовили я (Антон Цыпко) и Sonechko (София Мельник). Большое спасибо GlebsHP (Глебу Евстропову) и Sereja (Сергею Нагину) за помощь в подготовке задач, MikeMirzayanov (Михаилу Мирзаянову) за системы Codeforces и Polygon, а так же iSlava (Вячеславу Очеретному), AllCatsAreBeautiful (Марку Михно), BigBag (Матвею Асландукову), winger (Владиславу Исенбаеву) и AlexFetisov (Александру Фетисову) за прорешивание задач.

Участникам будет предложено по пять задач и два часа на их решение. Мы рекомендуем участникам ознакомиться с руководством по интерактивным задачам. Разбалловка будет объявлена позднее.

Надеемся каждый найдет себе задачу по вкусу. Всем успешного раунда и повышения в рейтинге!

Разбалловка:

Div 2: 500 — 1000 — 1000 — 2000 — 3000

Div 1: 500 — 1000 — 2000 — 2000 — 2000

Upd: Поздравляем победителей:

Div 1:

  1. geniucos
  2. Herzu
  3. Endagorion
  4. Um_nik
  5. Radewoosh

Div 2:

  1. fanache99
  2. amethyst0
  3. Gromah
  4. serlis
  5. Jason_zjj3

Разбор.

UPD: Приносим прощения, что задача Div 1 C очень похожа на эту, но раунд будет рейтинговым.

  • Проголосовать: нравится
  • +271
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Hope the Codeforces remain stable unlike last Div2 round.....

»
8 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

tomorrow, eid day in bangladesh. we can celebrate eid with contest. hope it will be a great contest.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In previous round contain Interative problem I lose 100 point on problem C because fflush :)) I hope nobody wrong like this :))

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    How you passed the example then?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      my code have many if and one of them I forget fflush :((

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится

        My strategie usually is make functions to interact, one for reading and one for writing. You can do this almost in all cases and you won't have to be worried about flushing or parsing at every moment.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

in the name of allah, most merciful

which rounds contain interactive problems?

i hope somebody says numbers for practice.

have good contest.

»
8 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Oh no!!! Interactive problems again :(

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

hope for a stable Codeforces.

»
8 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

Eid mubarak for all muslims!

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Наконец-то интерактив, уже соскучился.

»
8 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I so want this round to be rated and hassle-free.

»
8 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

I feel very interest in interactive problems :) but can't solve well :( All though, good luck to me for this Contest! and today is also Eid Day for in Bangladesh! Hope good luck in this Eid Day Conteset :D I think Everything will be okay During the contest Time.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Можно пояснить для новичка: что такое дивизион? Самостоятельно не нашёл..

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    все кто выше синего цвета — див.1, остальные див. 2

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    2-ой дивизион -- рейтинг от 0 до 1899. Там 2 задача не очень сложные, а 3 сквозные с первым 1-вий дивизион -- рейтинг 1900+. Опять три последних задачи из div 2, и 2 сложные.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +74 Проголосовать: не нравится

      Помнится, опытным путём было доказано, что не от 0...

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -12 Проголосовать: не нравится

        Пишу отталкиваясь от того, что "говорит" codeforces, а именно: "Рейтинг должен быть от 0 до 1,899 для возможности регистрации на это соревнование". А по поводу "опытным путём было доказано, что не от 0", не могли бы вы дать ссылку)

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

How to hack the interactive problem?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Eid Mobarok Everyone <3 from Bangladesh <3

Best wishes for Codeforces <3

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Wish the Internet&server will be better..........

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Wow! Interactive problems this time. Expecting Stable CF round this time :)

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

why interactive man?

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

I have problem with registration to contest... I register and then I click to list of participants and I still see "Register Now" although I was registered...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It will be a rated round ?

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

 **** Get ready fellas! :P :P

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

it's 10 left minute to start the round and the score distribution is not announced yet !

UPD : now it's 1 min and nothing announced :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Relatively few people registered(in both divs). I hope that means a working website!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is everything working fine for everyone ?? For me on main codeforces page top menu is invisibile like in mobile view

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Eid mubarak to all :) hoping a great contest

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I'm not able to submit You should be registered for the contest to be able to submit but on the contests page it says registration completed.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Cannot submit.It says should be registered for the contest even though I registered.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I cant see other codes when block my problem :(

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

cant open room, random pages are loading ! clicking on a submission, it says soln already hacked or resubmitted ! but thats not the case

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Not able to hack solutions

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't submit any solution.

when I click submit button, I just see  nonsense err.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can I test interactive code on ideone? Any help will be deeply soulfully appreciated :D

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +93 Проголосовать: не нравится

It is just unfair to include problems like this div2E/div1C

as you can see a lot of people had it passed in around 20 minutes

there is one who solved it in 4 minutes ( after he solved A )

13C - Sequence

it's here :)

too much creativity

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Man! Now I get the reference. I thought it was a joke only I didn't get!!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +56 Проголосовать: не нравится

    Pasting link to the same problem, with visible solutions, during the contest... genius.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The problem is not the same.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        You are right of course, but the only difference is non-decreasing vs. increasing, what is handled by line t[i] -= i;. So, almost the same problem.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      It is genius!!! Way to protest like a boss :p

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      it was actually posted here blog about 1 hour before the end of the contest so posting a comment before 10 minutes isn't that genius

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      the real genius is the problem setter i mean i wouldn't have pasted anything if it weren't some old codeforces problem

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +124 Проголосовать: не нравится

        Do you remember all problems that ever been on Codeforces? Neither do I, GlebsHP, authors, MikeMirzayanov or anybody else. Posting such link during the contest makes things only worse; you (and all who did the same thing except you) could've posted such a link after the contest ends so that results of people wouldn't be affected.

        After all, there is no difference between knowing a solution of problem because you studied many algorithms (even unpopular ones) and knowing the same problem beforehand. It's your advantage, use it. Posting it in public is equivalent to spoiling the solution during the contest.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +63 Проголосовать: не нравится

          I just checked the thread by Pepe.Chess. It appears this comes on the first page by a simple google search. Sure a co-ordinator shouldn't be expected to do this, but it's mind blowing how the author didn't even spend few minutes checking if it's original or not by a simple google search.

          After all checking if your ( as an author ) 5-8 tasks are original ( as in not easily googleable) or not has nothing to do with you knowing the whole problem set on CF.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится -8 Проголосовать: не нравится

            I agree with you. Still, this is not an excuse for ruining contest for everybody else. This is not how the contest ethics works.

            But let me ask you a question. You may often see a problem in div2 and even in div1 that may easily be reduced to a shortest path problem in directed weighted graph. You type in Google "shortest path algorithm" and it suggests you "Dijkstra" even until you press Enter. Does that frustrate you in the same manner?

            In this case it is not even the same problem; one should come up with replacing a[i] with a[i] - i trick to transform it to that problem.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

              ok dude , you don't remember any and you don't need to actually remember all problems on codeforces

              but that doesn't mean checking if a problem is googlable or not :)

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится +56 Проголосовать: не нравится

                You are intentionally ignoring my point :) I'm not trying to find excuses for authors and coordinator, it is indeed a fail from their side.

                What I'm talking about is that you and the guy who posted something at the middle of the contest did the wrong thing. In the conditions when this fail already happened, posting the link to the problem is a wrong move. Do not do that. Post it after the contest ends.

                And yes, I know you were the second one to do that. This is not an excuse for you. Hope it is now clear what I mean.

                At this moment I stop this conversation.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Is this a[i] — i trick a trivial transformation? Enough to deem the problem non-original? (Genuine question — I didn't know the trick — I was wondering how common it is).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Not exactly trivial, but it was obvious to me and should be to most people who are at the level of usually solving div1C. Basically, subtracting 1 from every difference.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

          ok i am the guilty guy

          some guy just copies an old codeforces problem and include it as a div1C problem

          and some pedophile posts the solution one hour before the end of the contest

          and i am the one who is guilty

          i just commented here 5 minutes before the end

          go paste the statement into google and you will find a post on quora

          thanks people

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          We can agree that it's impossible to know all problems. But Google does. IMHO every setter before the very beginning of preparing the problem should try to find it on the internet. Otherwise, such situations will surely happen

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            But Google knows so many things it is hard to specify what are you looking for. Googling tasks is not easy. I copied my code from my high school's online judge, but was unable to find a thread on CF about that task which I know I have read.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    Change a[i] by a[i] — i, it becomes 13C. Is it correct?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I accidentally down-voted your comment while trying to up-vote it and Codeforces won't let me change it. Sorry.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Also A isn't very original, I am sure I have seen easy variations of it twice in recent contests.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Waiting for rated contest for infinity time and now it will be unrated with almost 100% probability. That's fun.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      It is still funnier than losing a lot of ratings because of not Googling the solution :P

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No, unrated is fine for me, because I didn't google the solution. And got too much trouble with Div1B.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится

          I think it didn't affect so much because people are not accustomed to reading blogs during contests. Div 1 people would not google and for Div2 the number os submissions show people being unaware of it. Around 300 submissions should have raised suspision.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +23 Проголосовать: не нравится

            Div1 people would not google? You'd be surprised...

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

              I've been told that nowadays most valuable skill is not to know a lot of information, but rather to be able to get information you are missing in a short time :) (Ideally — without bothering other people with your questions while doing it)

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится -7 Проголосовать: не нравится

          Me too. But from now on google and I will be best friends.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Wait, I didn't get it, your reason for unrated event is "there was a problem in a contest which is rather well-known", right? :) Not technical issues, not problems being badly prepared, but the fact that some problem doesn't contain brand-new idea?

      Maybe it is time for me to hope for round being unrated as I didn't manage to solve D which is also well-known and classic :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I believe it was sarcasm, right? :)

        Anyway, why is D well-known and classic? I didn't come up with a solution with reasonable running time asymptotics and submitted parallel binary searches with 2D Fenwick tree and heavy optimizations that works in O(nmlog3n). Though, on pretests and my own tests here on CF it runs for <4s.

        UPD: ok, I got it. The solution is to do a binary search and then make a 2d-minimum query in the small rectangle. What exactly here is well-known and classic?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          If you mean first part of my answer — I missed the fact that there were some comments about this problem and discussions right during a contest, yet I don't think it is enough for making it unrated.

          For a second part — my solution is far from being cool, it is similar to your idea, and there is high probability that it will fail:). Even if it will pass — I haven't actually solve problem in terms of figuring out proper solution, and that makes me sad anyway. For me "find maximum in a static submatrix (using sparse table)" sounds like a very classic problem.

          UPD. Oh, it seems that for other people transition to binary search + max.query was not so obvious, while I got stuck on a part about finding max in O(1).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's quite funny that 713C is similar to 13C. Maybe it was intended joke? lol

»
8 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

How to solve Div.1 C???

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

    Let b[i] = a[i]-i. Then it can be thought that you're to make non-decreasing sequence instead of increasing sequence. From that, a dynamic programming idea comes out. D[i][j] : minimum cost of making b[1] ~ b[i] sorted, such that b[i] = j: D[i][j] = min(D[i-1][k]) + abs(b[i]-j) for k <= j. j has to be one of the initial values of b, so the time complexity is O(n^2).

    http://mirror.codeforces.com/contest/713/submission/20589839

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      How does b[i]=a[i]-i convert strictly increasing problem to non decreasing?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        "a[i] is increasing" and "b[i] = a[i]-i is non-decreasing" are equivalent.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Okay it founds an answer but how to be sure it's the smallest one? We convert our array, how can it be the right answer?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Suppose not. Suppose there is a set of moves that's smaller than our answer. use the same set of moves on b[i] = a[i] — i. It will be a non decreasing array. Which will cause a contradiction.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Div1C: go left to right, increase values greedily up and count how much you add. Also maintain a sorted vector of best costs for moving down the current stairs by one. E.g. you pay 1, 1, 1, then 2, then 3, etc. Costs are groupped so vector consists of pairs (cost, number): (1,3),(2,1),(3,1),...

    When next element is larger than current height, you increase all costs by 1 and push (1, h-1-x) to the vector's back.

    When next element is smaller or equal, you increase it by d to make it higher. Then you reduce the latests d costs by 1 (you may need to split some group in vector into two groups). And you increase all other costs by 1.

    Then you take all non-positive costs from vector's back and "use" them: decrease current answer and height.

    So this vector grows linearly, leading to O(N2) solution. This can also be seen as DP.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Missed the registration...a pity.

    I figured out a solution via MCMF.

    First we can consider another array: a2 - a1, a3 - a2, a4 - a3, ..., an - an - 1.

    Let's consider this new array as bi, and find the impact of increasing ai to bi.

    For increasing a1, we get b1 decrease by 1.

    For increasing ai (1 < i <  = n - 1), we get bi - 1 increase by 1, and bi decrease by 1.

    For increasing an,we get bn - 1 increase by 1.

    Notice that we can add arbitrary number to ai.Let's view bi as n-1 piles of stones(allowing minus stone number), then we can perform 2 types of operations.

    1.Generate 1 stone at pile 1 or pile n-1.Cost is 1.

    2.Exchange 1 stone between adjacent piles.Cost is 1.

    Out goal is to make every pile at least 1 stone.

    Let's solve this model by MCMF.

    1. Categorise bi as three types A(for piles with number more than 1), B(for piles with number less than 1), C(for piles with number exactly 1).

    2. Connect SOURCE to b1 and bn - 1 edges with infinity flow and cost 1.(Meaning generating stones.)

    3. Connect SOURCE to type A vertex edges with (bi - 1) flow and cost 1.(Meaning redundant stones.)

    4. Connect type B vertex to DRAIN edges with ( - bi + 1) flow and cost 1.(Meaning required stones.)

    5. Connect bidirectionally between adjacent vertexes edges with infinity flow and cost 1.(Meaning exchange.)

    6. Perform MCMF and you are done.

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Problem B. Filya and Homework ***** In this problem, Filya is allowed to pick any integer X, even x = 0. For each element of the array he can decide whether to add x to it, subtract x, or do nothing. He can choose to not add x at all, or not subtract x at all, or just do nothing at all. For each particular element he can add x to it (or subtract) no more than once.

This costed me 3 WA -_-

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

fml.
 .

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That was a lot of hacks!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a complicated solution for div2D, too easy to make bugs...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could problem C div 2 solved using simple bst? I represent the structure using 1D array.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C isn't just old — it's a classical min cost flow problem. :(

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Very weak pretests for A and B, especially B. My solution is completely wrong, but when I noticed it, it was already locked...

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

C can be solved in O(Nlog N) by using the fact that abs(x-k) is convex function, I think. (I have made almost the same problem and used in Japanese domestic contest.)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    I also gave the problem with very similar trick about convexity to the Yandex Algorithm 2016 Finals (problem D).

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      I solved that D problem, but have no idea how that relates to this problem. My codes to those 2 questions have literally nothing in common (even headers are not common xD). Could you elaborate a bit?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

        Replace a[i] with a[i] - i to transform problem the non-decreasing variant (this is not a necessary step, everything else may be done even in original statement, but it makes things easier to understand).

        Consider two DPs: E[i][x] = minimum penalty for making i-th number be equal to x and S[i][x] = minimum penalty for making i-th number be smaller or equal to x. This obviously does not fit in TL and ML, but we will deal with it.

        We have: E[i][x] = abs(a[i] - x) + S[i - 1][x] and . Actually this means that E[i] and S[i] being treated as functions of real variable x are piecewise-linear, convex and S is obviously non-increasing. This allows us to store only the vertices of the plot of E[x] in map and simply recalculate them in O(n) (with extra logn factor from the map).

        This may be simply improved to O(n2) by storing the points not in the map, but in the array, and furthermore, by storing them in some data structure that allows adding a linear function and binary searches (like segment tree or Cartesian tree), the running time may be improved to . The code is literally 40 lines.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Could you elaborate please? Ternary search for the first value would work?

    UPD: I see it's not enough to determing the full sequence.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

Hard Work Today XD
thanks for the nice contest =D

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For Div2 A, most of the hacks included the cases when there was no intersection between the time intervals like [1, 2] and [3, 4].

Some other were due to the silly mistakes by the users.

Nice contest though.

»
8 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

Interactive problems look fun until you get WA and then you need to write more code to have a chance to find a bug(or spend even more time working as interactor while debugging).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Totally agree!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    I think it's better to start with writing your own ask_query function, what should lead to something like this (version after changing it to the submitable version):

    int ask(int x1, int y1, int x2, int y2) {
    	printf("? %d %d %d %d\n", x1, y1, x2, y2);
    	fflush(stdout);
    	int ret;
    	scanf("%d", &ret);
    	return ret;
    	
    	/* int ret = 0;
    	if(x1 <= 17 && 57 <= x2 && y1 <= 80 && 80 <= y2) ++ret;
    	if(x1 <= 25 && 88 <= x2 && y1 <= 51 && 61 <= y2) ++ret;;
    	return ret; */
    }
    
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can my solution for 2B be hacked?

https://ideone.com/L9PBla

»
8 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Damn, C was already discussed on CF few times :/. And in xdd. Copy pasted 4 years old code (like probably many people).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    yeah there is genius who got it in 4 minutes

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Can you provide a link with the thread where it was discussed in O(nlogn)?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I tried to find it right now, but wasn't able to do that. I remember that it was on USACO and someone mentioned super short solution by ecnerwala, but it wasn't sufficient for me to find it :(.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    I knew the problem before as well, but not the NlogN solution (just the easy N^2). Can you please explain me the more efficient one or provide a link to some solution? I've been thinking for a while at it and was unable to solve it that fast.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Eid Mubarak Everyone :)

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

how to solve div 2 E

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share with me his solution for Div2/C using a trie data structure? My solution using trie exceeded the time-limit I am not sure why.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

a nice contest

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when judge ? i am newbee

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

when judge? i am newbee

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div 2 D, binary search for each corner of each rectangle? I get stuck on finding columns of second rectangle, it is just too many cases? Anything simpler?

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What is the intended time complexity in D? I wrote 10^9 solution and it passed pretest in <2s.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня на домашнем интернете посреди контеста вылез Bad Gateway и до сих пор висит, остальные сайты нормально загружает. Сейчас сижу через VPN, к которому я подключен всё через тот же домашний интернет, значит дело не в нём. У кого-нибудь такое наблюдалось?

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

I failed to hack someone 3 times on problem B cause he put that  :( :(

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In problem D, the answer is 0 when there is no valid square i.e the region is empty, which I think should be noted in the statement. And I got WA on pretest 4 due to this issue.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

When will the ratings be updated and system testing be done?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the solution to div.2 B?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We can make all values equal to either maximum value, minimum value or average of maximum and minimum(if (max+min) is divisible by 2).

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Could you explain me why still am i unrated after finishing Round 370 and 371? I wnat to get my color...

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

It seems Round 371 is gone from the contest list.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

div1 E++: What if the directions can change during the game? (And I mean something better than .)

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    EDIT: changed "j-i" to "j-i+2", sorry for mistake.

    I misunderstood a problem first and tried to solve such a version. My guess was that we should change the input to distances between consecutive owls and then print:

    where $S[a,b] = d[a] + d[a+1] + \ldots + d[b]$.

    The reason is that numbers in an interval of length d can be decreased by only d + 1 owls (other owls will never help because it's stupid to overtake/outrun an other owl). So, only j - i + 2 owls can fight against an interval of length j - i + 1. And there is also a case when we consider a whole interval, what explains in the formula.

    I don't know if it's enough to print the above formula. And it's quite known how to compute it fast — one must binary search the answer first (and then it isn't hard).

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I looked at E at some point in the contest, immediately recognised binsearch (it's quite common in this type of problems with parallel actions) and also misunderstood it as that at first. It seems harder to me than the contest problem — the optimal strategy within the binsearch isn't very clear.

      Consider the case where the owls' positions are -2,0,2 with M=11. The optimal answer is 3 when the owl in the middle takes the two chairs next to it. Does that work with your formula? (Your "distances" are actually the number of chairs strictly between two owls, right? And j - i should be |j - i| + 1, right?)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You test produces distances 1, 1, 6. My formula considers an interval with the number 6 only with fraction , what is correct.

        (j - i) means (j - i)%n, because we are on the circle.

        In your test I take maximum of 1 / 2, 1 / 2, 6 / 2, (1 + 1) / 3, (1 + 6) / 3, (6 + 1) / 3, (1 + 1 + 6) / 3. Reminder: taking the whole circle is a special case with dividing by len instead of len + 1.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I was confused by the denominator j - i primarily because of division by zero. So it's

          Unable to parse markup [type=CF_TEX]

          according to what you write, or [number of owls in the summed interval including the two border ones].

          If the distances are 2,4,6, then your formula gives 4, right?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Oh, there should be S[i, j] / (j - i + 2) everywhere, I'm sorry for that.

            I managed to think j - i + 1 + 1 = j - i, which isn't really correct.

            Yes, my formula gives 4 for 2, 4, 6. Is it wrong?

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Yeah, it is. You'd need everyone to take a chair in every move since 2 + 4 + 6 = 4·3, so nobody can turn around (the answer to the contest problem would need to be 4). That won't work for the pair with distance 2 and the 2 chairs between them.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Oh, we have two different wrong ways to understand the statement. I thought that a chair is removed and each time we choose to move to one of two neighbouring chairs. While your version has empty places where chairs used to be.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lol, so this wasn't the actual version -_-? Something is wrong if all of us misread it (either with us or with statement).

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The statement is correct, it's probably that people good enough to solve E read statements too quickly and don't notice that step 2 is out of the loop.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Usually numbered list in this kind of problem describes one turn, and it fitted here very well.

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Div2 is still going to be rated right?

there are only 28 accepted solutions on E.

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Problem C appeared on round 13 (http://mirror.codeforces.com/contest/13/problem/C). The only change is the resulting sequence must be 'strictly' increasing, but the idea is the same.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't believe this I didn't get a notification that my code on B was hacked I found that out when I was checking my friends standings.

:(

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Fun fact: An O(n3 + n * q) solution passed all test cases for D div 1. Bet that wasn't intended.

http://mirror.codeforces.com/contest/713/submission/20595881

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My 10^9 also passed. I think it is almost impossible to distinguish between O(NMlog Nlog M) and such a fast 10^9.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Setting TL to 2s would solve the problem. I can't see any reason for it to be 5s inviting stupid solutions to pass

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Decreasing TL will cause some O(log2) solutions to fail. It isn't true that all O(n3) solutions are faster than O(log2) ones.

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I prefer a contest where there is a gradual increase in the difficulty level of the problems....In this way you get a fair judgement. Just my opinion :)

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can we get the editorials ? Also will the contest be unrated ? At least for Div 2, it should be rated I think. My last 4-5 contests on CF have been unrated.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi everyone!

I have a concern regarding problems given, so need your advice...

In a problem A. Meeting of Old Friends it states: The only line of the input contains integers l1, r1, l2, r2 and k (1 ≤ l1, r1, l2, r2, k ≤ 10^18, l1 ≤ r1, l2 ≤ r2), providing the segments of time for Sonya and Filya and the moment of time when Sonya prinks. Please note on the statement l1 ≤ r1, l2 ≤ r2.

However, in the Test #3, in the input given l1 is actually bigger than l2, which should not happen by problem statement.

Test #3: 6 6 5 8 9

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is said that L1<=R1 and L2<=R2 ! In the test case that you gave

    L1=6, R1=6, L2=5, R2=8, k=9

    Answer should be 1

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

So, is it rated or not ?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://mirror.codeforces.com/contest/714/submission/20582567 Submission in python (during contest) http://mirror.codeforces.com/contest/714/submission/20597376 Submission in pypy (after contest) Even though both are same codes i got TLE for python and AC for pypy. Can anyone explain why this happens ?? If pypy is very good why is codeforces not removing python ??

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone understand how I got this compilation error:

Can't compile file:
C.java:39: error: reference to println is ambiguous
				out.println(cnt.containsKey(val) ? cnt.get(val) : 0);
				   ^
  both method println(double) in PrintWriter and method println(Object) in PrintWriter match
1 error
File should contain public class named as the file.

For this submission: http://mirror.codeforces.com/contest/714/submission/20581077

I get that println believes it can't be sure what the ternary operator is returning (either an Object of class Integer or int), but I would have thought the ternary operation would resolve first with the associated type. Is this simply not the case?

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

For Div2C, time limit was 1 second for my submission in python. Is time limit same for all the languages?? If that is the case, isn't it unfair?!!

I thought the time limit given in the problem statement page is for languages like C, C++ etc., and for slower language like Python, Java etc. the time limits are longer. For example, for Python it's around 5x, for Java it's around 2x etc. Could someone please clear my doubt?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    I have to say, ur knowledge of languages and their TL is very very bad. First of all, before you participate in a contest, u are expected to know the judge environment and the rules. Do you want somebody to come to ur place and explain to you in detail? And secondly, python is much much much slower than Java, if its 2x for Java, its 10x for Python. Did u get it?

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

three 0 rating changes until now... (actually, thanks god I didn't get negative rating change!)

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

@arsijo and what about the spoiling of the problem......

It's totally unfair to leave it rated.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    Why was it unfair? Everybody could google the problem.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -22 Проголосовать: не нравится

      Errichto this is sarcasm or what :D

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Said someone who thinks that using an already known problem means that "guy just copies an old codeforces problem and include it as a div1C problem". It was hard to say if you are joking or not.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          ok sorry

          i know you don't mean it ... and i was pissed off there so i wrote "copies" in fact it is not really far from copying

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      So instead of being concentrated on thinking of problems , we keep searching on google ... I don't think this is the goal of making contests and participating in ....

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Actually , It was fair. But it wasn't right and correct. so since it wasn't right, this contest should be unrated

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please, does anybody have any idea why this code doesn't work? I spent over an hour trying to debug it and even now when I see the test it fails on, I can't figure out what it is. When I enter the second test locally, it works. I flush the output everytime and the code to simulate queries seems fine as well. I also had an assert to check if it doesn't use too many queries and it does not.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    On your output line 22: ? 1 2 0 9 -> 0

    Notice x2 < x1 but the task says (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot, still not sure where it happens, but a simple if fixes it. Didn't even know that you would get WA for that, but I suppose it makes sense.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D, you pass first 3 pretests if you swap x and y values in input... I think that might be really misleading during contest especially when the order of x and y are nonstandard. Fortunately I had also another bug in my solution xD

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I passed the first nine pretests of E reading n and m in the wrong order. I guess pretests were a bit weak this time around.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).

My code : 20594137

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).

My code : 20594137

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That was a great round :D Became pupil for the first time. ( another one was decreasing pupil :P ) Thanks round 371 :D

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

I mean why can't problem setters just google the question before adding them to problem-sets , because no one runs a script to match keywords with problem , people just google it. Its third time i have encountered a similar situation .

  • 1 ) That pythagorean triplet Question, people pasted it from quora link .

  • 2 ) That trie question, copied code from other sites

  • 3 ) Today's problem C

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

I will deliver one nonpleasant spank for every problemsetter that denotes rows indices as x and columns indices as y :(.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am unable to understand problem B div 2. why is the case that if there are only 2 distinct numbers then answer is always yes? also why the condition as mentioned in the tutorial for the case 3?You can choose a number only once so say for example 1 10000000 so i choose 1 then i can only substract or add to 10000000 ,no way we can make these 2 numbers same by choosing any of the number and add or substract from other number.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You don't have to always add or subtract numbers. In the case you mentioned, you can add 9999999 to the first number and do nothing to the second. Then, both numbers will be equal to 10000000.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem Statement Says that l1 ≤ r1, l2 ≤ r2 But apparently test case 3 is 6 6 5 8 9 Isn't the problem statement wrong. I got 4 WA for this constraint during contest time. :(

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Спасибо за еще один день без ML!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help me!

here is my code for problem C http://codepad.org/zrZTXOBM

everything is ok in my compiler. but CF shows it's giving output '0' at every testcases!