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

Автор alex256, история, 8 месяцев назад, По-русски,

Привет, 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

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

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

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

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

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

Why not in main page?

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

finally a regular round after 10 days .

»
8 месяцев назад, # |
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.

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

Thanks for the contest.

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

ERROR 404 :p

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

Expecting a lot of Hacks !!

»
8 месяцев назад, # |
  Проголосовать: нравится +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

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

I advice you to read all the problems' statements attentively

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

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

    True

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

      Verdict Pretests passed mean that the solution is completely incorrect!

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

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

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

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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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

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

Div. 1 Round not found.

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

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

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

I hope short statements!!!

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

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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.

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

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

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

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

          In Allah's safeguard

»
8 месяцев назад, # |
  Проголосовать: нравится +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...:)

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

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

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

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

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

Contest 404 not found :P

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

Contest 404 not found ! :P

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

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

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

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

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

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

:|

»
8 месяцев назад, # |
  Проголосовать: нравится -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 ..

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

Thanks

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

Hoping of getting a color change to dark blue:)

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

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

This post scares me for the contest.

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

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

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

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

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

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

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

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

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

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

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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!!!

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

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

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

finally a regular round after many days.

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

The contest starts in 12 minutes. Good luck all!

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

The contest starts in 12 minutes. Good luck all!

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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

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

nice problems ... thanks alex256

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

Unable to Hack

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

Hack system not working

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

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

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

Long submission queue. Anybody else facing this problem?

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

Rating prediction for this contest could be found here

Extensions:

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

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

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

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

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

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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.

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

    It predicted exactly the same for me.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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:)

»
8 месяцев назад, # |
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

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

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

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

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

Good luck everyone in solving tasks about me!

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

the round is extended by 10 minutes.

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

What just happened? Was the contest extended?

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

So hard round, especially math in D

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

A similar problem of today's E : link

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

    just wait until the end of the round

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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)...

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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.

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

Hating Math more and more.

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

My 10 minutes are wasted... :(

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

How to solve D?

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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

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

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится +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

        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится 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. :/

            • »
              »
              »
              »
              »
              »
              »
              8 месяцев назад, # ^ |
                Проголосовать: нравится +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? :)

              • »
                »
                »
                »
                »
                »
                »
                »
                8 месяцев назад, # ^ |
                  Проголосовать: нравится +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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 месяцев назад, # ^ |
                  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.

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

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

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится +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.

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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]

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 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?

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

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

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

          This formula is giving 5 for the first sample:

          )(()()

          Could you please check my code? 25530480

          UPD: Sorry, found my bug.

      • »
        »
        »
        »
        8 месяцев назад, # ^ |
        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 .

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

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

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

    using Vandermonde's identity

»
8 месяцев назад, # |
  Проголосовать: нравится -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

»
8 месяцев назад, # |
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.

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

when SYSTEM TESTING WOULD START?

»
8 месяцев назад, # |
  Проголосовать: нравится 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 :/

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится 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

»
8 месяцев назад, # |
  Проголосовать: нравится +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.

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

404 rating not found :(

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

Too many Binary Search problems these days!

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

What is the hacking input of problem C?

»
8 месяцев назад, # |
  Проголосовать: нравится 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.

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

what is the pretest 4 in E ?

»
8 месяцев назад, # |
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.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +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.

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

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

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

      And it got AC :/

    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится +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.

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

What is the hack for problem C? :'v

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

hope today the system starts testing -_-

»
8 месяцев назад, # |
  Проголосовать: нравится 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

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

    mid * mid is way too big

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

      So, what should be the approach?

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

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

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

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

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

          How did you get the upper bound ?

          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится +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 .

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

              Thanks :)

            • »
              »
              »
              »
              »
              »
              »
              8 месяцев назад, # ^ |
                Проголосовать: нравится +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

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

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

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

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

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

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

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

 The Rank, The Name :D

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

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

»
8 месяцев назад, # |
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

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

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

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

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

»
8 месяцев назад, # |
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; }

»
8 месяцев назад, # |
  Проголосовать: нравится 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.

»
8 месяцев назад, # |
  Проголосовать: нравится +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

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится 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

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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'.

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

Problem C:

sqrt WA

sqrtl AC

how powerful is sqrtL?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    • »
      »
      »
      8 месяцев назад, # ^ |
      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)

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

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

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

»
8 месяцев назад, # |
  Проголосовать: нравится +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

»
8 месяцев назад, # |
  Проголосовать: нравится 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

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

    comparator(x, x) should return false

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thanks for the contest.

»
8 месяцев назад, # |
  Проголосовать: нравится 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 :(

»
8 месяцев назад, # |
  Проголосовать: нравится 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.

»
8 месяцев назад, # |
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?

»
8 месяцев назад, # |
  Проголосовать: нравится 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

»
8 месяцев назад, # |
  Проголосовать: нравится 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.