ilyakrasnovv's blog

By ilyakrasnovv, 6 weeks ago, translation, In English

Thanks a lot!

for Your participation

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #816 (Div. 2), which will be held on Aug/20/2022 17:35 (Moscow time). The round will be rated only for the second division. You will have 6 tasks and 2 hours to solve them. We recommend you read all the problems.

Round is completely set by winter SIS (Summer Informatics School) students. During the camp we did our best to prepare interesting and creative problems. You can check previous rounds prepared by SIS students: Codeforces Round #815 (Div. 2), Codeforces Round #694, Codeforces Round #612, Codeforces Round #530

We are very thankful to

Scoring distribution will be released before the contest begins

We hope that You will participate in our round, as well as in SIS!

Good luck and have fun!

UPD — Scoring distribution:

$$$500 - 1000 - 1750 - 2250 - 2750 - 3000$$$

The contest may contain interactive problems! Make sure to read this post.

UPD 2 — Editorial is out!

UPD 3 — Congratulations to the winners!

Official participants:

  1. william556
  2. infurnity
  3. huge_waxberry
  4. lbwhangbeateveryone
  5. Longiseta

All participants:

  1. jiangly
  2. kotatsugame
  3. hitonanode
  4. ksun48
  5. Rubikun
 
 
 
 
  • Vote: I like it
  • +703
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 6   Vote: I like it +330 Vote: I do not like it

UPD: Large text has reached its limit! Good luck on the round!

178 upvotes on this comment and the larger large text becomes even larger!

57 upvotes on this comment and the large text becomes even larger!

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

Big comment text for upvotes

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

    Italic comment text for upvotes

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

      ᵗᶦⁿʸ ᶜᵒᵐᵐᵉⁿᵗ ᵗᵉˣᵗ ᶠᵒʳ ᵘᵖᵛᵒᵗᵉˢ

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

        Русскоязычный текст комментария для лайков

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

          sǝʇoʌdn ɹoⅎ ʇxǝʇ ʇuǝɯɯoɔ pǝddᴉʅᖵ

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

            Monospace comment text for upvotes.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 3   Vote: I like it +13 Vote: I do not like it
            Spoiler for upvotes:
            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Spoiler
              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it
                Spoiler
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Spoiler
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Spoiler:
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Spoiler
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it -13 Vote: I do not like it

        hidden comment text for upvotes

        UPD 1 : there was simple instead of hidden before. UPD 2 : there was not before written on the upper line.

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

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

    Emoji (and other unusual UTF-8 characters) are not supported comment for upvote

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

As a (supposed) tester, I don't even remember testing this round but it should be good.

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

Same setters for this as well as the previous round, nice!

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

winter Summer Informatics School

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

As a tester, I don't remember tasks.

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

Finally, a round where I can gain rating again.

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

Hope to become an expert!

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

Well, it got my attention. The round better live up to your hype now, that's all I've got to say.

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

Float like a butterfly, Sting like codeforces.

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

as a student, I would like to learn from this Codeforces Round #816 (Div. 2) contest

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

Waitin

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

Very excited!

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

All these Contests back to back, as coders we are just loving it :)

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

thanks for contest !!!!!!!!!

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

Good Luck

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

Hope to become pupil(lll¬ω¬)

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

as a participant i will participate

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

I finally found SomethingNew that I have zer0brain, now I KAN participate in this contest :)

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

go go go

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

Thanks, SIS! The last contest was awesome. Probably there will be math and binary search or implementation problems again. Good luck everyone!

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

As a student, I will try my best to solve the problems.

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

(* ^ ω ^) comment ʕ ᵔᴥᵔ ʔ with (▽◕ ᴥ ◕▽) cute ❤❤❤ emoticons ❤ (ɔˆз(ˆ⌣ˆc) for (ノ◕ヮ◕)ノ*:・゚✧ upvotes (◕‿◕)

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

The same but not the same time :(

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

Just a random question but if anyone knows about it please reply. Here is the question:

I may not be able to participate in today's contest but i saw in the calendar that the next contest is going to be held on the 2nd of September. Do you know if any contests are taking place before that date? If not i might have to cancel everything and participate.

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

    very low or no chance that there will be any contest before 2 sept and after todays contest.

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

    there is no exact answer, everything can change

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

Hoping not to see grid in problem A.

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

I hope the problem statements are short, crisp and clear.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it
The contest may contain interactive problems!

Hope it doesn't >_<.

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

Ah, that score distribution is looking dangerous.

»
5 weeks ago, # |
Rev. 7   Vote: I like it -43 Vote: I do not like it

.

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Div 1.5

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

牛哇牛哇 (So EXECELLENT the writers are!)

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

C seems tedious

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

    not much, but i struggled for an hour on what i think was some overflow (WA on pretest 2). At the end i just put ll everywhere and it passed the pretests

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

    get better

»
5 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

It's hard for me to imagine what the author's mindset was when he wanted to put that hard tasks to 2C, only to make this LARGE GAP?

I know! The large text stands for the large gap, right?

Conclusion: gapforces, speedforces.

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

I couldn't see the problems for the past 15 minutes. It keeps saying "Bad Gateway 505". Anyone else?

»
5 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

speedforces

»
5 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

I feel that Problem b is more advanced than usual !! (•_•)
Speedforces!

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

[deleted]

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

    so sad, but true

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

    And why is it always C :(

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

    Not sure it's that big gap I solved C it doesn't need any data structures but it wasn't easy for sure

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

      I've heard that sb. used Treap / Splay Tree in C. Initially my solution have used Old Driver Tree but I gave up debugging it. so maybe a lot of people used some too complicated data structures :)

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

        I used array and if else XD

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

    The C of this round is nowhere as hard as the C of edu round 133

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

Nice round!No mutitestcases! C is a little difficult,but interesting!

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

Large Gap

to make you get negative rating change.

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

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

I TLEd on 2 different problems using Java and passed in C++. Not sure if it has something to do with my implementation, but I never encountered this on CF before.
I liked the problems though.

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

So sad, that i solved C too late. Could've solved 20 minutes faster, if i would've not been wasting time on E. At least now it's my bad. Thanks for contests, SIS! Was glad to participate in all of them! Hope to see more contests of yours!

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

regardless the round being unbalanced and speedforces and not being able to solve c, i see that c is an opportunity to introduce low rated people to new topics ( if i have the right idea). ps : after the round finished do we need lazy propagation in this problem?

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

Can somebody explain C? For me it is much harder than D

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

    Let's say, you know the result for the initial array. Try to find how changing one value will affect the result.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      ok, its easy to observe that, but how do you store data? do we need to have length of every block stored?

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

        No, you don't have to store the length of every block.

        If you are updating index i, then ans will only change depending on its adjacent indexes (i-1 and i+1).

        My Submisson: 169128778

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

        You don't need to store anything. Once you find the awesomeness of the initial array, it is straightforward to calculate the change in the awesomeness if one value is changed. You only have to keep track of the current awesomeness and the array itself.

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

      Is this about writing $$$998244353$$$ if statements or is there a clean way to do it?

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

      I tried, but couldn't come up with something fast

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

    Though it took me a lot of time to solve this, general idea for any such problem is, we want to know, if there is something with a[i-1],a[i] and a[i],a[i+1], when we do an update on index i.

    You can check that our summation for a given array of size n = (n*(n+1))/2 + sum of (n-1-x)*(x+1), where 0<=x<n-1 and a[x]!=a[x+1].

    Now, it is easy to refer to 169149222

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

    Individual contribution of each index to the whole. So, if all numbers are distinct, then each index contributes (i + 1) * (n — i) to the total sum.

    When you modify a number, check if it is equal to the left or right index. If it is, then subtract its individual contribution from the sum. If it was equal but now different, then add its individual contribution to the sum.

    The exact individual contribution formula is weird and just takes a lot of time to find. (Ex. it's different if it's the same as the left neighbour vs the right neighbour, different for the first element, middle elements, and the last elements etc.)

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

    I tried writing an explanation but I found I was unable to explain it clearly. Nonetheless I have left the explanation in case it helps.

    First, how to calculate answer overall? Calculating prefix of blocks is simple, and all subarray s contianing the first element must sum all these. Then just iterate from left to right and if you find a new block, subtract (length remaining — 1), otherwise subtract -1. Answer is sum of all this.

    To be clear: suppose you have 1 2 2 3 2 4 block_prefix = 1 2 2 3 4 5 answer for v[0] = 5 + 4 + 3 + 2 + 2 + 1 = 17 answer for v[1] = 17 — 5 (remaining numbers) — 1 = 11 answer for v[2] = 10 (since it's the same block, we only remove 1 from the answer) // and so on

    final answer is sum of all these.

    So now we know how to find the initial answer in O(n). How would it help us find the answer?

    After a query: we have 4 cases

    either this element begins a block on the left or begins a block on the right or breaks a block on the left or breaks a block on the right

    If it begins a block on the left, we subtract 1 from all the elements to our left. If it begins a block on the right, we subtract a 1 from all the elements to our left including us. We just reverse this if it breaks a block.

    for(int d=0;d<m;d++) {
                int i,x;
                cin>>i>>x;
                --i;
                int l = n &mdash; i;
                if(v[i] != x) {
                    // Case 1: We are breaking a block on the left hand side
                    if(i != 0 && v[i] == v[i-1]) {
                        s += (l*i);
                    }
                    // Case 2: We are breaking a block also on the right hand side
                    if(i != n-1 && v[i+1] == v[i]) {
                        s += (l-1)*(i+1);
                    }
                    // Case 3: We are creating a block on the left hand side
                    if(i != 0 && x == v[i-1]) {
                        s -= (l*i);
                    }
                    // Case 4: We are creating a block also on the right hand side
                    if(i != n-1 && v[i+1] == x) {
                        s -= (l-1)*(i+1);
                    }
                }
                v[i] = x;
                cout<<s<<'\n';
            }
        }
    
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    You just need to understand how often subarray of length 2 appear in array.

    For exmp:

    1 2 3 4 5

    Currently ans = 35. Lets say we want to change 3rd (pos = 3) element (1-indexed) to 2, so it became this:

    1 2 2 4 5

    Now we consider 2 things:

    was a[pos] equal a[pos + 1] before and if it is equal now. If it was equal and now it isn't, we just need to decrease ans by how many times does this subarray appears. In this exmp it appears 6 times: {2, 2}, {2, 2, 4}, {2, 2, 4, 5}, {1, 2, 2}, {1, 2, 2, 4}, {1, 2, 2, 4, 5}. So, now ans = ans — 6, so it is equal to 29. Else we increase ans by this number.

    was a[pos — 1] equal to a[pos] before and if it is equal now. (Do the same as this 1st case).

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

      Thank you very much! I realized my main mistake was thinking and writing some long and difficult formula. But now I see the solution was quite clear

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

    Try to think of a way to calculate the contribution of each index in O(1) time. Any number affects only the numbers just after and before it. Then the problem is simple. Whenever any number is changed, subtract the contributions of the 3 numbers(before, after and itself). Then add the new contributions after a number is changed.

    As far as calculating contribution, think of it this way — All numbers in a block except one are useless.

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

    First calculate maximum answer (i.e when all elements are distinct)

    Let B[i] = arr[i] == arr[i+1] with length n-1. Then subtract from maximum answer the sum of all subarrays of B (which can be done in O(n)). Answering queries can be done by extending the idea of sum of all subarrays: update can only change 2 values of B and it's easy to recalculate new sum of B.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Meme
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Assuming we have an array $$$pref$$$ where $$$pref[i]$$$ is the number of elements with indices $$$k\leq i$$$ where $$$arr[k]\neq arr[k-1]$$$. For a given $$$[L, R]$$$ segment, its awesomeness $$$=pref[r]-pref[l]+1$$$. Hence, the answer is $$$\dfrac{N*(N+1)}{2}$$$ + $$$\sum_{i=1}^{n}{\sum_{j=i}^{n}{pref[j]-pref[i]}}$$$ $$$=$$$ $$$\dfrac{N*(N+1)}{2}$$$ $$$+$$$ $$$1*pref[1]+2*pref[2]+...+n*pref[n]$$$ $$$-n*pref[1]-(n-1)*pref[2]-...-1*pref[n]$$$.

    So, whenever $$$arr[i]$$$ changes, it can can add $$$\pm 1$$$ to $$$pref[i]$$$, $$$pref[i+1]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i]$$$ and $$$arr[i-1]$$$ changes) and can add $$$\pm 1$$$ to $$$pref[i+1]$$$, $$$pref[i+2]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i+1]$$$ and $$$arr[i]$$$ changes.

    The effect of adding or subtracting $$$1$$$ to all prefix values in some suffix corresponds to adding or subtracting arithmetic sums to the answer, e.g, if we add $$$1$$$ to all the prefix values in the suffix starting at $$$k$$$, this corresponds to setting $$$ans$$$ to $$$ans+\sum_{i=k}^{n}{i}-\sum_{i=1}^{n-k+1}{i}$$$.

    Hence, we can process each query and modify our answer accordingly as needed then print the modified answer.

    Submission

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

    The initial answer is easy with DP. Then for every update at position i, you consider all segments including i, you check how their contribution change. To make life easier, you can classify segments into 3 types: 1. ends at i 2. starts from i 3. i is neither end nor start. That's the basic idea.

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

Thanks for the extra 15 minutes!

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

    I can see you solved C, can you please explain your approach !

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

      I guess there are already good explanations in other comments, but to come up with the idea, you should notice that even without any query, since n<=10^5, you already need around O(n)/O(nlogn) approach to find the initial beauty. Once you figure out the formula to calculate beauty in O(n) it's easier for you to handle queries in O(1).

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

Did anyone solve D with Python? I got TLE on pretest 4 :(

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

Yet another "speedforces" contest

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

can someone point out what's wrong with my submission for div 2 C?

spent basically the entire contest failing to figure out my mistake

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

    x will be compared with arr[i-1] and arr[i+1] and not arr[i].

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    	for (int i = 0; i < n; i++) {
    

    You know, subs += (n - i) * i; overflows because i is int.

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

      is it the (n - i) * i expression overflowing? because subs is already a 64 bit integer

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

        C++ evaluates (n - i) * i as int because all variables are int, and then adds result to subs. It doesn't care about context of expression

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

          thanks for your ans

          ORZ

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

          ty, it passed now.. just mad that all i had to do was change an int to an ll......

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

bet many have made silly mistake in problem B

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

Any hint for D?

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

    You can $$$and$$$ all the $$$x$$$ values of the triplets $$$l, r, x$$$ with $$$l = i$$$ or $$$r = i$$$ to find out which bits can/can't be placed at $$$a[i]$$$.

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

    First consider the case of $$$i = j$$$ in a statement.

    Then find all bit positions that MUST be 0. Then find all bit positions that MUST be 1. After this, you can greedily construct the lexicographically least array by deciding on the bits that are still unknown.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Denote $$$unset[i]$$$ as the mask representing bits that must be unset in $$$arr[i]$$$, this can be known from the unset bits in $$$x$$$ values which are the result of an $$$OR$$$ operation with $$$arr[i]$$$.

    So we can calculate first the array $$$unset$$$ and then iterate on the queries. For the $$$qi^{th}$$$ query, for every bit set in $$$x$$$ and must be unset in one of $$$arr[i]$$$ and $$$arr[j]$$$, then we are sure we must set it in the other element. This has to be done before any further processing to ensure no extra unneeded bits are set somewhere.

    What is remaining is those $$$x$$$ values where some set bits in them can be set in either $$$arr[i]$$$ or $$$arr[j]$$$. Assuming $$$j\geq i$$$, let's sort first the queries in ascending order of $$$j$$$, then process the queries in that order, and whenever we find a set bit in $$$x$$$ that is still unset in $$$i$$$ and $$$j$$$, set it in $$$j$$$.

    The reason for that latest sorting done on queries is to handle the case when we have queries $$${i, j, x_1}$$$ and $$${j, k, x_2}$$$, where $$$i<j<k$$$ and the $$$k^{th}$$$ bit is set in $$$x_1$$$ and $$$x_2$$$. So, it is sufficient here to set the $$$k^{th}$$$ bit only in $$$j$$$.

    Submission

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

    If i-th bit of x is 0, then i-th bit of a[l] and a[r] must be 0. After that consider all queries where l = 1 (1-indexing). If i-th bit of x is 1 and i-th bit of a[r] must be 0, then we have to set 1 at i-th bit of a[1]. After considering all queries where l = 1 we can do it one more time, but now if i-th bit of x is 1 and i-th bit of a[1] is also 1, then we don't have to set 1 at i-th bit of a[r]. Now we do the same for all 2 <= l <= n

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

Any Hints for Problem F? Can we solve the 1-d version (farm's top-right corner being (100,1)) in 3 steps?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    If my solution passes system tests, then...
    In fact
    A way to begin
    Continued...
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh nice! Yeah got it for 2-d too in 2 queries, 1 for getting the y (dividing into 100 such triangles...more or like zig-zag trapeziums) and next query for the row y, y+1...beautiful

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

How do you update values of blocks optimally for each query? This got me stuck hard on C

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

    You don't need to — the length of the blocks is immaterial, the only thing you care about is if a block is created or not.

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

    i don't know if there is an easier solution but either u use segment tree with lazy propagation or using BIT ( binary indexed tree)

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

      I thought about both, not familiar with lazy version of segTree, but couldn't get a grip on any of the two.

      But I agree with the above comment, I knew there was some kind of calculation possible to pretty much calculate everything after each query. Couldn't find it either, lol

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

        i was thinking the same as u in the contest i get an idea for a possible solution but get stuck at range updating and imn't familier with this topic even when i searched for templates for range update query couldn't use it xD

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it
Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How could I get TLE in task C if I only have five "for i in range(n)" (no nested loop)? :(

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

jjj

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve G?

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

Can anyone give me a counterexample for my submission for B?

I thought it covered all kinds of special cases but it gets stuck at pretest 2.

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

Speedforces and this is me on B; -100 delta incoming

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

Why would you put 1.5sec for D, just why... You made such a good problem and then you screw it with a shit TL...

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

When you get "WA on #4" on C in the last 5 minutes

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

Me who used multiset of structures to solve C and understanding the intended solution now..

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

    i used segment tree and i got a "beautiful" wrong answer which is really annoying

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

This round is neither bitforces nor mathforces, i like it !, Codeforces should have more rounds like this

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

    stfu, not everyone is lucky enough to do good in this trash type of contest.

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

.

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

    Agree. Very standard and bad problem C. Which cause me fail to solve E in time.

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

Can someone please explain what's wrong with my code for B?
https://codeforces.com/contest/1715/submission/169117875

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

    u can also give k-1 to a1,i.e. a1 can be at max k*b+(k-1)

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

Could Anyone Explain How to Solve Problem B I am Struggling in it :(

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

    The minimum $$$s$$$ is if $$$bk$$$ if each $$$a_i$$$ is divisible by $$$k$$$. There is no way to decrease $$$s$$$ because reducing any value of $$$a_i$$$ will reduce the overall beauty.

    On the other hand, if $$$a_i$$$ is divisible by $$$k$$$, then you can increase $$$a_i$$$ by up to $$$k - 1$$$ without changing the result of the floor division, i.e., beauty contribution remains the same. Therefore, the maximum $$$s$$$ is $$$bk + k (n - 1)$$$.

    So we can start by putting $$$bk$$$ in the first (or last) element to secure the beauty of $$$b$$$. If we still haven't reached our target of $$$s$$$, we can add up to $$$k - 1$$$ in each element (including the first/last!) to reach our target of $$$s$$$ without altering the beauty.

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

    One idea is to build an array with correct beauty, in example by setting a[0] to b*k.

    Most likely then the sum of a[] is smaller than s. But we can see that we can up to k-1 to each element in a[] without changing the beauty. So we update elements in a until the sum of the elements conforms to s.

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

I'm so glad I NOPE'd at C so fast and moved straight to D, which I felt was much easier than C.

Even after I returned to C (after solving D), I couldn't even figure out how to compute the initial awesomeness value for C in sub-quadratic time...

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

    Was D some graph theory problem or what? For me it was harder, than C

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

      Not so much graph involved, just some basic knowledge of connected components imo

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

      Nah, you just need to think about how bitwise OR constrains the values and then greedily construct the array.

      If $$$i = j$$$ for a statement, then $$$a_i$$$ is exactly equal to the result.

      Each statement is essentially 30 statements, each involving the OR of two bits.

      For bits $$$p$$$ and $$$q$$$, the statement $$$p \mid q = 0$$$ means $$$p = q = 0$$$. So now we only need to worry about statements where the result is 1.

      For bit $$$p$$$, the statement $$$p \mid 0 = 1$$$ means $$$p = 1$$$. After this, all that's left are $$$p \mid q = 1$$$ statements where neither $$$p$$$ nor $$$q$$$ are fixed.

      Now we can greedily construct the lexicographically least result: start with $$$a_1$$$, clear all of its uncertain bits to $$$0$$$, and check all $$$p \mid q = 1$$$ statements that involve an $$$a_1$$$ bit, setting the other bit to $$$1$$$. Repeat for $$$a_2$$$, and so on.

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

How to solve E?

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

    Relevant Problem

    Suppose $$$distance[i][v]$$$ gives the minimum distance of node $$$v$$$ from node $$$1$$$ on using atmost $$$i$$$ flights.

    Do standard dijkstra to find $$$distance[0][v]$$$

    Now repeat this process for $$$i(1 \leq i \leq k)$$$

    Suppose you use some flight. So find $$$distance[i][v]$$$ on using values of $$$distance[i-1]$$$ (use Convex Hull trick)

    Transition state is $$$distance[i][v] = minimum(distance[i-1][u]+u^2 - 2 \cdot u \cdot v) + v^2(1 \leq u \leq n)$$$

    Do standard dijkstra to update $$$distance[i][v]$$$

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

      How to calculate minimum(distance[i−1][u]+u^2−2⋅u⋅v) quickly?

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

        You can use CHT to do that. Kind of similar to this.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 4   Vote: I like it +20 Vote: I do not like it

        you can also use divide and conquer :D, which i think is more approachable than cht(i dont know how to do cht).

        Lets say you already have the minimum distances to all nodes if you use $$$f$$$ flights. I'm gonna denote the distance to node $$$a$$$ from source vertex $$$1$$$ if you use $$$f$$$ flights as $$$dist_{a,f}$$$. If you find the answer for some node $$$v$$$, which can obviously done in linear time by brute forcing all possible flights to $$$v$$$, you can find the optimal $$$u$$$ to minimize $$$dist_{u,f}+(v-u)^2$$$. Notice that, for any $$$x$$$ where $$$x<v$$$, you don't have to consider any flights where the node you travel from has a greater index than $$$u$$$.

        Let's say there exists a node $$$t$$$ where $$$dist_{t,f}+(x-t)^2$$$ < $$$dist_{u,f}+(x-u)^2$$$ and $$$t>u$$$. Note that disproving this statement suffices for a proof, since we will check all $$$t$$$ where $$$t \leq u$$$ anyways. If the inequality from before is true, then it will contradict the statement $$$dist_{u,f}+(v-u)^2 < dist_{t,f}+(v-t)^2$$$, since $$$(x-t)^2-(v-t)^2 > (x-u)^2-(v-u)^2$$$, since $$$t>u$$$ and $$$x<v$$$. Because we know that $$$dist_{u,f}+(v-u)^2 < dist_{t,f}+(v-t)^2$$$ is true from bruteforcing $$$u$$$, $$$dist_{t,f}+(x-t)^2$$$ < $$$dist_{u,f}+(x-u)^2$$$ simply can't be true.

        The same thing can probably be applied to the case where $$$x>v$$$, too. In that case, we don't need to check any $$$t$$$ where $$$t<u$$$.

        Now how is this information helpful? This leads to the divide and conquer solution; in the first stage we can pick the middle element from $$$1 \dots n$$$ and figure out the answer for that middle element. Then, we can split the range into $$$1 \dots mid-1$$$ where we only have to check $$$1 \dots v$$$, as well as $$$mid+1 \dots r$$$ where we only need to check nodes $$$v \dots n$$$ to travel from. Because the depth of recursion doesnt exceed $$$\log n$$$, and because each $$$v$$$ will only be checked in one branch of the recursion, this results in $$$O(n \log n)$$$ time complexity.

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

when will the editorial for this round be available?

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

Can anyone pass problem C in python? My solution is in O(n) time complexity, yet TLE on problem C.

https://codeforces.com/contest/1715/submission/169148981

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    import sys
    input = lambda: sys.stdin.readline().strip()
    

    try to add these two lines before your codes and submit again

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

How to solve question c

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

Solved Div2 D for XOR instead of OR :'(

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Code for anyone who did the same
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Code for OR. Turns out it is way easier than the XOR counterpart. Its always XOR. Why Codeforces OR now? :‑|

      Code for Div2 D
»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

the pretests at the last two contests were really terrible

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

in problem F, I submited this code and got Wrong Answer during the contest. So I submit another code after that. But the first code should be AC because of the wrong checker.

It makes me lose scores by resubmission. I hope my score could be be back :-( don't skip my code and give me the correct score, thx.

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

I hate pretests
On your contests
They're very bad
It's really sad

XD

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

Can someone tell on which test case my solution for Problem B is failing. https://codeforces.com/contest/1715/submission/169148352

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

    For example:

    2 2 2 6

    the answer should be 3 3

    but not 1 1 4

    (if it is wrong, just ignore it~

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

I apologize that there were technical issues during the round today. Ratings updated preliminarily. We will remove cheaters and update the ratings again soon.

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

    Thanks for your work. btw, some people submit problem F again during contest because of technical issues of checker. I suggest recalculate their scores if it is possible, thanks again.

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

hey guys, can someone please tell me what was wrong with my C submition? https://codeforces.com/contest/1715/submission/169155228

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

Hope I get an increase after rechecking

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

    Wishing for those +3 points just like you.

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I do not pass F on protests, although I solved it on testing)))))))))))

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

Hello MikeMirzayanov,

When CF was down in the midway, I submitted the exactly same solution twice (submission1 and submission2). One from codeforces.com and second from m1.codeforces.com as I was not able to see status. I still got first submission skipped and penalty for resubmission. Can you please look into it?

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

okay got it

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

thanks for the amazing problems in this and previous round, definetly would like to see more contests like this

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

Can someone explain me why these 2 solutions have 2 different verdicts :thinking:? https://codeforces.com/contest/1715/submission/169136307 and https://codeforces.com/contest/1715/submission/169166978

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Problem E is very nice

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

Really don't like this round, for :

Task A
Task C
Task D
Task E
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Very agree.E is the worst problem, it does not have any thinking content but only needs boring algorithms.

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

      I don't agree with "boring algorithms", cht/lichao tree are quite interesting as a concept

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

    I think that task was fit for div. 2, but maybe not for div. 1, since it's quite standard and a lot of div. 1 users would solve it without much thinking.

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

      Well but this trick is too high level for div2 contestants. And also everything besides this trick is quite standard

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

The system tests for problem D are too weak. Please retest it.

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

C time constraints are too tight for python :/ my linear solution TLE'd during the contest but a C++ translation worked

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

How do you create a grid in a note at problem A? Thank you.

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

Trash contest

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

Anyone just now got the email notification for this?

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

I feel sorry for whomever had to write the interactor for problem F