127.0.0.1's blog

Codeforces Round 907 (Div. 2)
By 127.0.0.1, history, 13 months ago, translation, In English

Hello, Codeforces!

max0000561, a.nasretdinov and I are glad to invite you to our Codeforces Round 907 (Div. 2), which will be held on Oct/30/2023 17:35 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100.

On behalf of our team, I want to thank:

And special thanks to my friends who have made a huge contribution to this round: Amir a.nasretdinov Nasretdinov, Maksim max0000561 Krylykov and Tanya medved Medved. Also thank you for all four years of friendship:)

During the round you will need to solve 6 problems. You will have 2 hours to solve them.

Score distribution: $$$500-750-1000-1500-2000-2250$$$

Good luck and, please, read the statements of all problems!

UPD: Editorial is out.

UPD 2: Congratulations to the winners!

Div. 1:

Div. 2:

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

Comments Comments (136)
| Write comment?
»
13 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Can't believe that mine is the first comment!

→ Reply
»
13 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Wow, So exciting to see this round, I hope it will be interesting.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can reach Specialist.

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

As a tester, the problems are cool and interesting!

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

Point distribution suggests all problems could be solved by average Div-2. But history suggests, Point distributions can be deceiving ... :D

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck and, please, read the statements of all problems!

Is there anything implied in this sentence?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I think they mean you should read all problems

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

      I think you're right.

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

        They mean, there is a chance, that you haven't been able to read through all problems before the match ends.

        → Reply
»
13 months ago, # |
  Vote: I like it +13 Vote: I do not like it

as a friend of the author of the round, I predict that round will be great!

→ Reply
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Message Notification system in telegram is very pleasurable for me . I almost forgot about this contest but telegram notification alerted me timely . Thanks to codeforces management system.

→ Reply
»
13 months ago, # |
  Vote: I like it +161 Vote: I do not like it

Kudos to 74TrAkToR for his decision about placing problem F at Div. 2 F!

He is the only coordinator who will make such creative decision!

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

Are you sure E and F should be in that order?

→ Reply
»
13 months ago, # |
  Vote: I like it +43 Vote: I do not like it

Good luck and, please, read the statements of all problems!

Lol, they knew F was easier than E

→ Reply
»
13 months ago, # |
  Vote: I like it +29 Vote: I do not like it

What was the idea of setting $$$1$$$sec TL in $$$D$$$???

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

    982 ms

    Clutched it

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

      Yes! I really don't understand why you should put a $$$1$$$ second limit, it makes it very hard to pass a python problem or a completely unoptimized $$$O(nlog(n))$$$ solution in $$$C$$$++. It's just an idiotic decision to put such a limit from the author! On the other hand the task is cool.

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

        wait you solved in O(nlogn)?

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

    That is probably because you are expected to precompute something?

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, how to optimize it from q*60*60?

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

    You can do $$$O(q*60)$$$ by storing each consecutive range with the same values, and iterating through this range vector for final computation.

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

      For range [2^f, 2^f-1]. How are you recalculating g without iterating on all powers of f?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 6   Vote: I like it 0 Vote: I do not like it

        I guess you mean $$$[2^f, 2^{f+1}]$$$

        In this range, there can almost be two such disjoint ranges, so I will binary search the point where the function changes.

        Calculating the given function is $$$O(log n)$$$, just simulate finding max power for which $$$base^{y} \leq x$$$.

        Btw I precompute these ranges, so each query is just $$$O(q * number-of-ranges)$$$

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

          there can almost be two such disjoint ranges

          Why?

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

            Gwynbleidd_ answered that ig

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

              He just stated the fact, but did not give explanation for this.

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

                The given function is monotonic in the range because $$$floor(\log_2 x) = f$$$ now

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

                  I had this same logic, but i am getting WA on pretest 8.
                  Do we also need to be careful about bounds?

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

                  I'm not sure, I fixed most problems in my code with the sample cases.

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

    f(x) ranges from 2 to 60 and for each f(x), g(x) is monotonic. Also for each f(x) if you check g(x) can have atmax 2 values. Precompute for all such ranges and answer it. tc: q*70 ig

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

      Yeaa!

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

      For each f(x), g(x) is monotonic. But how can we say that for each f(x), g(x) can have at max 2 values?

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

        What i did was just printed the g(x) value for start and end point for each f(x), i.e. 2^i, 2^(i+1)-1 and it turned out the difference between them is atmax 1. and since it is monotonic u can find the point where it changes using binary search.

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

        $$$x$$$ just almost doubles in this range

        For the function to take more than 2 integral values, we need X to be multiplied by $$$floor(\log_2 x)$$$ which is more than 2

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

        Hello sir . did u unnderstand why atmax only 2 values can be present. if so could u pls expalin sir

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

          Consider the range $$$[2^x, 2^{x+1}-1]$$$.Let y = f(x) >= 2. For some k, $$$y^k$$$ is somewhere between $$$2^x$$$ and $$$2^{x+1}-1$$$. So, $$$y^k \ge 2^x$$$. Then $$$y^{k+1} = y(y^k) \ge y(2^x) \ge 2^{x+1}$$$

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

      At first, I thought g(x) is monotonic on the whole range (not depend on f(x)), which give me wrong answer in the sample test case :((. Sad to be unable to solve D.

      → Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

In my opinion, F is easier than C. I was stuck on C the whole contest, but figured out F 15 mins after seeing it.

Drop CM again :(

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

    Was F using dynamic segment tree?

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

      I used BIT, but I think segment tree works too.

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

        I was thinking euler tour + seg tree. But how to take care of new nodes??

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          Start with the full tree and when a new node is added set it to 0

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

          Build the tree and do euler tour first, then do the operations backwards, that way add nodes become delete nodes.

          There is no need to worry about whether further queries will change the answer of the deleted node.

          → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      Another solution for $$$F$$$ without reversing queries!

      When you add $$$x$$$ to all values in subtree of node $$$i$$$, just add $$$x$$$ to $$$val[i]$$$. The answer for every node $$$j$$$ is the sum of $$$val[k]$$$ such that $$$k$$$ is ancestor of $$$j$$$ (Call this sum as $$$S(j)$$$)

      However, when you add node $$$t$$$ to the tree, then add node $$$t$$$ with $$$val[t]$$$ = $$$-S(t)$$$ in the current state of tree. This will "undo" the contribution of subtree sum addition due to queries performed before addition of node $$$t$$$.

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

        But how can we calculate -S(t) fast before adding node?

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

          Using a fenwick or segment tree. Adding $$$x$$$ to $$$val[i]$$$ means, add $$$x$$$ at $$$tree[tin[i]]$$$ and $$$-x$$$ at $$$tree[tout[i]]$$$. Note that $$$tin[i],tout[i]$$$ represent in-time and out-time of node $$$i$$$ respectively. Query sum of range $$$[1..tin[i]]$$$ to get $$$S(i)$$$.

          → Reply
»
13 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Screencast with commentary

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the great round

→ Reply
»
13 months ago, # |
  Vote: I like it +60 Vote: I do not like it

2^Forces

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

I don't believe that task E can be simpler than F

→ Reply
»
13 months ago, # |
  Vote: I like it +116 Vote: I do not like it

Thanks for the round! I enjoyed the problems, but F is absurdly misplaced. I spent less time on it than on any problem after B, and if it had appeared in position D I would not have thought anything was out of the ordinary; indeed, F had nearly as many solves as problem D did. (I also think F is a bit on the standard end, but it's fine for a Div. 2 only round.)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

FForces

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

read the statements of all problems!

This means you should look at the leaderboard to decide on which problem to work on.

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

What can so many people solve F! i couldn't get any valid ideas.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wow system testing already ??

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the 35th pretest?

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

    For F I presume. It is that every query is adding a node and the graph will have q+1 nodes. This was perhaps missed and caused RTE.

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

good contest

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://ac.nowcoder.com/acm/contest/27836/E?&headNav=acm It and F is simply the same.

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

Thank you for the beautiful round, loved it, although stuck on first problem till the end of time. Need some skills

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D Problem, For 179 1000000000000000000 of sample testcase, I get 41949982 in my system and online IDEs, but I got 773751787 codeforces, What had gone wrong ? where should I look for ? my submission

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

    I think overflow on signed integers is undefined behaviour, so that's why it's giving different results as your overflow check will not be correct. I don't know how to escape the overflow other than to tediously change everything to int_128 or do the code in python(risk of TLE).

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

      Ohh thanks, I submitted in practice, It seems that was the issue, lesson learned :)

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

In F, the pretests were passed, but now I got MLE on test 16. The pretests were more than 16, so shouldn't it be tested in the pretests?

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

Like really bro? F is way too easy for being the last problem of this contest.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't the range of unsigned long long till 2^128-1? In my local, it was overflowing on 2^70 only. Why?

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

    unsigned long long only goes up to 2^64-1

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

    Unsigned long long has a range of 0 to 2^64-1. There is int_128 which goes up to 2^128 but it is much more finnicky to use.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B can be cheesed, bad testcases i guess Link

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

230580209 can anyone try to help me finding bug in solution for D?

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

    Take a look at Ticket 17121 from CF Stress for a counter example.

    To help you debug, the testcase is constructed with $$$L = R = 2^{59}$$$. We have $$$f(2^{59}) = 59$$$, so we need to find the largest non-negative integer $$$z$$$ such that $$$59^z \leq 2^{59}$$$. It's easy to verify that $$$z = 10$$$ but your code produces $$$11$$$.

    → Reply
»
13 months ago, # |
  Vote: I like it +41 Vote: I do not like it

A round where everybody solved F.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B is kind of tricky, should some tricks.

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it
Relevant intervals for D
→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    UPD: solved it

    How is it calculated? I used binary search but got different numbers.

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

      We can check every [2^x, 2^(x+1)). If answers are (between Left and Right corner) different, we can easly find the border. If not, we now understand that all this numbers under one value

      → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      .

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

      Just binary search and check for 9, 1e18 + 100. This will give you the relevant intervals from 9-1e18. For 1-8 you can find them out just by observing.

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

        UPD: solved it

        Thats exactly what I did but got wrong answers. Thank you anyway

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

I guess D is all about implementation

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When do the ratings get updated? Thank you.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May I know why my 230532327 to B is skipped? 127.0.0.1

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Only the last "passed pretest" submission would be run in system test.

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

    it's because when you submit multiple correct solutions of a problem during contest, all the other accepted submissions (except the last one) of that particular porblem automatically get skipped.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My $$$O(Q*64)$$$ solution is doing TLE on test-case 10 https://codeforces.net/contest/1891/submission/230585018

my basic idea is between [2^q, 2^(q+1)], g(k) can only take atmost two possible values and I am combining them. Corner segments are handled separately.

Can I optimise it further or is it just too slow fundamentally, within the constraints I reckon it'd pass all the cases

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    230563485

    Yes, if i have understand you correctly

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

    At first you have ipow function, so it's $$$O(Q \log R * \text{(max ipow exp)})$$$. And you have too much $$$\% modm$$$, and time limit is too tough.

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

    I think ur problem is correct but the result of ipow(lq,z+1) can overflow long long and became a negative number.

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

What is the deal with pretest 8 problem D? For 63 5153632, my code gives 20673255 whereas the answer is 20673256. I can't figure out how I'm missing the extra 1! Any ideas?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    after we add 2^x to a number it will never be divisible by any 2^y where y>=x. Using this fact we can remove all unnecessary elements from array q after which it's length will be at most 30 and we can bruteforce it

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

      How like, if we take 4 and we add 2^1 to it multiple time, it may become 16, then it will divisible by 2^2

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

        to add 2^1 the number must be divisible by 2^2. After you add 2^1 once it won't be divisible by 2^2 any more so you cannot add 2^1 again.

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

Problems were really good!!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

When will the editorial be? Or maybe I'm missing something? Thanks

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why approach for F with euler tour + lazy prop is giving tle on tc 22. code- https://codeforces.net/contest/1891/submission/230589277

any help will be appreciated..

→ Reply
»
13 months ago, # |
  Vote: I like it +22 Vote: I do not like it

conragts to Gwynbleidd_ for finally reaching CM ( ME )

→ Reply
»
13 months ago, # |
  Vote: I like it +30 Vote: I do not like it

just wanted to see how this new color looks in comments

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

230598813

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, is it okay to check long long overflow using long double? I mean this :-

long double val = a;
val *= b;
bool overflow = val > LLONG_MAX;

Does anyone have experience with this? Even if it is not precise, can you get away with it during contests?

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

    I mean one scenario where this might come handy would be say you want to calculate log(1e18, 60) using a for loop. You loop through 1 to 10 and it's all <= 1e18 so you would want to check for 11, but that is where it overflows. But the above trick works here ig.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +125 Vote: I do not like it

I don't think that ETO is an individual participant. The submissions from that account is suspicious.

Its code style in Problem A and Problem B matched. However, a new default source came up in Problem C and Problem D with different reading and multi-test handling method. The last two submissions are even more confusing.

Among these submissions, we can learn 4 ways to solve a multi-test problem, 3 ways to read a integer from stdin, 3 ways to set a constant value, which is shocking. It's easy to see that there are >1 members(possibly 4: AB+CD+E+F) so they should be unrated.

I believe I can beat the whole team if this contest is rated for me(they are too slow) but it's unfair to all Div.2 participants. plz unrated this account.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many people solved F but only a few solved E?

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

    Cause F is a problem that has appeared in Nowcoder Monthly Contest before.

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

    Because it is not only too classical but also too easy.

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

Thanks，I reach master！！！I've waited a long time for this day

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!I reach Candidate Master!

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

very nice contest! And I solve all problems!

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

Thanks a lot... I got my new best rating..

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got the logic for D but implementation is tough.

→ Reply