ilyakrasnovv's blog

By ilyakrasnovv, 21 month(s) 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. fursuit
  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

| Write comment?
»
21 month(s) 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!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +73 Vote: I do not like it

    After getting $$$998244353$$$ upvotes...

    Spoiler
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    How about we count the upvotes on the post and enlarge this comment also accordingly

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    228

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -23 Vote: I do not like it
    Spoiler:

    Bold text

    Italic text

    inline text

    code:
    #include <stdio.h>
    
    int main()
    {
        printf("SlavicG");
    
        return 0;
    }
    
    

    Username: SlavicG

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    There is no limit if you use a bit of CSS :D

»
21 month(s) ago, # |
  Vote: I like it +69 Vote: I do not like it

Big comment text for upvotes

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    Italic comment text for upvotes

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +96 Vote: I do not like it

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

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 3   Vote: I like it +60 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +26 Vote: I do not like it

            Monospace comment text for upvotes.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            Rev. 3   Vote: I like it +13 Vote: I do not like it
            Spoiler for upvotes:
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Spoiler
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it
                Spoiler
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Spoiler
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Spoiler:
      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) 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.

»
21 month(s) 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!

»
21 month(s) ago, # |
  Vote: I like it +37 Vote: I do not like it

winter Summer Informatics School

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

As a tester, I don't remember tasks.

spoiler
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to become an expert!

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Float like a butterfly, Sting like codeforces.

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Very excited!

»
21 month(s) 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 :)

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Good Luck

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become pupil(lll¬ω¬)

»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

The same but not the same time :(

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there is no exact answer, everything can change

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Hoping not to see grid in problem A.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it
The contest may contain interactive problems!

Hope it doesn't >_<.

»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

Ah, that score distribution is looking dangerous.

»
21 month(s) ago, # |
Rev. 7   Vote: I like it -43 Vote: I do not like it

.

»
21 month(s) ago, # |
  Vote: I like it -19 Vote: I do not like it

Div 1.5

»
21 month(s) ago, # |
  Vote: I like it -20 Vote: I do not like it

C seems tedious

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

»
21 month(s) 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?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

[deleted]

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And why is it always C :(

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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 :)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I used array and if else XD

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Large Gap

to make you get negative rating change.

»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

»
21 month(s) 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.

»
21 month(s) 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!

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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.)

  • »
    »
    21 month(s) 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';
            }
        }
    
  • »
    »
    21 month(s) 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).

    • »
      »
      »
      21 month(s) 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

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Meme
  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the extra 15 minutes!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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).

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another "speedforces" contest

»
21 month(s) 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

  • »
    »
    21 month(s) 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].

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for D?

  • »
    »
    21 month(s) 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]$$$.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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

»
21 month(s) 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?

  • »
    »
    21 month(s) 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...
»
21 month(s) 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

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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)

    • »
      »
      »
      21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it
Spoiler
»
21 month(s) ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

jjj

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) 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...

»
21 month(s) 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..

  • »
    »
    21 month(s) 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

»
21 month(s) 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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

.

»
21 month(s) 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://mirror.codeforces.com/contest/1715/submission/169117875

  • »
    »
    21 month(s) 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)

»
21 month(s) 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 :(

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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...

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve E?

  • »
    »
    21 month(s) 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]$$$

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

when will the editorial for this round be available?

»
21 month(s) 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://mirror.codeforces.com/contest/1715/submission/169148981

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Solved Div2 D for XOR instead of OR :'(

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Code for anyone who did the same
    • »
      »
      »
      21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

the pretests at the last two contests were really terrible

»
21 month(s) 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.

»
21 month(s) 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

»
21 month(s) 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://mirror.codeforces.com/contest/1715/submission/169148352

  • »
    »
    21 month(s) 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~

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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://mirror.codeforces.com/contest/1715/submission/169155228

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I get an increase after rechecking

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Wishing for those +3 points just like you.

»
21 month(s) 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)))))))))))

»
21 month(s) 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?

»
21 month(s) 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

»
21 month(s) 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://mirror.codeforces.com/contest/1715/submission/169136307 and https://mirror.codeforces.com/contest/1715/submission/169166978

»
21 month(s) ago, # |
  Vote: I like it -13 Vote: I do not like it

Problem E is very nice

»
21 month(s) 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
  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Trash contest

»
21 month(s) 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