gepardo's blog

Codeforces Round #404. Announcement.
By gepardo, history, 8 years ago, translation, In English

Hello, Codeforces!

Tomorrow, in March 15, 2017 at 18:05 MSK a regular rated Codeforces round for participants from the second division will take place. As usual, participants from the first division can take part out of competition. It's my second contest and I hope you'll like it more than my previous one.

As usual, there will be five problems on the contest and two hours to solve them. I advice you to read all the problems' statements attentively. Also check all your solutions for correctness even if they passed all the pretests. Verdict Pretests passed doesn't mean that the solution is completely correct! I wish you to enjoy the contest and learn something new solving the problems.

Like in the last time, the problems will be about Anton and his friends.

Great thanks to Alexey Vistyazh (netman) for help in preparing the contest, Vladislav Vishnevsky (Vladik) for testing the round, Dmitry Klebanov (dmitriyklebanov) for reading the statements carefully, and of course, Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon.

Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500.

UPD. The contest is over, system testing has already started, the editorial will appear soon.

UPD2. Editorial has arrived.

UPD3. Congratulations to the winners of the contest!

Div. 1

  1. uwi
  2. rajat1603
  3. SaSa
  4. mr.banana
  5. Kaban-5

Div. 2

  1. CommonAnts
  2. Gauss
  3. binsjl
  4. hotwater
  5. mister_dudec

Thanks everyone for participating :)

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

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

Auto comment: topic has been translated by gepardo (original revision, translated revision, compare)

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

Why not in main page?

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

finally a regular round after 10 days .

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

Looks like more hacking is gonna happen in the contest.
Also love the statement
I wish you to enjoy the contest and learn something new solving the problems.

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

Thanks for the contest.

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

ERROR 404 :p

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

Expecting a lot of Hacks !!

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

Codeforces should have just skipped round 404 and have gone to round 405. That way, whenever someone searched for round 404, they would have got the error message "Round 404 not found" xD

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

I advice you to read all the problems' statements attentively

Delicate way of saying that pretests are guaranteed to be shit.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it 
    Verdict Pretests passed doesn't mean that the solution is completely correct!

    True

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

      Verdict "Accepted" also doesn't mean that the solution is completely correct, but we tend to forget it.

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

    I think it means that problem statement is complicated, but is it true?

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

    I saw sources that passed C with brute-force,but a simpla 10^18 1 test shut them down.

    Also,there were some with sqrt(n-m),but n<m crashed them.

    Pretests were really bad

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

Div. 1 Round not found.

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

Btw anyone knows the reason behind the low frequency of cf rounds thesedays.

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

I hope short statements!!!

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

    Why? Longer statements are usually more understandable and more interesting to read.

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

      mmmm..! Actually I mean short and understandable!!! You can see Csacademy's problems!!! Some of part of stories is really useless!!! We can make a short interesting problem.

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

        Yes, such statements are good. I hope you'll find my statements short enough, understandable and interesting :)

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

          Don't worry! I guess your contest is strong and interesting enough to don't think about the statements :)

          In Allah's safeguard

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

Also check all your solutions for correctness even if they passed all the pretests. Verdict Pretests passed doesn't mean that the solution is completely correct!

That's look like problem's are a little bit tricky and suitable for hack...:)

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

This is the first contest that I skip because I have 1900 rating!

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

    You can participate unofficially too. Main thing is learning, not rating, and I'm sure you can learn new things from any contest (no matters Div.1 or Div.2).

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

It is too late for me to join it. :(

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

Contest 404 not found ! :P

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

:|

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

Verdict Pretests passed doesn't mean that the solution is completely correct!

be carefull everyone , today's questions will have many hacks :)

wishing everyone positive rating change , good luck ..

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

Hoping of getting a color change to dark blue:)

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

This post scares me for the contest.

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

Anybody noticed the "tag not found" tag? :D :V

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

Let's see if there will be server problems this round...

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

The comment is hidden because of too negative feedback, click here to view it

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

The comment is hidden because of too negative feedback, click here to view it

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

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

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

Last time I did a comment like this I lost a 100 point in rating but...

This is the last CF round before the selection test here...

I really hope that I can get to Div1 so I can impress everyone I know with a new color wish me luck!!!

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

    it doesn't matter buddy
    rating does nothing on the field
    hope we can make it together

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

The contest starts in 12 minutes. Good luck all!

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

Did you experience a bug? The site said the the contest had started.

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

I think the score distribution for hacks isn't fair. Hacking a Div2A and Div2D isn't the same. Harder problems should have more points for hacks than the easier ones. Also it would be interesting if hack score decreased with time :P

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

I hate acting like a copy-past machine
I'm talking about div2 A

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

Long submission queue. Anybody else facing this problem?

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

Rating prediction for this contest could be found here

Extensions:

Have a high rating and don't lose anything:)

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

    This rating-predictor is vert accurate. Thank you very much for it :)

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

    Thank u very much for the predictions.Great work.Anyway what do use to make these predictions.

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

      Actually prediction is quite wrong word, couple of my friend misunderstand it too. I would be happy if someone propose better service's name:) My app just periodically calculate rating change based on open formulas, assuming that current standings is final.

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

    It predicted exactly the same for me.

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

      Unfortunately today's prediction is a bit wrong — my tool predicted for everyone exactly 1 point higher rating than official.

      I haven't figured out yet what is reason of this, for previous contests prediction was absolutely correct:)

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

Judge 404 not found :P

Please fix it (I submitted my solution to E and scared when seeing long long queue :D).

UPD: Nevermind it got TLE :P

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

My solution is saying in queue for the last 5 minutes. :( and only 10 minutes are left for the contest.

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

Oh, another round about me! Thank you, my brother!

Good luck everyone in solving tasks about me!

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

the round is extended by 10 minutes.

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

What just happened? Was the contest extended?

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

So hard round, especially math in D

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

A similar problem of today's E : link

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

    just wait until the end of the round

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

    This problem was bad. It timed out solutions based on ordered statistics tree for example, but allowed sorted vectors. The query answer complexity is the same O(sqrtn*logn)...

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

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

How do you do C? I was trying binary search, it was working alright on smaller cases, but it wasn't working on bigger cases.

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

    (1e18 * (1e18 + 1)) / 2 is really big...you shouldn't try a day that is bigger than 1e10

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

      Ans is not more than 1e9. Cause in worst case ans = sqrt n which is not more than 1e9.

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

        Nope, if n<=m, then ans is n.

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

        The result is < sqrt(2 * 1e18), not 1e9

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

          Why ?

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

            Let m = 1, and N = 10^18. ie from 2nd day onwards bird start depleting the barn.

            => x*(x+1)/2 — 1 = N.

            => x^2 + x = 2*N + 1

            => x can be up to sqrt(2N)+1. => search from 0 to ceil(sqrt(2*1e18)+1)

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

    I used binary search. But I guess there was an O(1) solution as well.

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

Hating Math more and more.

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

My 10 minutes are wasted... :(

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

How to solve D?

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

    for each i such that arr[i] == (
    let x = number of ( from 1 to i — 1
    let y = number of ) from i + 1 to n
    add to the answer
    this can be simplified to

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

      Can you show how to simplify it? I got the summation part, but I couldn't simplify.

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

        =
        This can be seen as you have objects on left and objects on right and you have to select objects in total which is just

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

          I also came up with the summation part but couldn't simplify it. Now when I saw that I feel like a total retard.

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

            You and me both. :(

            Another way of looking at it is by saying that we have a group of (x+y) items, x of which are '(' and y are ')'. Now find all ways to select k (from 0) items from x and k+1 items from y.

            This is the same as selecting k items from x and (y-k-1) items from y.

            If we consider this summation, this is basically, selecting (k+y-k-1) items (i.e y-1 items) from the group (x+y), considering the ways in which we can 'divide' the (y-1) items in the two distinct groups.

            => Reduces to all ways of selecting y-1 items from (x+y) group.

            Funny thing is, I remember doing this reduction long back. Just couldn't redo it during the contest no matter how hard I tried. :/

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

              Is this ok? Suppose we have x "(" and y ")", and we want choose k items from each. so it should be (x + y)Cy ? But for case ()) and k be 1, it will give answer as 3 but not 2.

              Here I'm not going with the same logic as rajat1603 where he omits one "(" and adds k + 1 to y. Infact, if we have at position i, X chars "(" until i and Y chars of ")" after i, the answer should be xCx . yCx, am I right? :)

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

                If it was xCx*yCx, you are double counting a lot of cases, for example (()). at pos = 0, you will get 1C1*2C1 = 2 at pos = 1, you will get 2C2*2C2 = 1 at pos = 2, you will get 2C2*2C2 = 1 at pos = 3, you will get 2C1*1C1 = 2

                => total ways = 6, there's a lot of double counting in there.

                To remove double counting, iterate from left to right, and only add when a new '(' is encountered, finding number of ways where the current '(' is included. That's why we omit one count for '('.

                This way, in your example we get

                at pos 0, two pos (.) and (). or (3-1)C(1) at pos 1, we get 0 (since not '(') at pos 2, we get 0 (since not '(') => total = 2.

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

          According to the definition we can use (x-1) instead of (y-1), how would that be true?

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

        Suppose you have 2 collections of size x and y respectively. Consider the number of ways choosing y-1 from the combined collection. Now each of these ways can be broken down to choosing some number of items from among the x, and some number of items from among the y. This is exactly what the first formula says.

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

      My idea for D is divide and conquer compute answer for left part and right part and merge the answers and then compute the answer for range l to r , i don't know where i went wrong could some one please help : link [submission:http://codeforces.net/contest/785/submission/25527662]

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

      Let me check if I got your idea correctly: you're counting the number of RSBS which will include the '(' occurring at position i. Is that it?

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

        i am counting number of sequences such that that rightmost ( is at i

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

          This formula is giving 5 for the first sample:

          )(()()

          Could you please check my code? 25530480

          UPD: Sorry, found my bug.

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

        Steps : 

        1 compute the answer for range [l,m] and [m+1,r]


        2 get the open '(' count in [l,m] and get the ')' close count in [m+1,r]

        int minc=min(oc,cc);
        for(int i=1;i<=minc;i++){
            ans+=(C(oc,i,mod)*C(cc,i,mod)%mod);
            ans%=mod;
        }

        where C(n,r,mod) i am using Lucas theorem here .

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

          Did it work for you? I got WA case 4...

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

          The case )()()()(((( gives wrong answer with this approach. But I don't know how to fix it.

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

          I think the right summation for ans is:

          ans+=(C(oc-1,i,mod)*C(cc,i,mod)%mod);
ans%=mod;
          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why i from 0 to x ? Why not 0 to min(x, y) ?

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

    using Vandermonde's identity

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

A and B are silly problems
E is so standard, and now I found that it's even a copied problem
for D I can't come up with an easy-coding solution and I hope it has an interesting solution
I think C is good but it's so easy for a div2 C problem

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

My idea of D is to calculate the partial sums of open brackets and close brackets, and sweep a line from start to end while doing some combinatorics. However this is quadratic and I got TLE on pretest 6. Cannot find a method to optimize it.

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

Was server slow or problem with my service provider? I waited to hack two solution in two tab, refreshed again and again but couldn't put the cases :/

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

    Same here. Because of that problem I ended up putting the wrong hack and got unsuccessful hack.

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

A big glitch in COdeforces is there.I hacked a user's submission which was clearly wrong.The thing is time was over when my hack was in process, hence I got -50 points loss without hack being processed. Moderators please check the glitch

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

I solved the problem E in the last minute ,but I submitted it failed because it just had a "%lld" which was commented out.

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

404 rating not found :(

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

Too many Binary Search problems these days!

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

What is the hacking input of problem C?

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

Problem C has funny test data.

I passed the pretests but got TLE-hacked. :-(

The algorithm I used is speed through the first m days, and then manually implement the rest. I barely passed the pretests with a 499ms running time, but then failed with a hack.

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

what is the pretest 4 in E ?

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

What is the time complexity of this code? I tried to hack (unsuccessful ) it with test case:

1e18 1

its ans is 1414213563

this guy saves 1 initially in i and m in ans, and he updates i every time by 1, i.e., his while loop should be running 1414213562 times! But no TLE.

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

    Yes, it iterates about 1.4e9 times. But the loop is very very simple, so it might run faster than expected. It runs within 600 ms in my desktop.

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

    Also thought abouth this solution, but i guessed that there will be TL :/

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

      And it got AC :/

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

      Just determine on how simple your code is, i saw some people using similar approach with time complexity O(answer - m) as well but unfortunately got TLE.

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

What is the hack for problem C? :'v

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

    Anything with n<m worked, like 2 3

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

    If someone uses like m*m without long arithmetic, that just 100 and 10^18

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

How to solve C?

I tried binary search over fucntion f(mid) = n-m-(mid*mid + mid) and set answer as the ceil of the root of the equation.

Solution Link: Solution

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

    mid * mid is way too big

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

      So, what should be the approach?

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

        I used BigInteger on java. So i guess, that it is a long arithmetic also

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

        The upper bound can be lowered to about as this is approximately the maximum value of answer - m.

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

          How did you get the upper bound ?

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

            The answer is finding minimum value of X such that m + (1 + 2 + ... + X) ≥ n, which is same as finding min X s.t. X(X + 1) ≥ 2(n - m).

            So, X should be around , and here the maximum value of n is 1018. So upper bound is about .

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

              Thanks :)

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

              I should have read this comment earlier was trying to figure out the same thing and understood after 2 hours that the problem is with overflow.

              PS : Thanks for the explanation

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

        easy . mid * mid might be too big but mid * mid / 1e18 is good enough . just be careful to write mid / 1e18 * mid

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

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

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

The Rank, The Name :D

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

Pretest 7?

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

http://codeforces.net/contest/785/submission/25527584 Please point out the mistake!!!

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

Apparently O(10^9) is enough for problem C: 25509756

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

Problem C : What is wrong in this approach ?

if(m >= n){ cout<<n<<endl; return 0;} else { ll i = 1; while((i*i)+i < 2*(n-m)) i++; cout<<m+i<<endl; return 0; }

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

    i could be near to 1000*1000*1000 (sqrt(2*(n-m)).

    and your solution is O(i)

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

i did casework based on the index of the last '(', and then got a binomial formula. My code is here: http://codeforces.net/contest/785/submission/25528358

does anyone know how to do the binomial thingies more elegantly, as these take quite a long time to implement. I tried checking others' solutions but I think that most didn't use explicit binomial formulas.

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

In problem test case 16 999999998765257152 10 of problem C, my ans on ideone is showing correct but on CF it shows different answer why? http://ideone.com/mn2iXL

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

What does this means? http://prntscr.com/ekdcpv

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

same code giving ac with g++ 5.1 and wa with g++14 what's this ??? ac code wa code what's the problem

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

    Seems to be a double rounding issue here: sqrt(1 + 4 * q)). The result of this statement for the failing test case is 2828427123.0000000... , which is close to 'double' precision limits. So it might also be saved in memory as 2828427122.9999.... When implicitly casting this to int, it truncates downwards, so that's where the -1 of your answer comes from. The solution is described here. In short, add +0.5 , before downcasting to 'int'.

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

Problem C:

sqrt WA

sqrtl AC

how powerful is sqrtL?

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

guys, help? What's the difference between addition and subtraction? first loop passed the worst case (1e18 1) in 904ms and got AC while the second got TLE.

code with 1st while: here code with 2nd while: here

also, what other details can reduce running time? and thanks

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

    ignore

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

    n-m is constant. I suppose it is a compiler optimization.

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

    In your code, "n-m" is constant through all the iterations of the loop, whereas "s+m" is not constant because the value of 's' changes in the loop. I believe, the compiler optimises the "n-m" case by avoiding recomputing the value of "n-m".

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

      And what's about -faggressive-loop-optimizations? Is not the optimizer able to make simplification in such simple conditions?

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

      Thanks

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

Hi! Tell me please what's wrong with this solution for B. Runtime eror. Can't find a mistake :( http://codeforces.net/contest/785/submission/25512453

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

    comparator(x, x) should return false

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

    Your comparator function should give false for equal parameters, which is the reason that your sort won't work well. Use '<' in place of '<=', that should suffice.

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

    to avoid mistakes like this, you can use std::stable_sort instead

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

    I was actually looking for exactly such a mistake during contest, but unfortunately (for me) everyone in my room got it correctly.

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

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

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it 
	int len=(int)sqrt(n);
	int cnt=1; 
	for(int i=1;i<=n;i++){
		belong[i]=(i+len-1)/len;
		vl[i]=i;
		if(belong[i]==cnt)r[cnt]=l[cnt++]=i;
		else if(belong[i]<cnt)r[cnt-1]=i;
		change(belong[i],i,1);
	}
	for(int i=1;i<cnt;i++){
		printf("--%d %d\n",l[i],r[i]);
	}

n=3; on my computer: --1 1 --2 2 --3 3 here: --1 0 --2 1 --3 2 Why did this case take place?

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

My submission for C was off by one in some of the test cases. Can somebody help me with it? Here is my solution 25525973

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

    Your solution has wrong logic, please read the editorial.

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

I tried to solve problemE with segment tree plus ordered multisets but I am getting TLE on test 7.
The complexity of build function in my code in O(N * LOGN * LOGN * C). where C is the constant factor in segment tree.(C ≈ 4).
http://codeforces.net/contest/785/submission/25568923
Is there any way to optimize the build function.

→ Reply