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

Автор djm03178, история, 3 года назад, По-английски

오랜만이에요, 코드포스! (Long time no see, Codeforces!)

I'd like to welcome all of you to Codeforces Round 688 (Div. 2)! The contest will start at Dec/04/2020 16:05 (Moscow time), and it is rated for all participants with ratings under 2100. Note the semi-unusual start time.

You will be given 6 problems and 2 hours and 15 minutes to solve them. The score distribution will be announced soon.

All problems are prepared by me, with a lot of help from the testers making me realize that my solutions are dumb.

Thanks to Green55, JooDdae, cs71107, YeongTree, Savior-of-Cross, jh05013, blobugh, 39dll, InfiniteChallenge, Pentagon03, sonjaewon, slah007, jooncco, and kalki411 for testing the round, and especially xiaowuc1 for helping polish English statements as well. I would also like to thank 300iq for round coordination, and MikeMirzayanov for the great Codeforces and Polygon system.

See you in the round!

UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3500.

UPD 2: The round is finished. Thanks for your participation! I'm sorry about underestimating the difficulty of problem B, but I hope you still enjoyed the problems! The editorial will be posted in a minute.

UPD 3: The editorial is out!

UPD 4: Congratulations to the winners!

Div. 2

1: caoyizhong

2: Depth_First_Search

3: Misaka23334

4: PleasePreyForMe

5: EzioAuditoreDaFirenze

Unofficial Div. 1

1: Geothermal

2: jiangly

3: neal

4: saketh

5: Pyqe

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

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

As the problemsetter, I want comments!

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

As a tester, Please enjoy problems!

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

    why is this getting downvotes lmao

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

      Even when I saw that comment first time, it already got about 70 downvotes, which made me surprised.

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

      When I first saw this comment it got more than 70 downvotes and I didn't know why... To tell the truth, I haven't seen such kind of comments being downvoted before.

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

    As a tester, I think he deserves upvotes. He did a great job as a tester.

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

Wow.. I'm looking forward to participate in this round!

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

Korean Round!

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

Is it rated?

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

Amazing writers Amazing testers and Amazing coordinator i wil remember the day 2020 December 4 forever.

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

    It's my ex-girlfriend's birthday on that day... Should I wish her excitedly, normally or not at all? The only thing I'm excited about is the contest and a little bit about the INDIA-AUSTRALIA cricket match.

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

      Then several cricket match is given and they have distinct costs and happiness

      Unfortunately, I only participate k match among them

      What is the best strategy I maximize the girlfriend's happiness and then minimize the costs I spend

      Wow amazing problem!

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

      .

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

Another Korean Round! This round will be amazing!

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

This round is sexy.

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

팬이에요 :fan:

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

Hope they dont give out a contest full of "interesting observations" problems.

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

꼭 참가하겠습니다!(I will participate in this competition!) :god: :fan:

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

please don't make it like educational round 99 !

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

    Please make it like educational round 99 so that we can see where we falter and keep learning new things!

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

Wait.... A negative rating tester??? Thats something new

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

Hope contest will bring some new learning

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

Oh friendly time for Chinese! But we Chinese will have a important contest (NOIP) right after this, hope for good luck after all!

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

May the pretests be strong!

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

Where the difficulties of problems in Codeforces round 685 and other?

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

unusual start time

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

Hope to see some interesting problems with short statements and strong pretests :)

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

The contest will start at Friday, December 4, 2020 at 18:35UTC+5.5.

Most Important Note the unusual start time.

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

Oh, time is more friendly than others

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

한국 시간 고려해서 semi-unusaul start time으로 맞춰주신 거 감사합니다! Thanks for considering Korean time!

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

Is it rated?

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

    It's already mentioned in bold. Should they just write it in the announcement heading for you?

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

Why semi-unusual start time and not unusual? :thonk:

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

Can I get contribution without posting a meme

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

Hope a Great contest

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

hope to become green

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

t's very sad that on the day of the round there is an RMI and I won't be able to raise the rating :(

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

i hope this time queue should be fast not as previous two contests !!

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

Plot twist-Early announcement was made just to get more upvotes.

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

hmmm strange Monogon hasnt put any comment yet.

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

Hope this time we don't have to wait too much time for the rating.

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

코드포스 is the wrong spelling

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

Good to see u again blobugh !!!

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

I hope there are more interesting greedy, math, constructive algorithms.It can exercise thinking :D

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

vaibhav garg

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

my first contest after reaching expert! Super excited :D

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

    I feel great when I see people like you, as some people after reaching expert, stop giving contests in order to uphold their ratings.

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

      It's likely that I might become a specialist after today's contest, but I love this quote from the Batman movie — "Why do we fall? So we can learn to pick ourselves up."

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

i wish to be a good contest

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

Hope the problem statements are as short as announcement

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

Wow... From the Round #620, we can see that djm03178 is a very talented problemsetter. I think this round will be great!

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

Is there a way to cancel the registration? I can't participate suddenly!!!

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

    Yes, you can cancel it, but remember — no submissions -> contest unrated for you

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

I should go to sleep before 11:00 tonight so actually this div.2 is the last round before I leave :)

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

As a participant, thanks djm03178 for the contest.

In conclusion, good luck to everyone ^_^

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

Hope to perform good in my 100th contest :) Good luck everyone....

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

I think djm03178 has done a typo while writing Div-*2* lol.

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

Is it Codeforces Round #688 (Div. 1.5)?

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

Is this a DIV 1.5 round?

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

I feel that in quest of making unique problems, problem setters are increasing the difficulty of the problem.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
3 года назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

I think there was some other comment related pob B. what's going on? why codeforces deleted comment related pob B?

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

    It is against rules to discuss problems before a contest ends. Please, wait for the end of the round.

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

      Dude, I got banned on 2 days and can't participate on next cf round on FenWick because of writing comments "A < C < D < B for me", It's soo stupid. I think it's not prohibited to write ur opinion about level of problem not statement.

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

        Your opinion on the difficulty of problems is information that can affect other participants. Just never talk about problems until the round is over. It's very simple. By the way, I recommend solving problems during the round. Note that the read-only mode does not limit participation in the rounds.

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

    The owner's comment makes it seem like the problem in its essence was being discussed. Perhaps that was the plan all along to delete the comments and make it seem like the approaches to the problem were being discussed. On the contrary, statements were made to connote the recent trend in absurd difficulties for Div 2B and there is nothing from the rules here that forbids that. If a specific rule bears that intent, I would humbly suggest that the English version is re-written in a way that the meaning is not lost during translation.

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

      Can-do's and Can't-do's 5th

      "The contestants are forbidden to talk about subjects, related to the problems, with anybody, including other contestants. It is only allowed to ask questions to the jury via the system (see the 'Questions' section)."

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

I hope your rate increases :)

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

I think codeforces is trying to avoid beginners. People are expecting a lot even from B.
All those confidence of solving A,B,C during contest is going down... day by day...

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

    This is a Div2 tho. I agree that the second problem may seem harder than usual but not that much. It was an easy to implement solution which needed a very nice observation. I think that it's better for the second problem to have something tricky in it, instead of being very easy and boring. Trust me, this kind of problems are good for beginners too because it teach them to think outside the box :). Also, there are div3 contests which kind of allows the beginners to solve the first 3 problems quick.

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

Now I understand, contest timing > 2 hours then it is going to be Div 1.5

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

In my opinion, B felt much harder than C.

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

I'm curious how many people just solved D quickly by just simulating to get the expected value of (k 0s) followed by a 1 and observing the answer from that (though it is pretty easy to obtain even without that).

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

    Transforming the tries to coin flips, it totally sounds like a common probability problem, which of course it is heh: https://math.stackexchange.com/questions/364038/expected-number-of-coin-tosses-to-get-five-consecutive-heads

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

      Yeah, one of my friends just told me about that, but simulating is really trivial as well (and faster if your math is weak like mine) with a simple code like this, and its pretty intuitive why it should work after you see the result.

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

    I derived expected value for covering different size gaps between successive checkpoints. For $$$g = 1$$$, ie consecutive checkpoints, expected value is $$$2$$$. For $$$g = 2$$$, using expected values, we get $$$6$$$ and then $$$g = 3$$$ we get $$$E(g) = 14$$$, using three equation. and then I thought maybe it is $$$E(g) = 2^{g+1}-2$$$ but dont know the general proof

    Edit:

    Ok link by robinz62 was useful, thank you

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

    Lol You don't even need to simulate take a look at 1265E - Beautiful Mirrors

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

Got terribly stuck at B. Can anyone please give me a hint now since the contest is over?

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

    first try to find how can you find min value of given array without any changes

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

    The key observation is that changing a number at begin is like removing it from the array.

    So we need to find which number, if removed, contributes most.

    The contribution per number is the sum of differences of the adjacent numbers, and the number itself.

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

    If you want to see the approach or idea for solution of B:

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

how to solve D??i feel dumb for 1 hr after solving c.

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

    Note that You need expected 2^(k+1)-2 moves to do 10000...0 where there are k digits.

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

    Number of steps to cross 1 is 2 , 1 0 is 6 , 1 0 0 is 14 , 1 0 0 0 0 is 30 . relation is s = 2*s+2 . Odd number of steps is never possible since to crossing any stage must be even . Now find biggest s which is close to n and keep doing that until n reaches 0 . For example for 20 it will be 14 + 6 i.e 1 0 0 1 0

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

Why didn't this work for C?I think there is a carazy mistake there.

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

I think problem D needs more explanation.

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

D, how can we get an integer number of expected tries at all?

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

    I guess the expected value converges to an integer when total tries is infinity.

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

      If there is one stage, then

      1/2 + 2 * 1/4 + 3 * 1/8 + ...

      I do not see for any number of stages how I could make such sequence ever result in an integer sum, by adding some checkpoints :/

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

        See this

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

          This is helpful link, thanks.

          So my above formular is kind of right, and simply sums up to 2.

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

        probability you will cross that level is 1/2 . Now i ask you a question , how many times you will win if you play at that level 2 times ? Answer is 1 . Else probability won't be 1/2.

        You can similarly generalize that beating that level n times will take 2*n matches .

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

    Beating n consecutive levels without a checkpoint is equivalent to getting heads in a coin flip n times in a row. Having that in mind you can read https://www.codechef.com/wiki/tutorial-expectation.

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

    Probability to cross a level is 1/2 . Thus total number of moves require to cross is 2 . Suppose i crossed a level and fell again to it . Then again expected number of moves required to cross it again will be 2 and thus total 4. Hence not only it will be integer but also even.

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

      Ah... ok, got it. Thanks. I was simply completly wrong ;)

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

      Probability to cross a level is 1/2 . Thus total number of moves require to cross is 2 .

      How? How can you relate probability with number of moves?

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

 Why guys why?? :(

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

How to solve D ?

It's either too much math or too much pattern finding

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

    If you have a range with 1 at the beginning and k-1 0s after, then this range increases the expected value by 2^(k+1)-2. So while remaining length is > 0 you can simply take largest k for remaining length and put 1 and k 0s at the answer.

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

      What's the proof for that? I tried to prove it during contest but couldn't complete the proof.

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

        https://codeforces.com/contest/1265/problem/E

        See this problem and its editorial

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

        I found that off google by searching "expected number of coin tosses before getting n in a row", where there's a convenient codechef link with the closed form

        the proof does seem kind of messy, so I suspect most people might've done the same

        EDIT: I realize it's quite obvious now if you write the recurrence relation $$$E_k = E_{k - 1} + \frac{1}{2} + \frac{1}{2}(1 + E_k)$$$

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

          I firstly had a formula like 2^0 * k + 2^1 * (k-1) + 2^2 * (k-2)+...+2^k * 1 + 2^k. And I wrote bruteforce for k to 100 and saw the pattern.

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

      You mean\begin{equation} {2^{k+1}-2} \end{equation} How do you prove it ?

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

        Let $$$E_x$$$ be the expected number of the state where you have beat x stages.

        It's easy to get $$$E_k=0$$$ and $$$ E_x = \frac{1}{2}E_0 + \frac{1}{2}E_{x+1}+1 , x < k$$$

        After calculation, you will get $$$ E_0 = \sum_{i=1}^k \frac{1}{2^i} + \sum_{i=1}^{k} \frac{1}{2^{i-1}}$$$

        And it means $$$E_0 = 2^{k+1}-2$$$

        That's the answer of k stages like 1 0 0 ... 0 0

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

        There is one more beautiful way to proove it.

        1. note that when you are at a 1-cell and you have $$$s - 1$$$ 0-cells till the next checkpoint you either succeed instantly with the $$$1/2^s$$$ probability, or you loose somewhere and return to the 1-cell. This situation is equal to flipping a coin that gives heads with the probability of $$$p = 1/2^s$$$. It's a known fact that the expectation of the number of throws is $$$\frac{1}{p} = 2^s$$$
        2. now let's realize that the expectation of number of times you visit a cell after a checkpoint halves as you go further. It becomes quite obvious if you think about revisiting the 0-cell as about going back into this cell instantly after loosing a game in a cell after it. Indeed, if you loose a game you return to the last checkpoing and so steps after it you return to the 0-cell we are talking about.
        3. hence, the expectation of revisiting the cells of the 10...0 block with k zeros is $$$2^{k + 1} + 2^{k} + \ldots + 2 = 2^{k + 1} + 2^{k} + \ldots + 2 + 1 + 1 - 2= 2^{k + 2} - 2$$$

        Voila.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    My approach passed 8 preteset . don't know correct or not.
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

was there an easy way to solve c or it was brute force???????

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

How to do D...

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

Apart of the long statements and the difficulty of problem B, I think the problems were amazing! Thanks for the authors.

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

I hate you Gildong !!

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

Where to see the solution???????????

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

can someone help me with problem C?

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

    triangle space is base*height/2 since they want it multiplied by 2 so it's just base*height so you just need to find the longest line for each number and you can calculate the max space

    I got the idea but sadly could not code it in time

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

B was way difficult !! i tried around all approaches but was getting none of them correct

Thought of sorting and making all elements equal to median of the sorted array that didnt even work , making all elements equal to minimum , maximum That also didnt work , taking absolute difference between the adjacent elements that didnt even work !!

I think B was really a difficult question !!

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

Very strict time complexity for C

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

    its not strict. You are saving index of each character. NOW, if all 4*10^6 are same character then you complexity will be (4*10^6)^2 (as you are traversing each possible pair of each character) which is definitely not in time limit.

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

      are u seriously? I think, (4*10^6)^2 = 1.6e+13 is way too much, and also t <= 2000. O(n^2) is not good for this.

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

      Continuous maximum value of n could be 2000. Hence the value 4*10^6

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

        But then matrix is n*n and u r saving indices of character so your set contains 4*10^6 elements. Moreover u r traversing ur set in two loops making it near 10^13...

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

    My O(n*10*4*2)ish 100378697 got AC with 2997ms. I can't even.

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

What should I do, if someone asked me to send him the solution of the problem until the end?

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

    humiliate him, tag that cheater in your comment

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

      Sulaimon is a cheater then

       (It means: "Give me the solution to the second problem in Div. 2 contset, please")

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

        After you have uploaded your image on any site(like imgur), open that image on that site,
        right click -> open image in new tab, then copy the URL(should end with JPG/PNG), use that URL to upload image

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

Problem C gave me PTSD

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

Long and difficulty problem statements !!

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

I hate problem B

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

what the fucking B

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

Damn that B problem will nerf my rating by far.. Like you could skip one of the numbers each time so I decided 3 cases skip the 1st one, skip the smallest one and skip the biggest one but I would not get the AC. I would get WA on test 5. Can someone give me a test case where these cases don't work?

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

Can anyone explain the solution of problem B...?

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

Any Explanation on how to solve B ?

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

Struggled on B for almost 2 hours but solved D in less than 10 minutes :( Feeling very terrible

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

    Story of my Codeforces career. And the funny thing is you need guts to skip B and go do D. Because come you did not solve D guys that were persistent on B will get B and you will get less score than them even if you get B later.

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

Div2 B took me 20 minutes to understand the problem, 40 minutes to crack, 20 minutes to get the idea, 10 minute to implement, 20 minute fixing bug. And after that what happened? The contest has been finished!! BTW, problem b was amazing!

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

This round was a nightmare and a reminder of how much I need to practice

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

How to not brick on this contest's B?

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

Unpopular opinion: D is easier than B and C.

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

This was a good set of problem set.

I Enjoyed solving them

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

This kind of contest is bad for mental health.

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

Not a good round, the statements wasn't clear enough.

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

:D I used 8 ifs for each for in problem C and get TLE :D

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

Unpopular opinion I liked the contest B was C level but it's a nice problem the solution is not stupidly obvious .. solving C isn't too hard but understanding it may take some time

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

solution to problem B.

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

    Please where did you get the idea that changing one element of the array implies removing it. If all the elements before the element you changed are not equal, I don't think you have removed it.

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

While solving problem B , I observed that for given array total operations required would be sum of absolute difference of consecutive elements. How to prove it concretely ?

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

    Start from last element add absolute diff of last and second element... Then last 2 elements becomes equal and equal to 2nd last. Go to third last element then add the abs diff bw third last and second last and go on.... resulting in sum of ablolute diff bw adjacent elements..

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

    In an array where all elements are equal, the sum of absolute differences of consecutive pairs of elements is $$$0$$$. The reverse also applies — if that sum is $$$0$$$, all the elements must be equal.

    When incrementing / decrementing the suffix starting from index $$$i$$$, note that all the differences between elements in the suffix and the differences between elements outside the suffix remain the same. The only place where that difference changes is in the pair of elements where one is inside the suffix and the other is outside it — indices $$$i - 1$$$ and $$$i$$$.

    Since each operation changes the difference (and, performing optimal operations, decreases the absolute difference) by exactly $$$1$$$, number of operations required is greater than or equal to the sum of the absolute differences of consecutive elements. The shown algorithm can do it in that number of operations, thus the sum of the absolute differences of consecutive elements is the minimum number of operations required.

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

After CF predictor predicts me -50,

What my mouth says: Rating is not the matter. The idea u learnt is more.

What my mind says: Rating is the matter,dude.

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

Please explain problem B in more detail.

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

    Let we have numbers $$$a_1, a_2, a_3... a_n$$$. Let make them all equal to m.

    Then to make $$$a_1$$$ equal to m we need $$$|a_1 - m|$$$ steps, and all other leemtns would increase by $$$m - a_1$$$.

    Then, to make $$$a_2$$$ equal to m, we need $$$|m - (a_2 + (m - a_1))|$$$ steps since $$$a_2$$$ is $$$a_2 + (m - a_1)$$$ now. $$$|m - (a_2 + (m - a_1))| = |a_1 - a_2|$$$.

    And total addition to elements is equal to: $$$m - a_1 + (m - (a_2 + (m - a_1))) = m - a_2$$$. From here we can see, that total addition to elements after $$$i$$$-th step are going to be $$$m - a_i$$$. So, the ansewer for number m is equal to $$$|m - a_1| + |a_1 - a_2| + |a_2 - a_3| + .. + |a_{n-1} - a_n| $$$.

    Now we want to minimize that sum. We can always choose $$$m = a_1$$$ to make first number 0. After that we just want to minimize the sum we have.

    To do that let assume we change $$$a_{j}$$$. After changing $$$a_j$$$ to $$$a_{j-1}$$$ (actually we want $$$a_j$$$ to be in interval from $$$a_{j-1} $$$ to $$$a_{j+1}$$$). After that $$$|a_{j-1} - a_j| + |a_j - a_{j + 1}|$$$ is going to become $$$|a_{j + 1} - a_{j - 1}|$$$. So we want to find such $$$a_j$$$ that $$$(|a_{j-1} - a_j| + |a_j - a_{j + 1}|) - (|a_{j + 1} - a_{j - 1}|)$$$ is maximum and change it to $$$a_{j-1}$$$.

    That's all.

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

      Why should we bring this number to zero: "We can always choose m=a1 to make first number "0"?

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

        See, nothing, except $$$|m - a_1|$$$ depends on m. As soon as we want to minimize the whole sum, we should make $$$m = a_1$$$. Otherwise $$$|m - a_1|$$$ is going to be bigger than 0, but making $$$m = a_1$$$ will make sum smaller.

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

          And what m should we equate them with, and did I understand correctly that each a[i] = |a[i]-a[i-1]|. That is how to find it m?

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

            No, you get it wrong. We just say that m is first number. We've proved that ansewer is $$$|m-a_1|$$$ + sum of absolute value of difference between $$$a_i$$$ and $$$a_{i+1}$$$ elements. Then, we want to find one number $$$a_j$$$ and make it equal to $$$a_{j-1}$$$ to minimize the whole sum

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

Benefits of hard contests:

1- No long queues. 2- System testing starts and ends in 30 mins. xD

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

C was easy but implementation was bit long i solve in 5 minutes implement in 80 minutes

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

why is B being rejudged?

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

    I think Mike added some more multi-tests and rejudged. Seems that my tests weren't strong enough :(

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

Nice problemset! Hope there will be more problems at the same difficulty as this in the future for the middle-ratings like me. Thanks for your contributions =) very much

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

The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3500.

REAL scoring distribution is 500 — 2000 — 1500 — 2000 — 2500 — 3500.

LOL

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

It seems that AceKing and I were the only people in the whole contest who passed the pretests for C, but TLEd on the main tests :( that's quite a sweet spot we managed to hit with our execution time!

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

    How to find this who all failed systests without exploring the whole ranklist obviously?

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

      filter the submissions

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

      As Forward. says, I clicked status, filtered on problem C, verdict Time Limit Exceeded. The results are displayed in reverse chronological order, so I looked specifically for entries submitted in the time range of the contest, but which got TLE verdict after the end of the contest. There were only 2 of us.

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

        Okay seems fine but I was looking for something which can show me all types of failed sys-tests (WA/TLE/RE etc) on one page. Thanks anyways.

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

        Not 2, there is also me who MLE-ed — you should filter by "rejected" and tests >= 10 (I think this is the number of pretests for C).

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

Today was the first time I needed to fix an MLE from pretests and fail system tests due to MLE :/

https://codeforces.com/contest/1453/submission/100368040

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

Today contest very bad contest. I downvote today contest. Do not make tomorrow contest. I not give contest. djm03178 do not make contest again.

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

B was probably more difficult than usual...

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

I think the 1st standing in div2 did not finish the competition independently for the submission time of his code. If he did, I apologize for this comment.

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

I did a very stupid mistake in B.
For n = 2 answer will be 0 but I don't know what came to my mind, I printed their difference.
Sadly that case wasn't in the pretests.

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

The contest was very good and problem A was easy and standard.

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

when will the rating changes will be published ???

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

Was it div1?>:

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

hic :(( i set the "max" is too small so i failed in test 27 :(( sad

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

Honestly, I'm tired of making small mistakes that cost me the whole round... In my submission, changing this line from
pow[i] = (long) (Math.pow(2, i)+pow[i-1]);
to
pow[i] = ((long) (Math.pow(2, i))+pow[i-1]); solves the overflow issue and gives correct answer.
I can remember more than 5 contests that I made similar small mistakes and it is really annoying because I have the correct solution and I get WA due to a small bug like this. Does this kind of stuff happen to u as well guys? How do you overcome making these mistakes? I know that this is a matter of experience but I already understand that by casting the pow function as long, a whole other function is used that uses long to compute the answer instead of int. Yet in that particular case, I don't think I could have ever realized that this was going to overflow during the contest. Of course, now that it has happened to me, I don't think that I will make the same mistake again, but that's what I thought when I made my last overflow bug and I don't think there is an end to this :p

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

I got Time limit exceeded on test 5 problem C any help? I solve it in O(n*n) MySubmission

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

    Your code actually has time complexity O(n^4). Consider the case where all the elements are similar (let's say zero). For example:

    5
    00000
    00000
    00000
    00000
    00000

    Your code at first creates all the pairs of (i,j) that the array has the value of zero. In this particular case, all the pairs of i and j are added (n^2 pairs). Then you make a double loop over the pairs you created, and thus your overall time complexity is O(n^4) Your code is similar to looping over all pairs of array possitions (i,j),(k,l) which is O(n^4).

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

Здравсвуйте. Мне пришло сообшения где говорится что возможно я действовал вне правил. Мне пришлось писать код изпользуя онлайн компилятор ideone. Компьютер был не моим. Но уверяю вас что все задачи решал я сам без какой либо помощи или подсказок. Вы можете сравнить мои прошлые и коды и заметете в дизайне незначительные изменения кроме таба. Таб в ideone явно не 2. Я не хочу лишится моего аккаунта. Пожалуйста.

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

Why there rating differs ? in this contest div2 #688

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

    The second account is new account. So,1330 wasn't his actual rating though it is shown 1330 and neither 1432 isn't his actual rating now. You can the see this to understand better.

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

    compare nishchay17 and optozorax, nishchay has a lower rating than optozorax and the same score. But optororax has a higher increment. Illuminati confirmed !!

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

After upsolving D, I am realizing that I should read all the problems' statements. D was easier than B and C.

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

    Only if you are a math noob. If you are programmer then B and C are simpler. I needed like 10 minutes for B, had a hard time to get C right, and D was impossible at all.

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

      How did you come up with the idea for B in just 10 minutes? It took me a lot of time to get the idea and the contest finished.

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

        I asked, to which number would I change a fixed a[i] if I could change only that one number? The answer is that I would change it to one of its adjacent numbers. Which is the same as removing it. At that point, the question is how much contributes the removal of each number, which is near to the final answer.

        In D on the other hand, I had simple no idea how to calculate the expected value for a given number of stages at all. It would have been nice if the fact that the expected value to finish one level equals 2 would have been written clearly in statement. Because if one did not read that fact somewhere before, it is hard to come up with it.

        One formular is $$$\frac{1}{2} + 2\cdot \frac{1}{4} + 3\cdot \frac{1}{8} + 4\cdot \frac{1}{16} ...$$$, and we need to see that this sums up to 2.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          In D what I did
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is really a tough contest, and I got stuck in problem C for too long time, but the problems are really interesting and I enjoyed this round very much. Thanks for such a wonderful contest.

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

I cant get more rating contests, so I try the get more contribution, please

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

At first I got irritated with all the math problems in this contest and hence left contest in between (after I wasn't able to crack B for a long time)

But later when I did the post analysis: A, B, C were not that hard, meaning no new algo or any new concept were required to solve those. So this also means that more practice could have made it easier and solvable during contest.

I liked problem E a lot though. Balanced amount of maths, logical thinking and algorithmic skill required for E. Although even after spending so much time understanding and upsolving it, I am still not sure whether I will be able to solve such problems during any contest or not.

Thanks demoralizer for your screencast. https://www.youtube.com/watch?v=AFqmxQzffrU&t=4276s

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

It took us one month to prepare a video solution for problem B :) If it is still interesting to anyone, please consider:

Video link

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

In Problem E doesn't it makes sense for the problem statement to mention that find minimum possible value if the player always chooses the closest next snack optimally (as opposed to arbitrarily)? In the former case, we need to consider the best case and in the later case, we consider the worst possible case.

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

    'Arbitrarily' is not equal to 'randomly'. It means that Badugi can decide whichever snack he wants to eat next. It's also hard to define what is being 'optimal' here, as the statement hasn't explained the goal of the problem yet. Instead, the statement requires you to find the value that makes it 'possible', as opposed to 'always', which means you should consider the best possible case.