zltzlt's blog

By zltzlt, history, 4 weeks ago, In English

Hello, Codeforces!

We are glad to invite you to participate in Codeforces Round 949 (Div. 2), which will start on May/31/2024 13:05 (Moscow time). Note the unusual start time of the round. You will be given 6 problems and 2 hours to solve them.

This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.

The problems were authored and prepared by sinsop90, yinhee and me.

I would like to thank:

Scoring distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$.

Good luck & Have fun!

UPD: Congratulations to the winners!

Div 2:

  1. cyb0101
  2. Feduk_Pro_Spb
  3. whale_0086
  4. graphcity
  5. grass8cos

Div. 1 + Div. 2:

  1. maspy
  2. Savior-of-Cross
  3. Rubikun
  4. femboy-wannabe
  5. turmax

Editorial and also Simplified Chinese Editorial are out.

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

»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

As a tester, there are some beautiful ideas in the tasks, and I encourage everyone to participate!

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell me how people are selected for testing ?

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for this contest, most of the testers are the authors' classmates or friends, and some of the others are well-known competitors in China as well.

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it
Silly Question which I can't resist to ask:
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Usually the reason is either that the contest is based on an olympiad or some other contest, so to avoid leaking problems the codeforces contest is set in an unusual time. The other reason is simply that this is the best time that fits the authors due to time zone difference or other reasons

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

      Yes, thanks for your understanding. Actually there is a conflict between this round and ours studying plan (we are from the same school). At the same time zltzlt and I are preparing for the Zhongkao, one of the most important exams in our life, so hope participants can understand us.

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

        Good luck on your exams!

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

        I've heard that Zhongkao is very prestigious, just as Gaokao is. I wish you the best of luck, and I hope that you perform really well.

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

        Good luck & high mark in Zhongkao!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        To my knowledge, both of you are good enough in competition and can be Baosong(enter without exam) to a very good high school. You don't need to do Zhongkao.

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

          Actually due to the policy, we are still required to get at least 680/810 in the exam, and the school ask as to get a score of 730+. It's not that easy, is it?

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

        Can we stop saying "Zhongkao" and actually speak some English? This is really a bit embarrasing /qd

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

          Zhongkao is shorter than 'ahrghaghrah entrance exam' and everyone knows what it means so it's not an issue

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

      Thanks!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OKay. Thanks a lot for quenching my Curiosity.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How exactly would an unusual round time prevent leaking problems?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's for mirror rounds, rounds that replicate an actual on-site contest.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As far as I know, it is because Guangdong provincial team training. The author of this round is a member of Guangdong provincial team.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay Thanks a lot for replying. May I ask, How long does the training lasts and how do Chinese coders train?

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

It will be my first contest in Codeforces, and I am looking forward to it!

»
4 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

As a first-time tester and one of the writers, I'm certain that you will have a good experience in this round and learn a lot. Just enjoy yourself:)

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

As a tester, hope you can enjoy the problems and get a positive rating $$$\Delta$$$!

Meanwhile, good luck to the authors who are about to attend an important examination -- Zhongkao!

»
4 weeks ago, # |
  Vote: I like it +71 Vote: I do not like it

As a tester, I like the problem set and hope you enjoy it too!

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Still waiting for the Educational Round blog

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Codeforces Round 949! One step closer to the milestone Round 950! <3

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

please change the time of the contest it is in the time of the pray in Egypt and we want to participate

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please delegate it one more hour, Many muslim guys in the middle east won't be able to join because of the prayer of jumaa.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

HOPE IN THIS ROUND I'D REACH MY GOAL BEFORE SUMMER BEGUN

GL FOR EVERY PERSON,WHO READING THIS COMMENT

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

As a Chinese CPer, I'm happy with the start time.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

As a tester, I would like to say that the problems are wonderful!

»
4 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

As a tester, I'm zltzlt fan.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

looking forward to give this round as a cyan :)

»
4 weeks ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

As a writer, I am a fan of zltzlt.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a tester, I am a fan of zltzlt. Good luck in Zhongkao!

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope the competition topic is more interesting!

»
4 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Usually the reason is either that the contest is based on an olympiad or some other contest, so to avoid leaking problems the codeforces contest is set in an unusual time. The other reason is simply that this is the best time that fits the authors due to time zone difference or other reasons

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

As a tester, I think this round will be educational and fun.

I think all the problems are great.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG Finally 18:05 round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

will be good contest

»
3 weeks ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

It would be great if you can delay it by 1 hour, as many middle east contestants will miss it due to a weekly prayer at that time.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Arithmetic Progression in scoring distribution!!!

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

    No because $$$3500-2500\ne2500-2000$$$ :)

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

      Ohhoo, I missed the last one. But, suiitable for the first five. Thank you.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Giving the round to compensate the loss in educational

»
3 weeks ago, # |
  Vote: I like it +120 Vote: I do not like it

Fun fact: the setter has solved 4000+ problems on codeforces and 10k+ problems on a Chinese online judge(which provide the remote judge service of codeforces and atcoder). I'm so shocked by his hard work.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm curious, how long did he take for the 10k milestone locally? Heck, this is making my 2.5k in ~2 years fall obsolete by a long shot, such a dedication.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If I don't solve A B and C then it's gg

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

    Update: I couldn't even do B its over for me

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

As a PST kid, I somehow managed to wake up for it :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish positive delta in this round!

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Will queue issues appear in contest because of EDU 166 system testing?

»
3 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Will there be delays due to an overlap with yesterday's Educational round's System Testing?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish ABC!

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

orz zltzlt

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

Tough contest.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

This didn't seem like a Div. 2.

»
3 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

It was more like Div. 1.5

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Any smart solution for C? Feels like another boring implementation task that I can't care less debugging. Took a huge L today.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your intuition and solution ?

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

        If there are no set values, just do 1 2 repeated.

        If there is some value set then the prefix can be obtained from the first value by halfing. If you get to 1 you double because you cannot half. The suffix is similar.

        Now to complete middle parts. Say we are bounded by $$$a$$$ and $$$b$$$. If $$$a > b$$$ then we must half $$$a$$$ in order to get closer to $$$b$$$. If we don't then $$$a$$$ was half of its right neighbour, but that only increases the distance to $$$b$$$ and we still will have to half at some point. We reduced the problem to a smaller instance (from $$$\frac a 2$$$ to $$$b$$$ and one less element). Similarly you can do the same if $$$b > a$$$. There is one issue, if both $$$a$$$ and $$$b$$$ are 1, then this does not work but you can just insert a 2 instead.

        In the end you want to check the original problem constraints (you did not get an invalid array). This can be computed as you complete the array.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

What the fuck of the C???????????

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

    I used more than an hour to write the code(182 lines) for C,but still didn't AC

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    isn't that simply find n sequence {a1,a2,...,an} start from x to y where a0 = x, a_{n+1} = y, a[i] = a[i + 1] / 2 or a[i] = a[i — 1] / 2?

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

      yeah, very easy to get the idea, but it just brabra casework and very hard to debug.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        not needed that much of case handling. assume the array has this form: [-1, -1, ..., x, -1, -1, -1, ..., y, -1, -1, ...]

        The prefix and suffix are kinda the same, start by doing x/2 until you reach 1 then do 2 1 2 1 2 1, In the middle part, start x/2 and y/2 from left and right, divide the bigger one in half each time, once you reach the other side just double check the OKity

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I literally missed a case in C and threw like 30 minutes finding the cause of the WA, leaving 5 minutes for D which I figured out a few minutes after the round ended ._.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I feel like I code a large number of droppings :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do prob B ?????

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

    Go through the bits of n, let's say you're at bit x, if the bit is a 0 then check if m >= 2^x — (the number represented by the binary expression before bit x) or if x is not greater than the most significant bit of n then you can also check if m >= (the number represented by the binary expression before bit x).

    263459449

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As the operation spreads for every second, at time $$$t=m$$$, the value at $$$a_i$$$ will be $$$a_i = a_{i-m}|a_{i-m+1}|...|a_{i+m}$$$.
    The above is exactly the bit-wise OR in the range $$$[max(0,n-m), n+m)]$$$.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

loved problem B.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how you did?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, just notice by writing the operation a couple of times let say 20 and 3 are values of n and m then in the first operation value will be (19|20|21) and in the second operation the value will be (18|19|20)|(19|20|21)|(20|21|22) --> which is nothing but or of [18,22], so if u write more such iteration u can conclude that the answer is OR of range(max(0,n-m),n+m).

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I reached uptil this that answer will be bitwise OR from range(max(0,n-m),n+m) but was not able to implement it, was this an easy implementation? because if it was an easy one i would work on my bitwise section

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Or am i missing something? does just doing output OR of range(max(0,n-m),n+m) will not give the answer

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It will give the correct answer, but not always in the time limit. To actually solve this problem you need to consider every bit individually and try to greedily find a number that has this bit set and lies in the range [max(0,n-m),n+m].

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can check out my submission. I also did the same observation as shviv1.

      Here is my submission

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Pure math + wrong difficulty estimation from coordinators. Typical Codeforces.

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

the authors cooked

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

C is not a C. D is not a D.

I think CDEF should be DEFG, and insert an easier C.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate it when a math problem (problem D) appears in my interesting interval

(the problem is nothing wrong tho, just I'm too skill issued)

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem B seemed tougher as compared to normal div2B problem ...

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Tough contest. We weren't given enough time.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong in this? 263494295. If someone can provide a testcase, it would be very helpful.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Brother, only the time was not unusual; To me, problem 'B' was also unusual, aaand the whole contest was unusual too!!!

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

my method for C

assume L is somewhere a[i]!=-1 ,R is next one that a[i]!=-1

then when a[L]>a[R] we can make a[L+1]=a[L]/2

when a[L]<=a[R] we can make a[R-1]=a[R]/2

if a[L]==a[R]==1 we can make a[L+1]=2

my english is so bad so dont critisize me

this is my code and i know it is ugly

https://codeforces.net/contest/1981/submission/263485331

»
3 weeks ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

Stucked on C for $$$45$$$ minutes and finally got 1 place lower than sevlll777, who solved 1 problem less than me. The slowest episode ever.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

agony

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can give me C's solution?

I did it for 1h30mins,but i have no ideas.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do 3 ops when moving from $$$i$$$ to $$$i+1$$$, namely divide by 2 (and floor), or multiply by 2, or multiply by 2 and add 1. It is easy to see that in enough steps, any number can be achieved with these operations. You compute the minimum operations, and if the distance is less than that, or the distance minus the minimum operations is odd, then it's impossible. The implementation is a bit tricky though...

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for you comment. in the competition,i thought of this trick but i dont know how to calc the minnium distance lol.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me find error in my solution for problem B ? It's failing on pretest 7. https://codeforces.net/contest/1981/submission/263482380

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

I'm officially having skill issue with constructive problems (again) :D

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to F

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

a B-like A a C-like B a D-like C and a C-like D Bruh...

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I actually enjoyed solving problem C a lot. but aren't the rounds a little too hard? there was literally only one full solve which came from a person probably above div.2 level. still, cool problems

»
3 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

It wasn't fun at all

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Will the rating changes of this round be calculated on the ratings before the EDU or on the updated ratings of the EDU?

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Adhoc dominates codeforces nowadays a lot.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve A? I know it must be easy, but I couldn't come up with a solution.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    p=2 works and hence, the largest power of 2 <= r is the answer

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops! That was easy! I somehow made it in my mind to be much more complicated. Thank you!

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Abnormal contest with CNOI-style problems.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C did give me a lesson...

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In contest i tried second question for 1 hour and 54 minutes still not able to solve it :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

not only not enough time but the problems were harder than usual div 2 problems

»
3 weeks ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it

I love the $$$O(\frac{n^2}{\ln n})$$$ solution of problem F, however I spent my whole time in $$$O(n\log n)$$$ overcomplicated segment tree merging solution and mixed indices like tr[x<<1](should be tr[tr[x].ls]) then finally finished 10 minutes after the contest...

edit: I got the first blood!! so funny XD

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate the idea?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Basically we have $$$x\not\in A\Rightarrow\text{mex}(A)\le x$$$. Then we can apply DP: $$$f_{x,y}$$$ is the minimum cost in subtree $$$x$$$ such that $$$y$$$ doesn't appear in the top path, then segtree merging.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had similar thought, but wouldn't it be N^2 though

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you can check the different between my two submissions. In the first RE one I use array $$$g$$$ to maintain, and it was replaced by segment tree in the second one.

»
3 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I think it will be more balanced to insert a *1500 problem between B and C.

Difficulty prediction (luogu): Orange Yellow Green Blue Blue (Black)

Difficulty prediction (Codeforces): 900 1400 1700 2200 2400 (3200)

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

After the Educational round I thought, "I am going to get a healthy positive delta". The rating is not updated yet. But after this unusual 949 round I am scared of being Pupil again!!!

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Wait. maspy FSTed on problem F???

A 0-solve D2F??

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

got RE on test case 2 of problem c and got accepted after contest. if just had 1 minute more whould get ac

Spoiler
»
3 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

a very nice D!! Thanks for the contest.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

how can calculate rate and educational rate not calculated yet??

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

But I really didn't have fun ...

I think it is too hard for a Div.2 contest.

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

Hi, can someone tell me where my submission for B is going wrong?

https://codeforces.net/contest/1981/submission/263488201

I converted the decimal numbers (n-1) and (n+m) to binary, and then traversed (from MSB to LSB) and compared their bits. Where ever they differ, that means from that bit onwards all the bits will be 1

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Am I the only one who felt A is tough than usual div 2 rounds

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

    wdym it's literally int l, r; cin >> l >> r; cout << (int)log2(r) << endl;

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got that idea after some time but initially I some how thought that we have to calculate the x in between l and r with maximum factors.I have to carefully read the question next time

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

      small code does not generally mean the problem is easy.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Het can you tell me why this method leads to wrong answer sometimes as i got in this question Atcoder Question

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        #include <bits/stdc++.h>
        
        using namespace std;
        
        int main() {
          int h;
          cin >> h;
          
          cout << 1 + (int)log2(h+1) << endl;  
        }
        

        This code resulted in AC

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

CornerCaseForces

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

BitForces

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Carrot is not working :( Any other working performance calculator extensions?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sometimes Codeforces close the API during contests due to the heavy load, it doesn't work because it can't get the data to 'predict',

    give it some time and it'll be working fine.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It might be Cloudflare's protection mechanic instead of Codeforces'. I can see an error message containing 403 and !DOCTYPE html followed by some are you a human webpage content

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

Chineseforces

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

It might be better to swap the D and E.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope someday I will be congratulated like this.

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

There are 10 types of people: 1. Those who like bit manipulation. 2. Those who don’t like it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the approach of C

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

    We can make the problem simpler ...

    => Given a and b in 'a -1 -1 -1 ...(k times) b', is it possible to fill the -1s with numbers >=1 and <=1e8 such that adjacent elements follow either A[i+1] = A[i]/2 or A[i] = A[i+1]/2 ?

    Let's approach to solve it from both ends (now, from the left). Say A[i] = a and A[j] = b, so A[i+1] can be a/2 on division side (call it OP1) or 2a or 2a+1 on multiplication side (call it OP2). So we store the number of such operations in respective maps for both OP1 and OP2 till j-i number of operations.

    Similarly, from the right-hand side. Since the hops between a and b are j-i for any common number x on map_OP1 or map_OP2, we have (say) t = map_OP1_left[x] + map_OP1_right[x] as the total number of hops. If (j-i) and t have different parity, it is not possible for such x to be a convergence point (obvious), so if they have the same parity and t > (j-i), one could just make x from a and b and fill between even hops by *2 and /2 alternatively. You can fill '-1 -1 -1 ... a' and 'b ... -1 -1 -1' ones similarly.

    That's the approach and here's my submission 263482841.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings get updated any idea ??

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Author cooked

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

a contest where no one completes all the questions But it is useful

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why my following approach for the problem B fails:

My Approach
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I cant tell what but you were trying to do something like this 263477911

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your approach is 100% correct, and this is my AC submission which is the same tbh 263460829

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Finding the smallest number greater than 'n' whose ith bit is set is easier. But can you please explain the approach to find the greatest number smaller than 'n' whose ith bit is set, because the number may or may not exist?

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

        So we traverse from i+1th bit towards MSB, and the moment we find a 1, say at bit j, unset bit j and set all bits from j-1 till 0, call this number x. That is the closest number on its left with the ith bit set, and this is the nearest because as you increase from x, you won't get the ith bit set in any number till n.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got the error in my code. orz

          I was setting the bits from (i-1) to 0 instead of (j-1) to 0, where j is the first bit set while moving towards MSB from (i+1).

          Here's the clutter created by me :)
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice idea,I never thought that instead I used pattern of bits at specific position

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, this was a really fun math contest!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Basic idea of D was almost exactly same as https://codeforces.net/problemset/problem/367/C just had to account for self loops and print the path

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but I didn't notice the problem before.

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

      It was a nice problem anyways I remembered the problem because it was first time I used things taught in my discrete math class(complete graphs, eulerian path ) ,that too in a problem which seemed unrelated to graphs and you took it a step further by making it feel like a number theory problem

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

666

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why unrated participant came first, shouldn't untrusted participants not be allowed

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

after solving a problem of this contest i used to be able to add tags and remove them but now it says no tag edit access is it because i dropped 8 points below CM or its the contest ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! Check out my video solutions for the contest. I've covered Problem A-C from contest here.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Love D, but too simple for div2 round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one tell me why my code is so slow? Submission: https://codeforces.net/contest/1981/submission/263742703

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

A probably high rated programmer type7shady, probably CM level has been livestreaming and leaking answers online, solutions upto C were leaked.

Here is the livestream for this round: https://www.youtube.com/watch?v=Px7R7j0uOtQ

Drive Link where all code is uploaded: https://drive.google.com/drive/folders/1T4jvLvOJwWq6R23xJjENJb4AgOHJjPmC

This person also leaked ABCD in the last edu contest, good enough to place cheaters at the high expert — early CM level. zltzlt and MikeMirzayanov please look into this.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • here are proofs of copied codes from telegram by anish.naruto
    • Proof
    • This account has skipped solutions in 4 different contests , and its +1 now , this account should be banned.
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi newbie isJaipal, I think you are new to Codeforces . The main crux of code i.e the logical part can be same for a numerous of people, implementation is what makes your code original, this includes of data structures you used and in what way you used that, of course algorithm may be same for many. Don't worry, You will learn it with time and practice. Also, the past plag I got in this account is because I used to use GPT for implementation in early days when I started cf, who used to give similar implementation to multiple users , but later , I stopped using that too and practiced a lot on my own to improve implementation ability.

      Thanks for the concern tho, I am myself very much against cheating even in academics like college exams or any online competitions , I hope this answers your query, All the best

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

        so how were you able to think and wrote these long codes in just 5-10 min , are you a grandmaster or some ? And that too very similar to ones available on telegram

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did not write them in 5-10 mins, I was trying E,F after B but I could not debug F1 first, so did C,D then did debugging for F1.That is why, there is a time gap between B and C. Also, you can use copilot in vs code for faster typing, which even many CMs use.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope you definitely cheated. Look at last contest’s E for example. You and a lot of other cheaters have nearly identical code. For example, you don’t meed to separately consider the case for n==m, but all cheaters have done so. Similarly, no need to find the transpose,you can just iterate rowwise and columnwise. Codes cannot coincide almost line by line for such implementation heavy problems.

        Dont deny it, otherwise I will look into all of your submissions and prove that you cheated line by line, which will be more embarrassing for you.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This wouldn't be deemed cheating since problem E was previously featured on GeeksforGeeks as an article, and contestants are permitted to utilize pre-existing online resources. Consequently, it's not uncommon for multiple individuals to have similar code for problem E due to this allowance.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope, This round will be enjoyable.

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

for problem D, in the examples, i think for the last test case, p=5 is possibly a correct solution but the online judge says its wrong