alex256's blog

By alex256, history, 5 months 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 (dakdima) 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. liu_cheng_ao
  2. Gauss
  3. binsjl
  4. hotwater
  5. mister_dudec

Thanks everyone for participating :)

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

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not in main page?

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

finally a regular round after 10 days .

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Thanks for the contest.

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

ERROR 404 :p

»
5 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Expecting a lot of Hacks !!

»
5 months 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

»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Verdict Pretests passed mean that the solution is completely incorrect!

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months 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?

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Div. 1 Round not found.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope short statements!!!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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 :)

        • »
          »
          »
          »
          »
          5 months 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

»
5 months 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...:)

»
5 months 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!

  • »
    »
    5 months 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).

»
5 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Contest 404 not found ! :P

»
5 months ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

:|

»
5 months 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 ..

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Thanks

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Hoping of getting a color change to dark blue:)

»
5 months ago, # |
  Vote: I like it -32 Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +17 Vote: I do not like it

This post scares me for the contest.

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +35 Vote: I do not like it

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

»
5 months 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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months 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!!!

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

finally a regular round after many days.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest starts in 12 minutes. Good luck all!

»
5 months 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.

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problems ... thanks alex256

»
5 months 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

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Long submission queue. Anybody else facing this problem?

»
5 months 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:)

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

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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It predicted exactly the same for me.

    • »
      »
      »
      5 months 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:)

»
5 months 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

»
5 months 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.

»
5 months 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!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the round is extended by 10 minutes.

»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

What just happened? Was the contest extended?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So hard round, especially math in D

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

A similar problem of today's E : link

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just wait until the end of the round

  • »
    »
    5 months 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)...

»
5 months ago, # |
  Vote: I like it +220 Vote: I do not like it

»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of this equation but couldn't implement in time. (ans * (ans + 1))/2 = N + ans * M — ((M * (M + 1))/2).

    It says, amount of food birds ate = N + grains_brought — grains_wasted I'm not sure if it's correct.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why ?

          • »
            »
            »
            »
            »
            »
            5 months 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)

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hating Math more and more.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

My 10 minutes are wasted... :(

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve D?

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months 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. :/

            • »
              »
              »
              »
              »
              »
              »
              5 months 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? :)

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Thanks priyanshu_95 for taking the time to explain. :) However in the example, (()), with xCx. yCx we would get 3 but not 6. We get three like this: 1C1 . 2C1 + 2C2 . 2C2 + (2C2 . 1C2 = 0) + (2C2 + 0C2 = 0). However, The real answer is 5.

        • »
          »
          »
          »
          »
          5 months 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?

      • »
        »
        »
        »
        5 months 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.

    • »
      »
      »
      5 months 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.com/contest/785/submission/25527662]

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

      • »
        »
        »
        »
        5 months 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 .

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 months 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.

        • »
          »
          »
          »
          »
          5 months 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;
          
    • »
      »
      »
      5 months 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) ?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I thought the same...

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        for i > x you can consider the terms as 0 so it it doesn't matter.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have understood it, thanks a lot :D

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    using Vandermonde's identity

»
5 months 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

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when SYSTEM TESTING WOULD START?

»
5 months 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 :/

  • »
    »
    5 months 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.

»
5 months 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

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

404 rating not found :(

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Too many Binary Search problems these days!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hacking input of problem C?

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the pretest 4 in E ?

»
5 months 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.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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 :/

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And it got AC :/

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack for problem C? :'v

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anything with n<m worked, like 2 3

  • »
    »
    5 months 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

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mid * mid is way too big

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, what should be the approach?

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How did you get the upper bound ?

          • »
            »
            »
            »
            »
            »
            5 months 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 .

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Thanks :)

            • »
              »
              »
              »
              »
              »
              »
              5 months 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

      • »
        »
        »
        »
        5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +21 Vote: I do not like it

 The Rank, The Name :D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Submission no: 25513626 It won't work for the following test case, but it is passed in system test. Test Case: 2 1 1 3 3 2 1 1 3 3

correct output:2 but the solution output will be 0

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 months 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; }

  • »
    »
    5 months 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)

»
5 months 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.com/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.

»
5 months 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

»
5 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

»
5 months 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

  • »
    »
    5 months 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'.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C:

sqrt WA

sqrtl AC

how powerful is sqrtL?

»
5 months 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

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    ignore

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    5 months 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".

    • »
      »
      »
      5 months 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?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

»
5 months 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.com/contest/785/submission/25512453

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    comparator(x, x) should return false

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow for problem C my code was

#include <iostream> 
#include <cstdlib> 
#include <cmath> 
#include <algorithm> 
using namespace std; 

int main(){
	long long n,m;  
	cin >> n >> m; 
	if (m > n) m = n; 
	long long k = ceil((double)(-1+sqrt(1+8*(n-m)))/2.0);  
	cout << m+k << endl; 
	return 0; 
}

and I got a wrong result on system test (test case 16). But when I changed the code to

long long k = ceil((long double)(-1+sqrt(1+8(n-m)))/2.0); 

I pass all system tests... I feel so sad :(

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May I make one suggestion: in Division 2 contests, the updates should first list the Division 2 winners, and then the Division 1 winners.

Great contest and very nice problems! Thanks.

»
5 months 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?

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution has wrong logic, please read the editorial.

»
5 months 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.com/contest/785/submission/25568923
Is there any way to optimize the build function.