300iq's blog

Invitation to Good Bye 2021: 2022 is NEAR
By 300iq, 2 years ago, In English

Hello Codeforces!

We have a pleasure to invite you to Good Bye 2021, which will take place on Dec/29/2021 18:35 (Moscow time). You will have 2 hours to solve the problems. The round will be rated for participants of both divisions.

The problems for this round were prepared by 300iq, with the help of excellent coordinators KAN and 74TrAkToR.

We would like to thank all the testers, who made this round possible: gamegame, thenymphsofdelphi, ko_osaga, golions, Ashishgup, izban, prabowo, 74TrAkToR, Devil, manish.17, taran_1407, minhcool, AlFlen, Utkarsh.25dec, NemanjaSo2005, wxhtzdy, ajit, mnaeraxr, Scrubpai, YashDwivedi, eatmore!

And of course, MikeMirzayanov for great platforms Codeforces and Polygon.

This round is supported by NEAR, a company founded by former competitor AlexSkidanov. NEAR is built by many prominent competitive programmers, including twice ICPC champion eatmore and GCJ and TCO winner Egor.

The participants who end up in the first 255 positions will receive prizes. The participant on the first place will receive Ⓝ128, the next two participants will receive Ⓝ64, the next four participants will receive Ⓝ32, etc.

NEAR is a modern blockchain protocol and a development platform. NEAR applications have digital assets as a first class concept, and are hosted in a way that anyone can ascertain the correctness of their execution. This allows building applications that by design provide users with ownership over their assets, data and the power of governance.

If you want to try building on top of NEAR, join Metabuild, a hackathon running until February with $1M in prizes: https://metabuild.devpost.com/

We hope you will enjoy the problem set! Good luck!

Congratulations the winners!

  1. tourist
  2. ecnerwala
  3. ksun48
  4. Radewoosh
  5. Benq

UPD: Editorial

Announcement of Good Bye 2021: 2022 is NEAR
  • Vote: I like it
  • +625
  • Vote: I do not like it

Comments Comments (205)
| Write comment?
»
2 years ago, # |
  Vote: I like it +55 Vote: I do not like it

woah 300iq is back

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +80 Vote: I do not like it

    How many Problems appears on the content???? and What there Score distribution?

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

      ++

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      sekrit

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

      To make the contest more realistic, looks like they have decided to keep the score distribution, number of problems and list of testers in suspense, just like 2021 itself (or are they giving an trailer of 2022?)

      → Reply
»
2 years ago, # |
  Vote: I like it +64 Vote: I do not like it

What is Ⓝ...?

→ Reply
»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

As I tester I can confirm that round has some interesting problems. I hope that you will enjoy them and the last round of 2021 (I think).

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +81 Vote: I do not like it

N64

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I noticed that the hackathon is open to "Individuals who are at least the age of majority where they reside as of the time of entry." Does this mean that individuals who are minors cannot participate?

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

    I suspect this is due to legal issues with awarding prizes. If you can find someone who's over the legal age of majority in your country to claim the prizes (shall you win some hackathon track) you should be good to go.

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

      Hm. I don't want to break any rules. Just to clarify, I can participate if someone else who is a legal adult claims the prize for me?

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

        I think that should be fine. Fancy seeing someone from Redmond here.

        → Reply
»
2 years ago, # |
  Vote: I like it -83 Vote: I do not like it

Is it rated?

→ Reply
»
2 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Why only 2h :(

→ Reply
»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

omg 300iq orz

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best present.

→ Reply
»
2 years ago, # |
  Vote: I like it +442 Vote: I do not like it

We would like to thank all the testers, who made this round possible. They will be added to this blog later.

Translation: testing will commence soon.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Unusual time alert missing!!!

→ Reply
»
2 years ago, # |
  Vote: I like it -25 Vote: I do not like it

What if NEAR bankrupts ? Are the winners going to win money ?

→ Reply
»
2 years ago, # |
  Vote: I like it +62 Vote: I do not like it

How many problems will be there in this round? 300iq

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

Happy new year ~ ovo

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

Such as a great year for me! Best of luck for everyone.

happy coding :)

→ Reply
»
2 years ago, # |
  Vote: I like it +247 Vote: I do not like it

Me during contests

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

3 contest in 3 days.For me its overwhelming !!

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

How many problems? and Why only 2 hours, Good Bye 2020 and Good Bye 2019 was 3 hours!

→ Reply
»
2 years ago, # |
  Vote: I like it +111 Vote: I do not like it

i heard Ⓝ1 worth about $13.5, so the total prize is Ⓝ1024 ~ $13800

that's a really big amout of money(to me)... i cannot imagine

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Good Bye 2020
edit : why so many downvotes , i just pasted the link of last year's contest to help people searching , wanting to solve it

→ Reply
»
2 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Weren't you guys making some kind of CP solving AI? What's up with this switch to blockchain?

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

All the best everyone :) Hope I reach pupil in this contest ! Wish me best of luck

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

How many problems will be there? 300iq

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

Last One

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Can we know how many problem there will be yet?

→ Reply
»
2 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I wish my rate became 2021 but I'm still living in 10th century

→ Reply
»
2 years ago, # |
  Vote: I like it +48 Vote: I do not like it

score distribution pls, i really wanna do some useless analytics five minutes before contest

→ Reply
»
2 years ago, # |
  Vote: I like it +142 Vote: I do not like it

Score distribution and problem count to be posted after the contest. Should add a new strategic element.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    Bold of you to assume there are problems and a score distribution

    → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Is this round only for those who don't care about the number of problems and their score distribution?

→ Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The suspense to the score distribution is as much as the suspense as to how 2022 will turn out to be.

→ Reply
»
2 years ago, # |
  Vote: I like it +49 Vote: I do not like it

I have seen many Oops! today. Maybe it's good to participate from the mirrors:
m1 m2 m3

→ Reply
»
2 years ago, # |
  Vote: I like it -104 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

→ Reply
»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Looking forward to receiving 1 Near coin! Might be able to afford a lunch.

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

WA3 in problem C is a nightmare

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

2022 ? yesterday was 2019:"

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

i feel d is easier than b and c :/

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    How to solve D?

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

      How to solve C ?

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

        How to solve B?

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

        For the array to be good, it's sufficient that the sequence is in Arithmetic progression. So try to fix two elements and check how many elements we should change in order for the sequence to be in AP.

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

      If there exists any bad $$$r$$$ for a given $$$l$$$, there will always exist some bad $$$r$$$ that is at most $$$l + 2$$$ (or at least $$$l + 9$$$ since I didn't have the guts to submit with $$$l + 2$$$). As for how you prove this I have no clue, I couldn't generate a counter-case so I submitted lol (inb4 pretests are weak and I FST).

      The intuition mostly arises from any two adjacent values $$$\lt x$$$ being bad. If that isn't the case then they must alternate between $$$\lt x$$$ and $$$\geq x$$$, so if the whole range satisfies some prefix satisfies or something like that, I tried generating a two really small ends case but couldn't come up with anything that took more than $$$3$$$ so I just guessed it at that point.

      Now you have a number of ranges of the form $$$[l, r]$$$ that must be covered with at least one point, so just use the standard idea — sort them by $$$r$$$, skip them if $$$l \geq \text {last removed}$$$, otherwise remove it and set $$$\text {last removed} = r$$$ (last removable point to make as many ranges as possible skippable).

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Ohh pretty cool. If for any $$$l$$$, bad $$$r$$$ <= $$$l + 2$$$, then this can be solved using simple dp as we don't have to consider a lot of cases.

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

          DP isn't even necesary if that fact holds actually. If you can identify all such ranges, it becomes a problem of choosing the minimum number of points that cover all ranges. This can be solved by processing the ranges in increasing order of their right points and greedily removing a point only when we reach the end of an uncovered range.

          → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        The proof is that every sequence can be split into chunks of 2 and 3, and the overall mean is a weighted average of these chunks.

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

        If there exists any bad r for a given l, there will always exist some bad r that is at most l+2 (or at least l+9 since I didn't have the guts to submit with l+2).

        I was able to solve this problem without the above observationl(actually, I was not able to come up with this idea at first lol). Observe that sum of a segment $$$[l,r]$$$ is negative iff $$$pfx[r] - x \times r< pfx[l-1] - x \times (l-1)$$$. Therefore, for every $$$j$$$ we need to find the largest $$$i(< j - 1)$$$ such that $$$arr[j] < arr[i]$$$, where $$$arr[k] = pfx[k] - x*k$$$. This can be done by modifying the standard method to find the nearest smallest element in the array $$$arr$$$.

        Submission : 141149652
        But this solution is an overkill if you have got the above observation.

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

      Subtract $$$x$$$ from everything, now it's asking for segments such that every subsegment has a non-negative sum. You can find it by checking the leftmost $$$l$$$ such that $$$[l,i]$$$ has a non-negative sum and then doing a simple DP.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        woah :o that's a great solution. from submissions, I see most people got this idea. don't know if that's a standard observation for such problems.

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

        What a simple solution!

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

        For the segment mentioned [l...i], In the dp phase, we will either choose the whole segment or leave it correct?

        If we choose it how can we say it has all valid subsegments ([l...i-1] , [l+1....i-1]...)?

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

          For the segment mentioned [l...i], In the dp phase, we will either choose the whole segment or leave it correct?

          Yes, that's correct.

          If we choose it how can we say it has all valid subsegments ([l...i-1] , [l+1....i-1]...)?

          You can keep track of this with $$$l[i] = max(l[i],l[i-1])$$$. You can see my submission for more clarity.

          → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Greedy,

      an important observation i found is if all subarrays in triplet $$$(a1,a2,a3)$$$ satisfies the given condition, if $$$(a3,a4)$$$ satisfies the condition then $$$(a1,a2,a3,a4)$$$ will also satisfy the condition.

      so maintain a variable $$$last$$$ which holds the last unselected index(initially $$$last=0$$$)

      so start from $$$i=2$$$ and first check for subarray $$$[i-1,i]$$$ ,then $$$[i-2,i-1,i](if possible) $$$,if it doesnt satisfy the condition , unselect i ,and repeat this process.

      sorry for my bad english.

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

      Initially we have:

      a(l)+a(l+1)+…+a(r)≥x⋅(r−l+1) -> a(l)+a(l+1)+…+a(r) — x⋅(r−l+1)≥0

      We can reagente to (a(l)-x)+(a(l+1)-x)+…+(a(r)-x)≥0, so we can do a[i]-= x and only care if a(l)+a(l+1)+…+a(r)≥0.

      Now we can use prefix sum to write this as ps[r] -ps[l-1]≥0

      The idea now is for each i, you will not select i if some ps[r] — ps[j] < 0, with (the last index not selected) < j < r-1

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

Solution of Problem C on StackOverFlow

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

    Jeez should have searched for this. Thanks though for the link!

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

      We just need to change our array into some AP. That's what I searched xD.

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

        Lol. I did the same things xD. My idea was Sn of AP = n/2.(a0+al) and its 1/2*(a0+al).(r-l+1) and somehow I have to convert the array into AP and I googled it xD and got this.

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

    Did the same exact thing. Unfortunately WA on tc 3 :(

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

Can someone link the recent opencup problem that was H but instead of counting maximize the size of the set? I forgot which opencup it was.

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

How to solve E?

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

    The resulting string s will be a prefix of t with the first character difference after less than the corresponding character in that position in t. We can just iterate this and use a segtree or something to maintain the minimum number of operations needed to transform to that prefix. Time is $$$O(n * 26 * logN)$$$.

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

    if there is any transformation of s in mimimum moves such that new string is smaller than t

    then that s will be converted to below transformation —

    (t[0]+t[1]+...+t[i-1]+c+X)

    where c < t[i]

    and X contains remaining characters of s.

    Iteratively, we can find moves required to transform s into all of the strings of above type and return minimum of all.

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

Solved only one problem, I want to die

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    you should convert array into arithmetic progression and for this it's sufficient to iterate over all possible $$$i, j$$$, fix this 2, find current $$$d$$$ ($$$d = (arr[j] - arr[i]) / (j - i)$$$) and make arithmetic progression with this $$$d$$$, then for each generated array find the one with minimum difference with old array

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

      it results in O(n^2) can we optimise it??

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

        maybe there exists more optimal solution, but this is also pretty fine to get AC(because of input size)

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

      why we need to convert the array into arithmetic progression? what is the intuition behind it? how you come to the conclusion that making AP is the key idea to solve this problem?

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

        The Sum of an AP is n/2.(a1+an) and in this question we were asked that a1+a2+a3+....+an = 1/2.(a1+an).(r-l+1) . Now r-l+1 is the number of terms i.e. n . So we can say that a1,a2,a3...,an are in AP and their sum is 1/2.(a1+an).(r-l+1).

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

        the reason is quite simple:

        every subsegment must be arithmetic progression(because this formula is correct only for AP-s), which definitely means -> whole array must be AP(because the array itself is the subsegment of it). Then, if the array is AP, indeed, every subsegment is also an AP, so this condition is necessary and enough too :)

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

    I thought of C as fitting a line. Each pair of points can form a line x being their index and y being array value. You need to find the line which has the most points lying on the line. The points which are not on the line is the answer.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I dont think simple fit would help. Since we need equality, we may need AP.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried finding the largest size of subsequence that is an AP sequence for C(then subtracting from N to get ans) but its TLE. Can anyone explain their solution?

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

    Fix any two elements of the array and get the common difference of the AP according to those two "fixed" elements. Now adjust all other elements accordingly. Among all n(n-1)/2 cases, the one requiring minimum alterations corresponds to the required answer.

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

      after fixing the 2 numbers how did u check.

      did u had everything in double datatype?

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

        You can also rewrite the equation and write the condition with integers.

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

          could you please elaborate this.

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

            For example in the submission that exulansis linked he checks the following condition: v[k]!=a+d*(k-i).

            You can replace d there and you get v[k]!=a+(b-a)/(j-i)*(k-i) and if you multiply both sides by (j-i) you get v[k]*(j-i) != a*(j-i) + (b-a)*(k-i) which are all integers.

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

              Nice. This is better. You don't require to worry about floating point error

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

    Just realised my stupidity. This is in fact a viable solution. But i was not doing what i described here. Lol, so I came up with the solution while trying to ask for help.

    UPD: The one I proposed here is actually wrong and the one I was doing in-contest is right but is way too slow.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      This is actually not a correct solution. I got stuck on this approach, but here is a counterexample:

      2 1 6 8

      The answer is 1, but doing what you described gives 2.

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

WA on B was the most irritating

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

I haven't proven it yet, but for problem E was it enough to try to find the nearest character in s equal to the current one we are evaluating (iterating through the target string t)? To update the answer, then we just find a smaller character instead. The idea would be to do this with Segment tree / BIT,

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

Was not able to do the kindergarten math of C :/

And noticed after contest that it is also doable with doubles instead of fractions which is even simpler.

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

due to lags in the last 10 seconds, I didn't have time to send problem H (let's see if it works later...)

upd. no :)

→ Reply
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Did anyone else think there were some server issues during the contest? It took me around 30 minutes to just get to read the problem statement of B, not even the lightweight sites were loading for me. Wanted to see if this was a server issue or a local one, because other sites were loading...

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

    Same for me. Codeforces only worked for me in the last ~30 mins and even the lightweight websites were taking too much time to load. I was using a different internet connection today, I thought it's because of that.

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

    Its Working properly In my Case

    → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Today, i literally understood the meaning of laxicographically smaller.

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

Happy new year everyone <3

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

In whole contest the codeforces not worked properly,uneccesrily buffering . : (

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

One thing you should learn:

  • For every div.1+2, H is easier than F
→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any one felt server is slow?While contest

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

    Exactly! Even the lightweight sites were refusing to load, I thought it was a local issue, but others were having problems too, and other sites were loading fine

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      It is taking 30-40 seconds to reload the standings and submissions :( .

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea behind B?

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

    You just had to take the longest nonincreasing prefix of the string and mirror it.

    The only corner case is when the first two characters of the string are equal, in this case just take the first character and mirror it, as all possible generated strings are guaranteed to be lexicographically bigger that it.

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

      This problem B derailed my contest. Seeing the number of successful submissions made by the others, I had a feeling that I was just missing something obvious. In the end I got some sort of an overcomplicated mix of greedy and DP (keep increasing 'k' as long as the new string becomes lexicographically smaller than the previous one and use DP for doing fast amortized O(1) comparisons of these strings). Unfortunately I was just a few seconds too late to submit it during the contest time and got interrupted by the "end of contest" banner. Okay, no luck getting back to blue in 2021, but hopefully 2022 will be better.

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

Short statements, really interesting problems, and good distribution. Thanks, 300iq!!

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

Are you aware that a problem very similar to H (max clique instead of number of all cliques) was on an OpenCup on 5th December ;d?

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

    Well, unfortunately I was not aware :(

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

    It is also kinda funny considering the fact that I've created this problem two years ago. In the 300iq Contest 2 there was a version with $$$\geq$$$ instead of $$$\leq$$$, because I couldn't solve $$$\leq$$$ back then :)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain me this

code actual

141111062 this is my submission

when i run the code in custom invocation (top right bar on codeforces) the execution time is 3478
while if i just comment the if condition

like this

the execution time is just 452
why????

in case someone is intereted in test case
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any idea for E ???

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

    Greedy. Iterate through the string $$$t$$$. For each position, we either find the closest character in $$$s$$$ that is strictly smaller than the current one we are evaluating on $$$t$$$, or we just find the closest equal character and move on. The number of swaps required to properly position each character we pick is $$$pos + sum(pos + 1, n) - i$$$, where $$$pos$$$ is the position of the character in $$$s$$$, $$$i$$$ is the current index of $$$t$$$ and $$$sum(pos + 1, n)$$$ is the number of characters previously taken that are on the right of $$$pos$$$. Code : https://codeforces.com/contest/1616/submission/141130793

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Haha, I just bruteforced my way through C and prayed that it will pass =) 141117223

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain how we can tackle E? I read the comments above but still have no idea

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D solvable using segment tree?

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

    It is I believe. Everule solved it using segment trees (141109186) in contest though I don't know what it does as I cannot comprehend how his brain works.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 5   Vote: I like it +21 Vote: I do not like it

      First we subtract $$$x$$$ from all elements, and now we need all subarrays of more than one element to have non-negative sum.

      I calculate the minimum $$$lim_i$$$ such that $$$[i \ldots lim_i]$$$ is an invalid range. For that let $$$p_k$$$ be the sum of the first $$$k$$$ elements. Notice that $$$p_i \le p_{i+2} \le p_{i+4}$$$ for the range $$$[i \ldots i+4]$$$ to be valid, so the value of $$$p_i$$$ becomes irrelevant after a certain range, in which case the maximum range is the same as for $$$i + 1$$$. If it becomes invalid earlier, then you can do quick brute force on small subarray.

      Then I just iterate over where the next removed element is, as element $$$i$$$ being closed means that there is some element before $$$lim_{i+1}$$$ that is closed, and we take the minimum dp value among those. You could also probably do $$$O(n)$$$ for this but I didn't think that much.

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

    I solved it using segment tree. First of all, we need to ignore an element from a subarray $$$[l, r]$$$ only if $$$ps(r) - x \cdot r \lt ps(l - 1) - x \cdot(l - 1)$$$. I call such subarrays "invalid subarrays". Note that $$$ps(x)$$$ here means prefix sum upto index $$$x$$$ ($$$1$$$-indexed).

    Say $$$F(i) = ps(i) - x \cdot i$$$. First, I precompute all $$$F(i)$$$ and store it in an array $$$V$$$. Now for any invalid subarray to end at index $$$r$$$, we need atleast 1 $$$l$$$ such that $$$F(l - 1) \gt F(r)$$$.

    We maintain a segment tree where index $$$i$$$ stores the largest $$$l$$$ such that $$$V_i$$$ is the largest value $$$\lt F(l - 1)$$$.

    In this way, while iterating over the array and updating and querying the segment tree, we can find out for every invalid subarray ending at index $$$r$$$, the largest starting point $$$l$$$.

    Once we have all $$$r$$$ and corresponding $$$l$$$ values, we can greedily choose what indices to not pick so that we have to (not pick) the minimum amount of elements.

    → Reply
»
2 years ago, # |
  Vote: I like it +113 Vote: I do not like it

Stupid problem F. A $$$\mathcal O(m^{3.5})$$$ solution is so obvious that I think there will be testcases to let it TLE. but everyone's naive Gaussian elimination implementation passed F in 31ms.

It's like, a simple tripartite graph with $$$9 + 9 + 9$$$ vertices and $$$3 \cdot 9 \cdot 9$$$ edges, and $$$9^3 = 729$$$ triangles, can let my solution spend 280ms in naively eliminating the linear system. But you didn't put any of similar graphs into the testcases.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I didn't dare to write it for a long time, worrying about TLE..

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

    I doubt that there is no big tests in the testcases. I think that this particular solution is just very fast. You can try to hack all these solutions if you think you know how to

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +65 Vote: I do not like it

      There was no big test in the systests. I was able to uphack a few of the AC solutions for TLE -- for example: https://codeforces.com/contest/1616/hacks/779744

      It's true though that the constant factor on this solution is very fast. However I don't see any reason that this problem needed to have 10 tests at a time and only 1 second for the time limit.

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

        You can work mod 3 with bitsets, maybe they wanted to cut solutions that didn't use them?

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +59 Vote: I do not like it

      Unfortunatly due to the relatively small constant of Gaussian elimination, even my naive implementation passed it in 850ms (141133870). (with absolute no pruning, I just used traditional Gaussian elim. but not the Gauss–Jordan elim., so there’s smaller constant)

      I tried the tripartite graph of $$$[9, 9, 9]$$$, and the complete graph $$$K_{23}$$$ but both cannot let the implementation TLE. (actually an observation is that, any $$$K_5$$$ must be monochrome, my first code used this fact to reduce the constant)

      It seems that 300iq intended to let these naive solutions to pass. But I think the simple observation of “ $$$1 + 2 + 3 \equiv k + k + k \equiv 0 \pmod{3}$$$ ” is not worth an F in a combined round.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Exactly, when I read problem F for 2 minutes before solving E, I immediately got that solution and thought "Lol get back to E, I am under-estimating this" because of only 30-40 solves.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    You can actually get way more triangles, around $$$1771 = \binom{23}{3}$$$ with a clique of size $$$23$$$.

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

      The reason of why I didn’t use $$$K_{23}$$$ is any $$$K_5$$$ must be monochrome, and maybe some solutions can check this to reduce the number of variables and equations. (actually myself considered this. But after the contest ended, I realized that I’m overthinking, and I’m very frustrated because of the puzzling constraints)

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

    Similar feelings about E: firstly I wanted to fast write $$$O(26nlogn)$$$ with splay tree but thought it will TLE and I spend ~20 minutes to achieve $$$O(nlogn)$$$ with BIT. Splay passed in 62ms in upsolving...

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me the mistake in this code for problem C

Code
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    It might be due to double / float being not precise. It is better to implement this using int. To do this, instead of dividing $$$x$$$ by $$$(j - i)$$$ at the initial step, you check whether $$$(a_j - a_i) \cdot (k - i) \% (j - i) \neq 0$$$ which means that the result is a floating point number, otherwise you can get the expected value of $$$a_k$$$ to be $$$\frac{(a_j - a_i) \cdot (k - i)}{(j - i)}$$$.

    You can view my submission here: 141082107

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

It seems for E, you can just copy and paste this , modify it a little and run binary search to get K. Unfortunately, I was unaware of it and coded a solution from scratch... RIP rating

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Are you seriously saying that being unable to copy paste an existing solution is unfortunate? Yikes.

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

Hi, This contest has a lot of traps (eg. Problem B, C). May I ask that how do you all do testings other than stress testing to find out the wrong proof that we have made? I am very often stuck in these kinds of situations where my solution is mostly correct but due to tricky edge cases or wrong assumptions (for eg my problem C) that I could,t find out I was a mistake. I wish that I could get some help in facing these situations because I quite often faces these issues. Sorry for the bad english. Thank you very much.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so sad. After I solving the Problem C I am nearly 70th, But after I solving the Problem D I am nearly 700th.

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

    I use a dp to solve the Problem but I think it is too hard. So I use greedy and pass the pretest suprisely in the end. It takes me nearly 1h. Is there anyone have an easier solution? Many thanks.

    My stupid greedy

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

      The first part of my solution is similar to yours: subtract $$$x$$$ to all the elements of $$$a_i$$$ so the problem becomes make range sums non-negative.

      Then, we use the following greedy algorithm:

      Iterate from $$$i=1$$$ to $$$i=N$$$, let us assume that $$$j$$$ is the maximum index smaller than $$$i$$$ such that $$$a_j$$$ is not selected. Then, if there exist any $$$k$$$ where $$$j < k < i$$$ and $$$\sum_{x=k}^i a_x < 0$$$, we can delete $$$i$$$.

      To implement this, we can store the prefix sums of $$$a_i$$$ and keep track of the maximum prefix sum when we iterate from $$$i=1$$$ to $$$i=N$$$.

      You can see my submission here: 141100821

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

When will ratings be updated?

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

    It's clear that rounds with unusual timing have unusual rating updating :)

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    CF Predictor says I'm becoming a specialist, but only by 6 points. I can't handle this uncertainty

    → Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Codeforces is taking longer time than usual to reflect the rating changes :(

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add tutorial, looking forward to read approaches for D and E problems

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is error in my solution for problem b my solution

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    wrong answer 8th lines differ — expected: 'baaaab', found: 'baab'

    for input: baa

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

When will ratings be updated??

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    you can use CF predictor to get approx idea about what your rank will be be. I understand the excitement before announcement of ratings

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone find the mistake in my Problem-C solution?? link to my solution. https://codeforces.com/contest/1616/submission/141148146

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

    use integers and multiplication instead of floating points and divisions

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is error in my solution for problem C . It is failing in 7th testcase.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    you have used double as data type for the common difference. instead of this you should have cross multiplied the denominator value with all terms in the equality statement

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

      yes got ac but why division of doubles give wrong answer. Is it due to precision error?

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

        Yes it is most probably due to precision issues in comparing double values. I handled that in my submission — 141107791

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

    Your solution is failing probably due to comparison operator (!=) you are using in inner most for loop arr[k] != a + k * d. This way of comparing double is inappropriate. Replace that line with : abs(arr[k] — (a + k * d)) > 1e-10 and it should pass !!

    → Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

When will the rating be updated？

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

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Editorial of this contest is published https://codeforces.com/blog/entry/98501

somehow they didn't linked it to this post

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

In problem C,7th testcase was not included in system testing!!

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Anyone else waiting for rating change to see that beautiful purple color of candidate master

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

Can someone please clarify why the 7th test case was not included in system testing for problem C ?

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

    Those are hack tests. And probably added by >=CMs after system testing

    → Reply
»
2 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Please tell me how to get the reward of this competition

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

Hi, my solution for problem 1616B (141080537) and the solution ti21_phnam (141107393) was found to be too similar by the system. We believe that there is nothing similar in them, except for the title, but this is a comment. Can the authors of the round or the admins deal with this situation?

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Yet another young LGM in China ,He_Ren orz.

→ Reply
»
2 years ago, # |
  Vote: I like it -31 Vote: I do not like it

And where did you guys take DIV 3 and Div 4 contests? Not all of us are in the elite league consider!!!

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

    Do you realize that beginners get more resources than anyone else? You get more contests, more tutorials, everything. And yet you demand more. Be happy with what you get. Div 2 contests are completely suitable for you. Don't be so entitled to expect everything to be tailor-made for you.

    Further, the last Div. 3 was a whopping 10 days ago. That's a normal gap.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it -28 Vote: I do not like it

      He is not wrong tho. You guys even participate in div3. Solving questions in like mins or so and When we get stuck, (and check the leaderboard by mistake), you guys have already finished the contest. It demotivates the shit out of us.

      Talking about div2, Sometimes it is difficult to crack even A. But you guys, make it look so easy that anyone below you, if asks for something(like the comment you replied to), You guys treat it like its worth nothing. -is-this-fft-

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

        I think if you get demotivated by the existence of people better than you then it is hard to accomplish anything in life; Codeforces should not take such feelings into account.

        When I started, there was no such thing as Div 3. And people managed to improve just fine. The whole existence of Div 3 is IMO a big favor.

        → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

Wrong solution marked correct My solution of the problem C has been marked as AC in the contest. AC SOLUTION However this solution is incorrect possibly due to floating point precision. On trying to resubmit the problem now it's giving WA on test 7, however in the contest there were only 5 tests and the solution was able to pass all those tests. Would you please revaluate the solutions? @thenymphsofdelphi @74TrAkToR @gamegame @300iq

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

    It could be that extra tests got added after system testing. In that case it isn't right to rerun systests since it could be done forever.

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

      Well that sounds right! I understand the thing, however it’s weird to know that the testcases were weak enough to make some wrong solutions pass. Thanks for the input

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Let's use the new feature!

Problem A:

liked:
disliked:
neutral:

Problem B:

liked:
disliked:
neutral:

Problem C:

liked:
disliked:
neutral:

Problem D:

liked:
disliked:
neutral:

Problem E:

liked:
disliked:
neutral:

Problem F:

liked:
disliked:
neutral:

Problem G:

liked:
disliked:
neutral:

Problem H:

liked:
disliked:
neutral:

→ Reply
»
2 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Hi! I got rk12 in the goodbye round. However, I only received Ⓝ0.1 rather than Ⓝ16. I guess it's because I changed my handle after the contest. What should I do now?

→ Reply