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

Автор alex256, история, 13 дней назад, По-русски,

Привет, Codeforces!

Завтра, 15 марта 2017 в 18:05 (время московское) состоится очередной рейтинговый раунд на Сodeforces для участников из второго дивизиона. Участники из первого дивизиона, как обычно, смогут поучаствовать вне конкурса. Это мой второй раунд, надеюсь, он вам понравится больше, чем предыдущий.

На раунде, как обычно, будет пять задач и два часа на их решение. Советую внимательно прочитать условия всех задач. Также советую перепроверять решения на правильность, даже если они прошли все претесты — вердикт Претесты пройдены еще не значит, что решение полностью правильное! Желаю всем получить удовольствие от контеста и научиться чему-то новому, решая задачи.

Как и в прошлый раз, задачи будут про Антона и его друзей.

Хотелось бы поблагодарить Алексея Вистяжа (netman) за помощь в подготовке контеста, Владислава Вишневского (Vladik) за тестирование раунда, Дмитрия Клебанова (dakdima) за вычитывание условий, и конечно же, Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Codeforces и Polygon.

Разбалловка: 500 — 1000 — 1500 — 2250 — 2500.

UPD. Контест закончился, системное тестирование уже началось, разбор скоро появится.

UPD2. Появился разбор.

UPD3. Поздравляю победителей контеста!

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

Всем спасибо за участие! :)

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

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

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

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

Why not in main page?

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

finally a regular round after 10 days .

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

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.

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

Thanks for the contest.

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

ERROR 404 :p

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

Expecting a lot of Hacks !!

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

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

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

I advice you to read all the problems' statements attentively

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

  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится
    Verdict Pretests passed doesn't mean that the solution is completely correct! 
    

    True

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

      Verdict Pretests passed mean that the solution is completely incorrect!

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

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

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

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

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

    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

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

Div. 1 Round not found.

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

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

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

I hope short statements!!!

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

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

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

      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.

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

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

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

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

          In Allah's safeguard

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

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

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

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

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

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

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

Contest 404 not found :P

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

Contest 404 not found ! :P

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

Желаю всем на этом раунде +404 к рейтингу!

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

вердикт Претесты пройдены еще не значит, что решение полностью правильное!

Надеюсь это намёк на возможность взломов.

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

:|

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

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

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

Thanks

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

Hoping of getting a color change to dark blue:)

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

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

This post scares me for the contest.

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

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

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

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

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

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

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

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

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

Автокомментарий: текст был обновлен пользователем alex256 (предыдущая версия, новая версия, сравнить).

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

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

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

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

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

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

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

finally a regular round after many days.

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

The contest starts in 12 minutes. Good luck all!

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

The contest starts in 12 minutes. Good luck all!

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

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

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

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

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice problems ... thanks alex256

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

Unable to Hack

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

Hack system not working

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

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

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

Long submission queue. Anybody else facing this problem?

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

Rating prediction for this contest could be found here

Extensions:

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

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

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

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

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

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

      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.

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

    It predicted exactly the same for me.

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

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

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

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

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

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

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

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

Good luck everyone in solving tasks about me!

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

the round is extended by 10 minutes.

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

What just happened? Was the contest extended?

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

So hard round, especially math in D

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

A similar problem of today's E : link

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

    just wait until the end of the round

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

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

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

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

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.

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

Hating Math more and more.

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

My 10 minutes are wasted... :(

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

How to solve D?

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

    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

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

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

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

        =
        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

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

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

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

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

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

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

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

                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.

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

                  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.

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

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

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

        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.

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

      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]

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

      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?

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

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

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

        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 .

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

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

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

    using Vandermonde's identity

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

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

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

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.

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

when SYSTEM TESTING WOULD START?

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

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

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

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

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

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

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

404 rating not found :(

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

Too many Binary Search problems these days!

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

What is the hacking input of problem C?

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

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.

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

what is the pretest 4 in E ?

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

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.

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

    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.

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

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

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

      And it got AC :/

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

      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.

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

What is the hack for problem C? :'v

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

hope today the system starts testing -_-

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

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

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

    mid * mid is way too big

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

      So, what should be the approach?

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

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

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

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

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

          How did you get the upper bound ?

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

            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 .

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

              Thanks :)

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

              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

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

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

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

Автокомментарий: текст был обновлен пользователем alex256 (предыдущая версия, новая версия, сравнить).

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

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

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

 The Rank, The Name :D

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

Хороший раунд

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

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

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

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

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

Почему зависло на 100%?

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

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

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

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.

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

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

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

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

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

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

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

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

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

Problem C:

sqrt WA

sqrtl AC

how powerful is sqrtL?

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

Забавно. Моё решение задачи С упало на фин.тестах, потому что строка: (long long)ceil((sqrt(1+8*(long double)(n — m)) — 1)/2) + m для значений 999999998765257152 10 под MS C++ выдаёт 1414213571, а под GNU C++ 11 — 1414213572. Я "в восторге".

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

    Тесты специально так подбирались. Рассчитывалось, что все решения без бин.поиска обломаются и не пройдут по точности. Это сделано специально.

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

      Зачем решать в одну итерацию, лучше за логарифм, логично.

      UPD. Если таким тестом действительно отсекалось альтернативное решение задачи, то это по крайней мере глупо, не говоря уже о корректности. Задача решена и решена правильно. Если она должна решаться только бинпоиском, то будьте добры, составьте так условие, чтобы прямое решение не проходило. Гробить решение за счёт погрешности библиотечных функций — это свинство.

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

        Да, но ведь было много решений формулой)

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

        Почему "Гробить решение за счёт погрешности библиотечных функций — это свинство"?

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

          Потому что контесты не направлены на выявление багов компиляторов. Если я использую sqrt, я полагаю, что он даст правильный результат, и не прыгаю с бубном возле ноутбука во время систестов в надежде, что при специально подобранных входных данных эта функция вернёт мне необходимые милионные доли результата, тогда как тип данных эту точность подразумевает.

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

            Контесты направлены на получение верных решений. Мне кажется, довольно глупо использовать sqrt для вычисления корня из целых чисел порядка 10^18, забив на возможную погрешность. Не понимаю, как можно засылать и надеяться, что не будет специально подобранных тестов. Это как будто написать самые тупые хэши и надеяться, что авторы не будут их ломать. Или написать неверное асимптотически решение с оптимизациями и надеяться, что оно зайдет, а когда не зайдет, сказать, что отсечение верных решений (ну оно ж верное, просто медленное) — свинство.

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

              Написать кривой хэш или накосячить с асимптотикой — это вина программиста, а то, что sqrt по-разному работает на двух компиляторах под один и тот же язык — нет. Вот в этом моё негодование.

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

                Разумеется, программист не виноват, что sqrt — неточная функция. Но он должен это знать и уметь использовать ее так, чтобы это не доставляло проблем. Поэтому Ваше негодование кажется мне, мягко говоря, немного необоснованным.

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

        На мой взгляд, лучше знать особенности работы библиотечных функций (например, погрешность в стандартной функции sqrt), прежде чем их использовать. Сильные тесты должны были сломать такое решение по точности. И да, это решение не предполагалось мной как правильное.

        Советую лишний раз не использовать функции, работающие с вещественными числами, без крайней на то необходимости.

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

          В таком случае, почему оно должно заходить под одним компилятором, и откидываться под другим? Это тоже стоит знать и учитывать, когда решаешь задачу?

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

      int main() { long long n,m; std:: cin >> n >> m; long double D = 1 + 8 * (n-m); D = sqrtl(D); long double t = (D — 1)/2; if(n <= m) std::cout << n; else if(t > (long long)t) std::cout << (long long)(t)+(1+m); else std::cout << (long long)(t+m); } не обломалось (#25530070)

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

В задаче В поставил необходимую константу 2е8 вместо 2е9. Удивительно, что никто не взломал во время раунда. Из-за этого в итоговой таблице опустился на 700 мест.

"Вердикт Претесты пройдены еще не значит, что решение полностью правильное!"©

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

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

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

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

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

    comparator(x, x) should return false

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

    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.

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

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

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

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

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

Автокомментарий: текст был обновлен пользователем alex256 (предыдущая версия, новая версия, сравнить).

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

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

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

Поправьте ссылку на разбор. http://codeforces.com/blog/entry/50996

UPD: Пока писал, уже поправили.

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

жду разбор задачи

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

Thanks for the contest.

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

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

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

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.

»
11 дней назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
	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?

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

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

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

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.