enot110's blog

By enot110, history, 21 month(s) ago, translation, In English

Hi!

This round is sponsored by esports team cybercats. The team was founded in October 2021 by me and subscriber.

We currently have a Dota 2 roster, playing in the second division of EEU DPC. Come support us on streams and in the comments!

As a thank you to Codeforces and the competitive programming community, we decided to make this round and give away 100 plush cybercats!

The prizes will be awarded to the first 100 places in the round.

Follow our social networks:

   (RU) VK    (RU) telegram    (RU) youtube    (EN) twitter.

The problem set was prepared by subscriber, isaf27, KAN, Catmoonlight, jdurie and BucketPotato.

Round was tested by enot110, izban, qwerty787788, MateoCV, ilyakrasnovv, blobugh, ak2006, Valters07, DiegoGarcia, Chaska, kzyKT, Dan4Life, FedeNQ, alysonNBS, petertromso and jojonicho.

UPD. Scoring distribution: 500 — 1000 — 1500 — (1500 — 750) — 2250 — 2500 — 3000 — 3500.

UPD. editorial

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

I have got negative delta in div1 or div1+div2 contests for 3 times (and dropped from master to CM twice), but I still decide to take part in next contest (and get another negative delta).

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

    Worst Contest I have Ever Seen!..

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

      Absolutely, only 7k people participated, the problems were too hard so that many did not even submit A

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

        I feel A and B were fine for their spot (considering it isn't a div-2, but a div-1 + div-2). C felt too hard for being C. D1 and D2 were cool problems and I really liked them, and I think they were a little easy for their position. Can't say anything about other problems since I didn't solve them.

        So which problems exactly do you feel were hard for their place? (apart from C, I agree with you on that one)

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

        cannot agree with you more.

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

      True

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

Div1 + Div2, but no Div2 tester.

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

You forgot to thank Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces

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

    They also forgot to thank X for excellent coordination and help with preparation

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

cypurr cats!

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

Hi Vlad, no Rocket League roster yet :p? Did you hit Diamond or higher :D?

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

    diamond 1, finally!

    no pro Rocket League roster yet, only the fan one :)

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

I might end up top1 in this contest

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

I think and hope the problems are easier than yesterday's #853

Spoiler

We also have 3 hours unlike yesterday where we had only 2 hours for that div1. Hope it's gonna be great and educative.

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

You know, I am something of a cybercat myself

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

    I've read all of your submissions on Codeforces, really really impressive.

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

      Did no one get this? This is the response that Peter gave when Osborn said that.

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

        I am ashamed; I only remembered the initial quote, but now when you mentioned it, I also recall that response!

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

Hello guys — I am new to codeforces. I just tried my first div 2 virtual contest and solved 2. Is it okay to participate in this one, or should I stick to div2/3/4 contests?

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

    Give all the contests except Div1. This contest has Div2 questions in the beginning so you can participate.

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

    Do participate in all contests. Even if ratings go down, it can be recovered in 2-3 good rounds.

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

To be really skilled at both gaming and cp. Orz

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

Wow, this is so cool 😄. Never thought professional gamers would sponsor a Codeforces Round. Pro at not only CP but gaming too!! I wish your team all the very best in all your future endeavours.

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

As a tester, I highly encourage you to read all the tasks!

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

I liked your old logo more :(

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

Hope this is my real CM promotion contest ):

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

    what happened in the last round ? you posted the same comment last round right?

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

      +12 , not enough to become a CM ): But yes right

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

This cat looks kinda sad

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

I guess the problem statements will not be short and clear and will include some story of the game they are promoting.

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

cute cat :)

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

How many problems can we expect in this round ?

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

I felt something like lol after testing.

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

The timing is not very friendly to Chinese participants, as they still have classes tomorrow.

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

    It should be obvious by now mate, Codeforces >>>>>>>>>> classes :)
    Best wishes for the round ! <3

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

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

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

Pls no weak tests today.

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

so cute!

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

Wow, I saw this team in DPC standings, but had no clue someone known to me is in charge. Can you tell its story?

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

As a tester, i confirm the round is good :)

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

I hope after this round I will stop being a prisoner of the cyan

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

when there will be twitch streams ?

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

Can't take part today, but the problems look nice.

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

How to solve D1, D2?

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

    D1: You can do it using a simple O(nk) DP (define state dp[i][j] as the minimum time to do the ith task such that the other machine (the one which doesnt do the ith task) last did the jth task). Transitions will also be quite easy, you need to handle the case wherein (i-1)th task = ith task separately though.

    implementation: https://codeforces.net/contest/1799/submission/195167349

    D2: If you observe the transitions carefully you will notice that at each i, what happens is that we do a range sum update on some dp values from the dp[i — 1] table and set them to their corresponding values in dp[i] table, and a point update on one dp[i — 1] value and set it to its corresponding dp[i] value, so this can be done easily using a segment/fenwick tree.

    implementation (segtree): https://codeforces.net/contest/1799/submission/195178402

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

    I solved both D1 & D2 without segment tree or Fenwick. You can watch my video editorial if you are interested: https://youtu.be/oOyPQL16x1M

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

Yeeee, i created E of this round 2 years ago

https://www.codechef.com/FEB21C/problems/MEOW1234

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

I really liked the problems but the round was weird for me, I was able to solve D1 and D2 quite easily but I can't for the life of me figure out how to do C. Could anyone give me a hint?

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

    I tried my best and got WA on 4th pretest :'(

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

    I have a quite long solution for problem C although I don't know how to prove it yet: Firstly, create two pointers p1 ( set to 0 ) and p2 (set to n), then save all the strings to a map and then iterate through the map, then for each key in the map, if the frequency of that key is divisible by 2, then simply put the first appearance of the character in p1, the next one to p2, the next one to p1, etc until it ends. If the frequency of that key is odd, do the same process for the n-1 number and then break out of the map. At this time, there are 4 cases : 1. If the map is now completely empty, we can check for the constructed string and reverse version of it to output the larger one out. 2. if the map size is equal to 1, then put the last element in the map in the position string size/2 and printout the larger of the constructed string and its reverse version 3. If the map size is >= 3, then we can put the current element in position of p1 and the other element in the map inside the string in reversed order and output 4. If the map size is equal to 2, then we can put the remaining 1 element in the middle of the string and then put all the other inside it and output it .

    Code : https://codeforces.net/contest/1799/submission/195192191 ( sorry for the bad implementation )

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

    I agree, for me too C is harder than D. For me it just came down to considering three cases:

    1. Every frequency is even. Then the answer is just 'abccba'.

    2. Suppose that the smallest symbol whose frequency is odd is symbol 'f'. Then if all symbols greater than 'f 'are the same, then the answer is 'abcfffggfgggfffcba'.

    3. Otherwise, the answer is 'abcfffghijkffffcba'.

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

seems like it was div 1 only not div1+2

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

Dislike C and E lol

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

one of the best Div2B on codeforces

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

    Why? It’s straight forward to get a 2 which is true if you have more than 3 different elements. Otherwise just check if you can make a 2. Whats so good about it

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

Why problem C are usually harder than normal in div1+div2 rounds? I've consumed much time on it.

Ps: I've lost 50 points for forgot to change array size from 5000 to 300000 when submitting solution of D2, and lost 100 points for forgot to check whether ptr<0 when solving problem A. Why I perform badly on every div1+div2 rounds...

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

    When I started testing, C and D1 were not in the problemset and the order of other problems was A — B — F — E — D2 — G — H. Of course the standing page was funny, and current problemset is even much improvement. This is why I felt lol after testing.

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

    I agree that C was very troublesome to deal with (and I personally had multiple incorrect implementations of a correct idea). I think that kind of messy problem might appear in any kind of round and that it might just be smarter to skip it directly (tbh, after reading the statement, I could guess that I would most likely spend inf time on it).

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

Don't like ADEG, very boring problems.

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

In Problem D1, can we create a 3d dp array where the 1st one is for index, 2nd one is for the number of elements which are consecutively used by current CPU and 3rd one is for current CPU ?

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

How to solve hairy multiple case problems like C? I was on it for 2:00 hours of thinking different cases and got AC on 2:55

Was this problem kind of pain for everybody? or is it just me not thinking in a good way? Can div.1 contestants solve it easy and without pain thinking???

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

    Skip the problem.

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

    I also wasted 2 hr solving this, and after that when I saw D1 it was direct dp but there was no time to complete the code.......

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

    I agree with every word you said.

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

C and E are trash problem.

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

C is really tedious to solve. It’s almost like trial and error. The fact that it has so many submissions means there are tons of cheaters on this round

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

How to solve (prove) B?

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

    If there's exists some $$$i,j$$$ ($$$i \ne j) \quad a_i = 1 , a_j \ne 1$$$ then we cannot make all the elements equal. because for $$$a_i = 1$$$ you cannot change it. and if you attempt to make the other elements 1 then you are failed also because after making $$$n-1$$$ elements to 1 then you cannot make the last one same because it is now max of the array.

    But if you have an array of greater than 1 integers, then you can make all of elements 2 in at most $$$30n$$$ operation. the idea is whenever you found two distinct elements you can divide greater integer by smaller integer. so in this way you make array elements smaller and smaller till you make all elements equal to 2.

    Worst case scenario you have to divide 10^9 by 2. then it wouldn't take more than 30 operations (because $$$log(10^9)<30$$$)

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

      Sometimes you don't even reach 2, but rather a bigger number.

      Example: (23, 8, 3) --> (3, 8, 3) --> (3, 3, 3).

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

      Thank you)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1. If you've got 1, array must contain 1s only: otherwise you can't make array maximum equal to 1.
    2. If there is no 1, let's divide non-minimal elements by minimal element. This will eventually make all numbers equal, as this algorithm does not create 1 and the array decreases on each step.
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

E is just a tedious implementation problem. I really enjoyed solving from A to D, but E just simply ruined all my mood.

Please send my thanks to whoever create such an atrocious problem E.

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

Is it only "Zero IQ" me who found C to be extremely hard? How to solve it :")

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

    Sol:

    Let's construct the optimal string in two parts (a left side and a right side which are respectively a prefix and suffix of the final string)

    In the first step we will keep the following invariant: left is the same string as right

    We consider the chars in lexicographical order

    While the current char occurs an even number of times it is clearly optimal to split it evenly on both sides (it is easy to get a contradiction as if you place more a to the left, then you would put some, say, b at the symmetrical position in the right side and you could get better by putting an a instead).

    Now we are either done, either facing a char C having odd count.

    As earlier, it is optimal to split the even part of the char equally on both sides (so if you have 5 a you will put aa on each side).

    (You can do a proof by contradiction exactly like earlier)

    There is now only one occurence of C

    Consider two cases

    1: you have one or less remaining chars greater than c

    2: you have more than one remaining chars greater than c

    Case 1:

    if C is the last char, you just put C as it's the only thing you can do

    else, it is basically analog to solving the case abbbb...bb and in this case the best answer is (by casework) to put a in the middle of the group of b

    Case 2:

    There are more chars so its similar to solving abbccdd... (you can compress adjacent equals chars to make them blocks)

    Here we can wlog assume that reading the string starting from the left side will give the lexicographical smallest string.

    Assume you don't place a right now, it will be suboptimal as you would add some b on the left and right side (if you add anything greater the string becomes >) and now if you add a on the left side, you can just swap a with the b to get something <= (same on the right side by symmetry).

    So you will add some c on both sides but what can make a better answer.

    So you should add a to the left. Now it is clearly optimal to sort the remaining chars.

    Indeed: we know that reading from the left side gives something strictly smaller than reading from the right side so we are now only interested in making the right as small as possible

    Code: 195196709

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

Constraints in D1 are toooo bad!

n*n*4 memory is not allowed while n*n*2 is allowed

and n*n*2 time is not allowed while n*n is allowed

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

    So do we need to tabulate the solution ?

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

    There's no need for 2D array in D1.

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

      Can you share how did you solved it ?

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

        Let dp[i] = the answer of the problem when consider on range [1, i]. dp[0]=0.

        First, let dp[i]=dp[i-1]+cold[a[i]] when a[i]!=a[i-1], or dp[i]=dp[i-1]+hot[a[i]] when a[i]==a[i-1]. That's the situation when we use same cpu for i-1 and i.

        Then let j<i-1, a[j]==a[i] and assume we use cpu1 for i and j, cpu2 for [i+1...j-1], we can get dp[i]=min(dp[i], dp[j+1] + cost(j+2, i-1) + hot[a[i]]) where cost(j+2, i-1) is the cost for range [j+2, i-1] if we use only one cpu (we can calculate them in O(n^2)), and for checking all valid j, we can solve D1 in O(n^2).

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

          Hey, your solution seems easy but i do not understand the cost() function. becuase i am confused with the first element of cost(). the first element of the $$$cost()$$$ function contributes $$$cold[j+1]$$$ or $$$hot[j+1]$$$?

          can you explain please.

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

            assume we use cpu 1 for j, cpu 2 for j+1, j+2, ... i-1, cpu 1 for i. So each k in [j+2, i-1] contribute hot[k] if a[k]==a[k-1].

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

              but i am asking for the cost of $$$j+1$$$. We are using cpu 2 for $$$j+1$$$? It will take some time to process the $$$j+1$$$ process. But will it take $$$cold[j+1]$$$ or $$$hot[j+1]$$$ ?

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

                Cost of j+1 is contained in dp[j+1].

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

      Yeah, but if one person had n*n time solution, he got AC , but if someone has just extra factor of 2 , it got TLE , this does not seems fair!

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

        My solution for D1 ran for 46 ms, so even a 10* constant factor doesn't matter (if you're using c++).

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

          What is time complexity of your D1 solution

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

            O(n^2) of course

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

    I agree. Lost more than 450 points because of memory.........

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

    You can use the "hidden parameter" technique to only store the current layer of DP, reducing the memory consumption to O(n).

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

My solution for C (passed pretest but I can't prove it):

  1. Sort string s. Let ptr=0, L=0, R=n-1.

  2. If s[ptr]==s[ptr+1], we must put them on ans[L] and ans[R] in order to minimize t_max[L]. Repeat this while increasing ptr by 2, until we are done or we meet s[ptr]<s[ptr+1].

  3. In the second situation, we check if s[ptr+1]==max(s)==s[n-1]. If not, the answer (for the remained part of ans) is s[ptr+1...n-1] + s[ptr]. Otherwise, the remain part of s is something like "abb...bb", so the answer is 'b'*ceil(k/2) + 'a' + 'b'*floor(k/2), where k = count of remaining 'b'.

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

How to solve B? ;-;

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

Could we just stop making problem A too hard? Making problem A too hard will scare out most of the contestants, making number of participants too small and are quite unfair for all of real participants, making them very likely to drop rating.

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

    But it's completely trivial ._.

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

      Actually,you can let more pupil or specialist to test, and if any of them cannot finish this problem in 15 minutes, this problem should not appear as problem A.

      First, the description of problem A should be simple, can let all participants have idea what this problem is about. If they are confused, they just quit the contest.

      Also, the constraint of problem A should be very small to let brute force to pass. As I know from some of my friends, when they do a contest, they will see the constraint of problem A, if the constraint of problem A is more than 10^4, they just know this is a harsh contest and quit.

      In my opinion, Problem A should act as a "sign up" problem and should not have any difficulty.

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

        Plus plus, hxu10

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

        In my opinion, Problem A should act as a "sign up" problem and should not have any difficulty.

        So are you proposing to decrease amount of real problems in every contest by one?

        Heck, it's competitive programming after all, we are here to solve problems, not to write A+B in every single contest. IMHO, it's fine that today's A is not completely trivial, because that's A of combined round. It should be interesting (despite not hard) to solve for everybody. And there are different types of contests for newbies out here (div3 or even div4) where I don't care if A will be A+B or whatever.

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

          Also, I agree that there is a need for a way to "sign up" for a contest in order to avoid situation when people are reading problems and skipping the round. But let's just add corresponding button and not affect problems quality.

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

    If participants are scared by task A, I think they don't submit any solutions so their rating is not going to drop. However, as average rating is (almost?) constant, this means someone other with higher rating will have to fall, and that's sad)

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

    I am a newbie and I don't think it's hard it you think in the right direction, I immediately had the idea of using deque or set. I think the problem is not the difficulty but their inability to fight hard until they could solve the problem.

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

      Good for you for solving A so quick. However, many of the newbie are not lucky enough like you to think in the right direction. They are frighten by the problem description and just go away.

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

    I think today's A was really an easy A (compared to A requiring some number theory or some ideas, thus pushing beginners to guess the solution and submit random ideas).

    The only problem might be the statement which is a bit confusing if you read it too fast but I think that beginners don't try that hard to get AC in less than 10 minutes x)

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

    making them very likely to drop rating

    I don't think you'll lose any single point of rating because of 100 (or even 1000) grays who weren't able to comprehend A.

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

      If 100 user did not attend the contest, that is true. But 1000 user did not attend, that will be different.
      Actually, there are at least 4000 users who did not attend, let us see what is the difference.

      In round 854, 7800 rated users, if you are rank 1000, your performance is 1851.

      In TypeDB Forces 2023, 11000 rated users, if you are rank 1000, your performance 1958.

      That's totally a 108 performance difference. Usually, every 4 performance change will cause 1 rating change, which means that will cause 26 rating change.

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

        I'm sure this difference is caused by higher rated users who didn't attend (most likely from objective reasons) and not by hundreds (or even thousands) of grays who was scared by A. Because if we are talking about milestone of top 1000 which you mentioned in your comment — it's very unlikely that many grays in the bottom of standings will really uprise the rating of top-1000 as top-1000 scorers are rated much higher then gray (on average) and grays below them don't affect their expected place much.

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

Anyone enjoyed the number of sample tests?

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

    Absolutely! And even more their coverage. I was about to start writing wrong solution on C and closer look on pretests really saved my time.

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

    It's good that you add test cases. It will be better if you can make statements more clear.

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

A-G are all very boring and disgusting.

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

Why the aim of TL=1s? Seems tighter than usual and I hesitated to implement >100ms (like 1e8 steps) solution.

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

Nice to see strong pretests :P

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

could someone please tell the logic of b question

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

Greedyforces

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

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

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

this round be like...

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

Why is F so easy?

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

    I had one red guy in my room who will not agree with you :)

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

Why are constraints in G so low? I have $$$O(n^2)$$$ solution and it can be optimized to $$$O(nlog^2n)$$$ with FFT

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

I accidentally solved F in O(n log n) despite N = 5000, though I feel that giving N = 2e5 would make a more interesting problem.

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

    I wanted to make subtask with bigger $$$n$$$ and I noticed such funny solution: in the $$$O(n^2)$$$ solution we can just make ternary search by one of parameters because the function is convex (don't know how to prove, just made a stress test).

    I think there are many approaches to make $$$o(n^2)$$$ solution, but we noticed that the problem is enough hard for some reason, so decided not to make the subtask.

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

F is solveable by simply using the same solution of https://codeforces.net/problemset/problem/739/E.

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

out of 21K participants only 7K are rated for them, just implement the atcoder system already

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

Why is this round Div.1? It is definitely not hard enough.

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

wow, very fast editorial, thanks

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

If only 2 more minutes were left, I could've solved C. Well glad that at least my idea was correct..

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

D1 :( :(

long long int dp[5001][5001][3]; gave MLE long long int dp[5001][5001][2]; got AC;

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

    Note that u can drop the first dimension

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

Why was this contest this difficult the B problem ripped me apart *_*

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

So low constraint in E led to me implementing a total atrocity of a 5-dimensional dp that works in general case (i.e. arbitrary set of initial cells). After coding it for ~45 minutes it was ~2 times too slow when implemented in $$$O(n^5)$$$, so I needed another ~45 minutes to optimize it to $$$O(n^4)$$$ and then it got WA, so I spent another 30 minutes to write from scratch another solution that works for 2 cities totalling 2 hours for E. I also misread D thinking we got nonconstant number of CPUs and did not finish G on time. My worst performance in a very long time xD (sry for wrong choice of words before the edit xd)

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

Problem D is a harder version of 1479B2 - Painting the Array II. I actually resorted to copying ecnerwala's solution to that problem (which generalizes easily) because I'm really bad with this type of problem.

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

    I remembered the greedy approach to this problem and used a similar idea where we are assigning the program to the CPU whose latest program is occurring farther in the future than the other. But it gives wrong answer. submission : 195166846

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

I hate C.
Spent 2 hours and found out it is so fxxking easy.

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

    can u give me a hint ?

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

      try to build a string with min lex so that the leftover pieces can form a reverse string with lower or equal lex. In this case you can make sure the string you build will be selected as answer, and still some implement ation details need to be worked with.
      Seriously, It was way past my sleeping time when I worked on this problem.what are your excuses, down voters?

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

We only recently had a ton of community discussion on how unfun it is for participants to express nonconstructive negative feedback only for this comments section to be flooded with it for not much of a reason ._.

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

Before systest: NO... I'm in 101st place and I had been resubmitted 951ms E... good bye my cat...
Now: Let's GO!!! I'm in 99th!!! Hello, my cat!!!
upd: Sorry I was just lucky, got uphack on E...

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

Can anyone tell why my code is failing for Problem D1 as I have declared long long everywhere still ans is coming wrong ?

It is giving correct ans in my IDE but failing when I am submitting Submission Link — https://codeforces.net/contest/1799/submission/195194098

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

Got stuck in A don't know why!!!!

Got the idea of B in 10 mins and implemented the same, but I didn't get the idea due to pressure that I have to change int to double for both the variables (numerator and denominator) to use ceil and wasn't getting answers as I was only doubling numerator.

Figured out and saw the contest ended:(((((. Submitted after the contest and it got AC! Such a bad day!!

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

    Don't use double for ceil. Ceil(a/b)=(a+b-1)/b

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

      if youre using c++, this will give you WA with negative numbers

      a/b + (a%b>0) better

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

I once saw a website for predicting the difficulty of the problems.

Is it still there?

Link?

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

I have submitted the same code again and i got Accepted

If there is a way to rejudge the solution again?

195196340 Accepted submission

195171454 TLE submission

subscriber, isaf27, KAN, Catmoonlight, jdurie, BucketPotato, MikeMirzayanov

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

In Problem B I have a question Can we solve in this way if the number does not contain one then check whelther dividing the no by a[i] with a[j] the value of a[i] will result in two or not If the result is two then we can convert all the number by selecting the ind which get converted to two and the remaining index one by one except the ind index Please answer this Thank You

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

    No. What if there are only 2 numbers, a 3 and a 9? In this case, we divide 9 by 3 and then the array will have both elements with the same value.

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

Why F is easier than C?

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

    I solved D1 significantly earlier than B, and that really surprised me)

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

    Because current F was originally in C — you and the setter had same thought :P

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

    Feels the same, it took me longer to get the idea of C than F.

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

Did anyone else solve C recursively?

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

Hi guys you can check video editorial for

Problem A , Problem B, Problem C, Problem D here — https://youtu.be/AGIrdT_cQuY

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

    Can you tell me what I am doing wrong 195231790

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

      return ans=cc[aa[l]][0] + min(rec(l+1,pre),rec(l+1,aa[l-1]));

      here you are directly returning without saving the data into the dp.

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

Can someone please point me where my solution is leaking memory for Problem B ? — Solution

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

As long as I have more than 2 hours to solve, its good :D

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

Dear sir, MikeMirzayanov

I recently got message from system that my solution 195163597 is same as others, several names were there. But I did not copied from anyone. You can see I was getting MLE in my initial verdict, then TLE and WA. My initial logic was making all elements 2, which I was trying for atleast 45 min. After getting so many wrong verdict I removed all my code and started again.

I removed all my template in order to not get any TLE( as earlier I have suffered TLE because of my template ), and wrote the basic logic divide by minimum every time, which unfortunately came very late. The question logic is common for everyone. It does not mean that everyone have shared the code. Please correct your plag checker.

I know it was mistake but we who do not cheat and give a lot of time we get plag, just like other cheaters hurts. Please look into this.

Please correct it and improve your plag checker system, and thanks for such great platform for CP

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

How can I get my cat? haven't received any message yet :(

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

    Be my cat.❤

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

    Normally, you'll have to wait for about a week or so to get a notification. (and wait for a year to have it delivered to your home)

»
20 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Dear MikeMirzayanov

I received a message from the system that my solution is similar to unordered_map's solution. But only the input part matches and the process of calculating the dp table is different.

Also, problem D1 is similar(the definition of the dp table is exactly the same) to the past problem in KOI(Korean Olympiad of Informatics), which is well-known in Korea. Both I and unordered_map have solved it. So, we were able to solve D1 without copying the code. It seems that it will be faster to implement it alone than to search for the solution code.

I think the system is detecting coincidences only in the LCS of two codes. Please correct this.

My submission : 195156487

Skipped submission : 195164678