arsijo's blog

Codeforces Round #371
By arsijo, 8 years ago, translation, In English

Hi everybody!

Codeforces Round #371 takes place on 13 September at 19:35 MSK for the both divisions. This is our first round and we hope it won't the last one.

This round is prepared by me (Anton Tsypko) and Sonechko (Sofia Melnyk). We want to say thanks to GlebsHP (Gleb Evstropov) and Sereja (Sergey Nagin) for help with preparation of this round, MikeMirzayanov (Mike Mirzayanov) for Codeforces and Polygon systems, iSlava (Viacheslav Ocheretnyi), AllCatsAreBeautiful (Mark Mikhno), BigBag (Matvey Aslandukov), winger (Vladislav Isenbaev) and AlexFetisov (Alex Fetisov) for testing problems.

It's recommended for both divisions to read the Interactive Problems Guide before the round. Scoring distribution will be published right before the start of the contest.

Good luck!

Scoring:

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

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

Upd: Congratulations to the winners:

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

Editorial.

UPD: We are sorry that Div 1 C is very similar to this, but the contest will be rated.

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

Comments Comments (256)
| Write comment?
»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

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

    Hope so.. last round was pain :(

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

    Good day, good Codeforces, and tonight I will be a purple Coder.That is really great.Thank you everyone!Thank the is world!

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

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

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

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

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

    How you passed the example then?

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

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

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

        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.

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

in the name of allah, most merciful

which rounds contain interactive problems?

i hope somebody says numbers for practice.

have good contest.

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

Oh no!!! Interactive problems again :(

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

hope for a stable Codeforces.

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

Eid mubarak for all muslims!

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

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

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

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.

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

    Hope you solve the interactive problem. and also Eid mubarak. :)

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

    good luck to everyone :)

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

How to hack the interactive problem?

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

    If you're on Linux, write sudo rm -rf /. Make sure you have root access or it won't work!

    If you're on Windows, make a file named something.bat, type in it 

    @echo off
del C:\Windows\System32

    save and run it. It really works!

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

      No one is such a arse I think!

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

      It isn't funny.

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

      3ib da enta red

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

      I'm shocked! what the number of downwotes!

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

        Isn't saliii you ?!?! I'm shocked!

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

          yes, exact! he is me! but how you got it!? actually I can't have virtual on the contests that I have participated before and I have such a fake account!

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

            Actually, we have common friend (;

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

    You must submit hacking program which will interact with target

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

    It depends on particular problem. Instruction for writting hacking program always present in an interactive problem statement.

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

    It will be described in the statement.

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

Eid Mobarok Everyone <3 from Bangladesh <3

Best wishes for Codeforces <3

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

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

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

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

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

why interactive man?

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

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

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

It will be a rated round ?

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

    yes

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

    I'm shocked this comment is so far down, considering how it usually goes...

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

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

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

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

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

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

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

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

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

Eid mubarak to all :) hoping a great contest

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

    লাইক দিয়ে পাশে আছি, ফ্রান্স।

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

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.

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

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

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

I cant see other codes when block my problem :(

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

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

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

Not able to hack solutions

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

Can't submit any solution.

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

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

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

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

    Write some code which will answer the questions automatically instead of answering them in stdin

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

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

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

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

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

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

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

      The problem is not the same.

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

        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.

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

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

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

      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

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

        Omg, make it unrated pls

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

        And your comment here fixed the whole situation.

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

          At least don't make it unrated just remove the question from consideration.

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

            Great idea !!

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

              Yeah if you just solved the C or smth you better be GO TO HELL IT'S THE PERFECT IDEA EVERRRRRRRRR!!!!!!

              Seriously, it looks like "great idea" to you?

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

                Oh I forgot that it would be unfair for those who solved C only.... or maybe I didn't forget and it was just sarcastic comment.

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

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

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

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

        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.

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

          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.

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

            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.

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

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

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

                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.

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

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

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

                  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.

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

          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

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

          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

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

            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.

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

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

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

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

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

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

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

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

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

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

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

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

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

          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.

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

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

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

              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)

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

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

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

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

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

        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?

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

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

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

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

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

How to solve Div.1 C???

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

    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://codeforces.net/contest/713/submission/20589839

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

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

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

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

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

          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?

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

            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.

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

    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.

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

    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.

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

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

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

    Yes, same here. I got 1 wa and waited for an announcement to clarify this. :/

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

fml.
.

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

That was a lot of hacks!

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

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

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

    Yeah i hope it had strong pretests...

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

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

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

    It's just simple trie problem.

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

      Trie sounds like an overkill. Can't we simply use maps here?

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

        Lol, I just copied my implementation of trie and changed it a little bit.

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

        I think no because of anti-hash test!! not sure though!!

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

        I kinda worried about maps speed so I'm using array instead. So the root of tree is 1. If current node is x and the digit is odd, then we visit node number x*2 + 1, else we visit node number x*2. I'm taking advantage that the maximum number of digits is 18. So 2^18 < 600000.

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

      Can't we just use an array of size 2^18 ?

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

    Did you trie your best?

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

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

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

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

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

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

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

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

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

      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?

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

        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.

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

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

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

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

Hard Work Today XD
thanks for the nice contest =D

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

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.

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

    Too bad it is going to be unrated .

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

      If it is unrated....Good for me...I got a lot of penalty in B. Misread it completely -_-....BTW it is not helpful if there are too many unrated contests

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

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

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

    Totally agree!

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

    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; */
}
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can my solution for 2B be hacked?

https://ideone.com/L9PBla

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

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

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

    yeah there is genius who got it in 4 minutes

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

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

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

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

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

    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.

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

Eid Mubarak Everyone :)

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

how to solve div 2 E

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

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.

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

a nice contest

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

when judge? i am newbee

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

    You'd better go and do something else instead of waiting, because it can be (very) long. :P

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

      it is 2:52 in china.... i want to sleep but i also want to know rating!!!!!!!!!!!!

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

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?

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

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

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

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

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

    LOL, should notice it :P

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

    It is his loss, not yours.

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

    People regularly put #define long long int int to disturb hackers.

    Update : see the comments below. :P

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

    Don't you guys run their codes on your machine at least??????????

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

      That takes too long to copy down. If you mean do that automatically, it's against the rules (and also kinda makes hacking silly as you could script the whole thing).

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

      no of cours it takes so much time

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

    Problem B's constraints are within 10^9, why would long long be necessary?

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

    Also notice when in someone's code there is an "if()" which it is wrong he might did this : if();

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

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.

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

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

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

What is the solution to div.2 B?

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

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

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

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

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

    370 was unrated due to server issues. 371's ratings are yet to be updated.

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

    wait for it ..... system testing is still going on!

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

It seems Round 371 is gone from the contest list.

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

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

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

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

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

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

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

        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.

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

          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?

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

            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?

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

              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.

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

                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.

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

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

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

      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.

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

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

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

Div2 is still going to be rated right?

there are only 28 accepted solutions on E.

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

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

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

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.

:(

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

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

http://codeforces.net/contest/713/submission/20595881

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

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

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

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

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

        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.

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

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

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

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.

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

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

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

    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

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

So, is it rated or not ?

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

    I hope no.

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

      You didn't even participated!!??

      UDP.You participated but you're not even showed in my friends standings,is it a bug?

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

        perhaps he(she) was participated with his(her) other account.

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

    Yes it's rated, blog updated!

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

http://codeforces.net/contest/714/submission/20582567 Submission in python (during contest) http://codeforces.net/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 ??

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

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://codeforces.net/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?

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

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?

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

    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?

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

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

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

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

It's totally unfair to leave it rated.

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

    Why was it unfair? Everybody could google the problem.

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

      Errichto this is sarcasm or what :D

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

        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.

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

          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

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

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

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

        Nobody said it's good that such a problem was used today.

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

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

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

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.

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

    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)

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

      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.

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

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

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

    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.

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

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

My code : 20594137

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

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

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

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

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

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

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

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.

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

    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.

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

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

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

    6 <= 6 and 5 <= 8 so those constraints are valid.

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

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!

→ Reply