_LeMur_'s blog

By _LeMur_, 11 months ago, In English

Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round 917, which will take place on Dec/24/2023 17:35 (Moscow time). Round will be rated for participants with rating less than $$$2100$$$. Participants from the first division can take part out of competition.

There will be $$$6$$$ problems for $$$2$$$ hours. The problems are authored by IgorI, zidder and me.

Part of the problems in this round were in the Yerevan SU 28.1₀.₂₀₂3 Contest. If you participated in it or know at least one problem from it, please refrain from participating in this round.

We would like to thank

Scoring distribution: $$$500 - 1000 - 1500 - 2250 - 2500 - 3000$$$

We hope you'll like the problemset! Good luck and have fun!

UPD 1: Editorial

UPD 2: Congrats to our winners:

  • Div1 + Div2
  1. tourist
  2. Sugar_fan
  3. BurnedChicken
  4. Rubikun
  5. kotatsugame
  • Div2
  1. -Misaka-Mikoto-
  2. _chashuibiao_
  3. needy_and_sorry
  4. Godjob
  5. LordVoIdebug
  • Vote: I like it
  • +281
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

]

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Great!!!

»
11 months ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester, I recommend trying all of the problems (really good ones). Also I wish everyone positive delta as a Christmas present:)

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I will try it!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

^_^

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I want to reach pupil after this round

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking like speedforces:( because D is 2250.

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

hgglmao This round is good?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope i become expert after this round

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

CM TIME

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

participate cf contest on Christmas Eve (east Asia time) this is really a round 😂

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Big point difference between C and D

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it
╱|、
                      (˚ˎ 。7  
                       |、˜〵          
                      じしˍ,)ノ
»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hopefully I become a master after this contest!

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

Maybe I can reach specialist by the end of this year :)

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

    Mate you just missed by 2. Maybe in rechecking later it may increase.......

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

      Yeah, was almost there... maybe next time

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

      And I'm confused how the hell on earth did your code for problem C got accepted...I just copied and ran your code and it's showing WA on testcase 38

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

        Can you tell me what did you change to get it accepted?

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

          Just ran the outer loop till d rather than min(d,max(n,k) and then checked inside the loop if n+(d-i-1)/2<=current_answer then simply break as checking beyond it wont give the maximum answer. Because the max n can go upto is 2000 where as d can go till 1e9.

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

            I found that if I run the loop till min(2*n,d) it works.

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

              Yeah same approach in editorial as well... no need of using min(2*n,d) just 2*n is enough

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

                Congratulations dude you became specialist.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester for the 1st time,i feel proud.

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

    i often wonder what exactly does a tester do ? and how do even 1200-1300 rated people become tester

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Specialist Time ! I hope .

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yeeeeeey

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yo

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become Expert.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope is a good thing

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will finally give a Cf contest. Lets go.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a contestant,I want to reach pupil after this round btw

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

best wishes for every one

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Clicked me now, why all are LGM here

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a kawazaki I will participate

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

AbduSaber First tester from Sohag, Egypt :) , remember this name very well -_- .

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

Hope to solve all the problems!

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

As someone who has a birthday, please give me a contribution.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really weak sample for C. Is it fun to see players wa2 again and again?

»
11 months ago, # |
  Vote: I like it -6 Vote: I do not like it

my last unrated contest

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope will become expert

»
11 months ago, # |
  Vote: I like it +22 Vote: I do not like it

unbalanced forces !

»
11 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Defeated by constructive round. so sad.

update: now I'm defeated by the FST XD

»
11 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Am I missing something or does D effectively boil down to:

  • Calculate inversions within P.
  • For each i, calculate number of values in P which would be its inversion for relative power shifts between -20 to 20.
  • Iterate over values of Q, and check how many occurances of [Q_i — 20, Q_i + 20] lie before it and add them to the answer.

I spent 15-20 mins thinking of how to simplify this to something I could implement without going insane before giving up and going to problem E instead...

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

    Had the same idea, how are you calculating the inversions for relative power shifts? My approach ended up double counting many things

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

      I didn't implement it because I felt it would be an utter mess. As I mentioned I just gave up and went to solve E instead.

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

    You don't need to simplify this to anything else. You can calculate this directly

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

      I mean "simplify" the implementation so I don't go insane implementing this. I seriously doubt I could code this in less than an hour with all the debugging from minor mistakes that are likely to occur. It feels like a 10 mins to think, 1 hour to code problem.

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

    Can u plz explain me your submission for problem B, why it is working ?

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Whoever made C deserves lifetime sentence in jail.

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

How to approach B?

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

    Sum of the first occurrence of each character is the answer. Suppose we have s = "abeakf". Then if we consider 'a' is the first character, we will have ["abeakf", "aeakf", "aakf", "akf", "af", "a"]. We only need to care about the first position of character 'a' in s, because if we tried to used the second 'a', the result string will be duplicated (these are "akf", "af", "a")

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

    Essentially, the only difference between strings after "i" operations is the first letter. That's because you can't reach the other characters through these operations. However, that initial letter could be any letter present in the prefix of length "i" of the original string. So, you calculate the number of unique letters in each prefix and then sum them up. That's basically the answer.

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

    Just add the left over length when ever you encounter a new character. for a string abcde the number of substring contributed by letter 'a' => $$$a, ab, abc, abcd, abcde = 5$$$, 'b' = 4... so on.

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

    check the string from left to right, if i th character has not appeared before, answer += n-i

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

    I thought of that in this way. Suppose you have a string "ayush",now if you want to find all the strings of size '4', "ush" will always be there so the string will be "_ush" now for the first character look at how many distinct characters we have encountered before we reach 'u' (2), so there are two possible choices for the first character. Do this starting from size 'n' to size '1'. Hope this makes sense to you!

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

still don't know why in C, when I tried to iterate min(n, d) times, it gave me wrong answer, since I thought it is enough to make the array big. I used a large number instead like min(5000, d) and got AC.

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

    i did min(3*n, d)

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

      why?? can you explain why calculations after 2*n/3*n will be waste??

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

        Suppose we have:

        A = [N, 1, 2, ..., N-1]
        V = [1] * (2N-5) + [N]
        

        Then after (2N-5) + 1 operation (1), we have:

        A = [3N-4, 2, 3, ..., N]
        

        where 3N-4 = N + (2N-5) + 1.

        Apply operation (2) to score N-1 in (2N-4) + 1 = 2*(N-2) + 1 < 2*(N-1) which beats the alternating method from the zero array.

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

          This seems much like a case specific example. How can you guarantee that the claim is true for any A and V ?

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

            All the calculations from an initial array A only result in a single scoring operation before it gets reset to zero.

            As stated in the comment below, the largest score we can get from a single scoring operation is N — assuming every element satisfies the criterion.

            Calculations taking strictly more than 2N moves are not better than scoring immediately (ie. transition to zero array; if needed) and then alternating operations 1 and 2, scoring N.

            I produced the earlier example to show that in some case, we cannot perform much fewer than 2N moves either.

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

              Oh, I get it now. Thank you so much.

              UPD: I would like to explain mathematically (that's how I like to go about it). Let's say you have done operation 1 for the first $$$X$$$ days, and for the rest $$$(D-X)$$$ days, you'll perform both operations alternately. So your total score would be $$$S + (D-X)/2$$$ where S is atmost N. If you had performed alternating operations from the start, you would have scored $$$D/2$$$. Now, my prior answer is better only if:

              $$$\frac{D}{2} < S + \frac{D-X}{2}$$$
              $$$\Rightarrow X < 2*S$$$

              Hence, you will get the most optimal answer in the first 2N days because S could be atmost N.

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

                You can't get $$$d/2$$$ in general case because if you start alternating ops from day 1 you'll get $$$initialScore + (d-1)/2$$$. Proof: 238854323

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

          oh I got it, we want to maximize the answer, so one possible answer can be d/2, via doing reset and cash score operations. but to further optimize our answer, we will be checking first at least 2*n days and check whether we can score of n-1 in these days or not. if we can that would give us maximum possible score.

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it +12 Vote: I do not like it

    $$$n$$$ is not sufficient. You can raise the answer by $$$1$$$ in $$$2$$$ steps using operation 2 but operation 1 can add upto $$$n$$$, so you need to check for the first $$$2 \cdot n$$$ steps.

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

    I can proof. You actually need to do not 5000, but 4001 (additions). Because if you do 4002 additions and get 2000 score as return, you could have also done 4001 for 2000 score with the strategy — do one addition — cash the score

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

    It don't know understand why you need to do that , main thing is that only 1 such position is possible after 0-array , so brute force till k , then all will give 1

    for(ll i = 0; i < k ; i++){
         ll cnt = 0;
         for(ll i = 0; i < n; i++){
           if(a[i] == (i+1)) cnt++;
         }
         ans = maxm(ans,cnt+((d-i-1)/2));
         for(ll j = 0 ; j < v[i] ; j++){
              a[j] += 1;
         }
      }
    
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but k is at most 10^9

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

        no , sum of it over all t is given <= 10^5 . re-read the question

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

        No k is <= 10^5

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

        if k were to be 10^9 , then how would it be even possible to take v input

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

      why iterating over first k days will work?? is there any proof of it ?

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

        nah , it FST'ed :( it should've been min(d,max(k,n)) , then it AC

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

I tried to solve B using DP, but got Memory Limit Exceeded at test-case 3, anybody else tried it using recursive DP, or DP?

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

    same bro.

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

    I did it by dp First reverse string s, then we are considering removing from either last or the second last position. Our answer is f(n-2,s[n-1]) f(i,x) = No of unique strings that can be obtained from (s[0:i] + x ) by 0 or more operations f(i,x) = 1 + f(i-1,x) if s[i]==x f(i,x) = 1 + f(i-1,x) + f(i-1,s[i]) — f(i-2,s[i-1]) otherwise subtraction is to avoid double counting

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

    I used recursion, but not DP. First submition failed as I tried to save all possible subsrings https://codeforces.net/contest/1917/submission/238697805. And the next attempt was successfull when I decided just to increment answer https://codeforces.net/contest/1917/submission/238704078

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

    I tried that too I reversed the array and used a stack dp but when I calculated the space complexity I was kinda convinced it would give me MLE so I tried a different approach

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

how to solve 'B'!!!

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

    you can observe something from enumrating the resulting substrings

    hint1
    hint2
    hint3
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for every suffix[i] from n-1 to 0 :

    I erase second character until s[i] is the same as second char. (count += i - last occur of s[i])
    
    I dont use fisrt type operation because the string will be the same as suffix[i+1].
    
    so I just store the position of last occur s[i].

    my submission here

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

      when you are doing

      cnt+= m[j] — i;

      Are you removing the double counts of the same character?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what happens if you submit right answer twice for pre tests?

i submitted D twice to avoid tle later.

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

    Your second submission, and its submission time, is used. You are also penalized as if the first submission was rejected.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone check why my code for C is wrong? I have been staring at it for 1+ hour and couldn't find the problem.

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

    In the last 'for' loop, you are checking for the valid indices only till b[j]+1. You need to check the whole array.

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

      Oh my bad, that was a last 15 seconds desperate attempt, I meant the one before that where I have b[j] instead of b[j]+1.

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

    i think when u added to the first b elements in the array, you checked if an element became "good" meaning that a[i] = i but not if an element is now no longer "good"

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

      Ohhhhh I didn’t check for good elements after b[j]. So sad. Thankss!

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

C is greedy af

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I have skill issue.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem set is crazy :)

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

    Recently all problems sets are very nice.

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

      yes quite intuitive one. ig they want to make special ending for 2023.

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

D always getting wrong answer on pretest 5, what a sad Christmas Eve :(
BTW, could anyone please tell me what's wrong with my code 238736754 ?

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

    Oh I see, forget to take those power of 2 exceeding ±20 into consideration ...

»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Not putting N = 2, K = 2 in the samples of E is cold-hearted lol :P

Also imagine debugging WA on E for 15 mins after "handling" this case just to make this fix and get AC ._.

Image
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't solve $$$C$$$. How to learn to notice all, what needs to be noticed?

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

    You don't need to do so. Its just that after you do a reset operation then you can't get score greater than 1 after any number of operations. So its optimal to take a score of one from first element greedily after doing 1 reset operation

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

      Surprisingly, I noticed this.

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

        Lol I noticed it too and didn't solve C. I tried two +- different ways, but both have WA2 on pretests. I was only 10 points away from CM, sad :(

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

          same stuff happened to me sad

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

      I noticed this too but couldn't implement

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

    How many can you get from first reset op?

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

    Here is my solution by the way, which didn't passed probably because of bug in implementation.

    Fix an element in array $$$a$$$. I want to know, when it is good, i.e. $$$a[i] = i$$$. If $$$a[i] < i$$$, then after some movements on array $$$v$$$ it will become good, then it will become bad forever. Sounds like scanline. Let's calculate for all elements of $$$a$$$ the segment of numbers of operations of type 1 after which the element is good. Process them in decreasing order. Fix $$$i$$$. Then all $$$v[j] \ge i$$$ change element $$$a[i]$$$. I want to know the position in cyclic array $$$v$$$, after which $$$a[i] = i$$$, i.e. I want to know $$$(i-a[i])$$$-th element of array $$$v$$$ with only elements which $$$v[j] \ge i$$$. Assume, they are in some structure. Let there are $$$x$$$ satisfying elements in array $$$v$$$. Then I need to traverse the whole array some number of times, and them some prefix. So I need to be able to find $$$k$$$-th element. I can do it with Cartesian Tree (Декартово Дерево), or with "indexed set" (google "cses.fi Josephus Problem II").

»
11 months ago, # |
  Vote: I like it -17 Vote: I do not like it

div1 difficulty

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

    not actually

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

      more difficult than usual div2 rounds

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

        I don't think I think A,B,C were just like they always are, maybe C was a bit tricky but it's core idea was very easy to notice

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain an approach for C?

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

    My English is not good,in my opinion,the sequence is like stairs,because it can be added to ans when it equals to it position,so every time you do opreation [1,b[i]] +1,it will break the stairs,so if 1-n is 0,only 1 or 0 can be added to your ans after several +1 opreation. To be the best,you can do opration 1 once and do opration 2 once.In this way you can add 1 to ans for two oprations. after understand it,you can make a brute force on array 'a' to Calculate the best ans. it will be allowed on O(n*n) , you can according to my ans 238725053. I Hope i can help you.

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

      Thank you much. I understood your solution) But there is one question. Why do you brute for i <= min(k, d-1). Why not further?

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

        oh god,i'm wrong ans on test 26 Hhhhhhhhhh,i think you need a better person explain for you

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

          Lol)) Anyway, thanks for answering)

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Thank you for spoiling the mood for the new year :(

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Codeforces ------- NO
Speedforces ---- YES

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

    True A and B were speedforces couldn't say the same for rest of the problems

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why we need to check 2*n instead of n in C?

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

    really? how do you know

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

      The max score u can have before 1st reset is n. In 2*n days, using the reset operation u can increase your score by n.

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

    Yes because if it doesn't get give better result in this range there's no way it will give better if it's more since you can increase the score by 1 in 2 steps. I didn't realise that and checked way more than this by throwing and got Ac

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

    Here is a case where checking up to $$$n$$$ fails:

    1
    4 3 6
    2 0 1 2 
    1 4 1
    

    Only optimal solution is doing op 1 five times then op 2.

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

      After doing op1 5 times the array is [7 2 3 4] and doing op2 => answer is 1

      But that is not the optimal solution

      [2 0 1 2]

      op2 => answer = 0 [0 0 0 0]

      op1 => [1 1 1 1]

      op2 => answer = 1 [0 0 0 0]

      op1 => [1 1 1 1]

      op2 => answer = 2 [0 0 0 0]

      op1 => [1 1 1 1]

      Answer is 2

      Did I understood this right?

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

        Doing op2 on array [7 2 3 4] gives 3.

        Op2 counts the number of indices $$$i$$$ where $$$a_i = i$$$, in this case 2 3 4.

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

    more like max(n,k)

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

optimizing knacksap with bitset is uninteresting

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think div2 B should be easier or I'm not participate enough

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

    me too, I felt than C even easier than B.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain why tourist's solution to problem C 238680690 passed the time limit. I think the condition in the for loop is doing the optimization, but I do not understand why.

for (int u = 0; u < d; u++) {
   if (n + (d - 1 - u) / 2 <= ans) {
     break;
   }
   ...
}
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    d can be upto 1e9 which goes way above the constraint

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

    If n + (d - 1 - u) / 2 <= ans then this and the future iterations are useless since they won't improve the answer. And since the initial ans is $$$\frac{d - 1}{2}$$$, any value of $$$u \ge 2n$$$ will be useless. Therefore, this cycle performs at most $$$2n + 1 = \mathcal O(n)$$$ iterations.

»
11 months ago, # |
  Vote: I like it +7 Vote: I do not like it

noting to say, but good night

»
11 months ago, # |
  Vote: I like it -6 Vote: I do not like it

nothing to say, avarage armenian round

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

min(n, k) gave wrong ans so i submited it with k i forget about k = 1e5 after wrong ans test 3 now waiting for fst :( now +60 will turn int0 -60

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

    You don't get FST because $$$k$$$ is large, you get FST because checking the first $$$k$$$ days is not enough.

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

      bro why is there no pretest regarding this. btw thanks for yesterday's contest problems were really interesting even though i didn't get them during contest but i enjoyed during upsolving them

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

E: You are given an even integer n and an integer k

I missed the "even", I would have been able to solve it if I noticed that. Now I think I have a working solution for the odd n. Could have been a nice E1 and E2 problem.

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

    Yes, I didn't think a lot about odd $$$n$$$, but yes it's solvable (check Bonus in the editorial for the problem E)

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

    Ohh What fresh hell is this !!

    Really feels bad when you misread the problem.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For C I have an Idea, You can just keep doing Op1 till you get the max score out of it. Than hit the reset button i.e. do op1 and op2. So finally (mx_score + (d — op1)/2)

And this came after the contest is over. :(

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

    couldnt make this work ( 238728699 ), wasted 2 hours

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

      i mean you need to manually brute force operation 1 for k times. to get this

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

        hm, i do not get why. Please prove?

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

          As the score wouldn't increase more than 1 in 2 ops (doing op1 and then op2) after we have arrived at [0....0] array. So the task is to get the max score until we arrive at this 0 array.

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

            Ah, true, misunderstood your statement

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

            But there was one test case 26 where many people got fst with this approach

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

    I got fst with same approach at test 26. Really hurts bro

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

This contest was OVERKILL for me :(

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me whats wrong with my code for Question B? https://codeforces.net/contest/1917/submission/238702690

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B was tough to understand that the second occurrence wouldn't affect the answer but will be counted.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did my solution to C pass? I don't understand why it works.

»
11 months ago, # |
  Vote: I like it +20 Vote: I do not like it

C became a scam

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with my code for task C? I have WA2 and O(n * log^2 k) asymptotics. 238736328

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You guys were solving B with a set?

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

    simple observation of first and last test cases: in first — aaaaa all chr are same and ans is 5; in last -abcd.... all chr are unique and ans is 210;

    so we can assume that initial ans should be sum of 1,2,3..n, and we need to subtract some value when we have same characters: so first test case ans is 5 (15 — x) x is 10 here right, and for last is 210 — 0. and if you continue you could find this x calculating from similar chr in s

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

      But why my approach do not work for summing up the diff initial char and last occured char using map

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

    I did solve using a set. Code

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

      Yeah there's like a couple hundred (?) copy pasted solutions like this

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

      Could you explain why counting pairs?

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

        Consider the string abcdef.

        I just wrote a tree describing all the possible strings. Something like this:

        .               abcdef                        <- len 6 string
              bcdef               acdef               <- len 5 strings 
         cdef      bdef         cdef      adef        <- len 4 strings 
        def cef  def  bef    def  cef  def   aef      <- len 3 strings
        .......                                       <- .... so on... 
        

        At length 5, cdef is constant. if a and b are the same, then there is only 1 string possible. else 2 strings are possible.

        At length 4, def is constant. If c and b are the same, then there is only 1 string possible. else 2 strings are possible. If c and a are the same, then there is only 1 string possible. else 2 strings are possible.

        At length 3, ef is constant. If d and c are the same, then there is only 1 string possible. else 2 strings are possible. If d and b are the same, then there is only 1 string possible. else 2 strings are possible. If d and a are the same, then there is only 1 string possible. else 2 strings are possible.

        so on...

        Calculate for each length and sum them up in answer.

        PS: Fixing current character and comparing with previous seen characters is what I've considered as pairs.

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

          So we already saw ef then we need to add pairs,

          Then we saw def

          Then cdef

          and so on.

          So your soFar set is describing this phenomena

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

            Yes, for example: at length 4, i=2 current character is c and it's compared with previously seen characters b and a.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats to guys who solved C! And I have a question, can we approach to this problem in this way, so everyday we compare two values: either we choose first option (cnt of all a[i] == i+1) or we go with second option to increase a's values (cnt of a[i]+1 == i+1 for i in range(0, v[day]) and compare this two values. And we implement it to every day. Is this correct approach?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many solutions fsted on C?

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

    They simulate the process from $$$1$$$ to $$$k $$$

    However we should simulate from $$$1$$$ to $$$2n+1$$$

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

      Can you explain why $$$2n + 1$$$?

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

        If we do $$$x$$$ updates before getting the score $$$c$$$ in the $$$x+1$$$th step , the total score is $$$c$$$

        But if we perform the operations normally (for a 0-array) the contribution will be $$$ \lfloor\frac{x}{2}\rfloor$$$

        Than it is optimal to make updates in which $$$n\geq c\geq \lfloor\frac{x}{2}\rfloor$$$

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

      Is it because I would have gained $$$n$$$ points in $$$2n$$$ days if the array were reset to 0. The maximum I can gain from an array is $$$n$$$ points and doing it beyond $$$2n$$$ days is wasteful.

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

    min(2n,d) may be greater than k.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love this round.

I love the super-weak pretest in C, which make me fst.

I love the interesting problems C and D, which made me stuck in implementation and debugging.

I love the random constructive problems taking the place of E and F, which makes the diffculty distribution so unbalanced and weird.

Oh. How I love it.

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

    F is not constructive and implementation of C is very short. About weak pretests, I'm sorry.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you for the weak test cases for problem C.

Now I can reach Expert with the help of FSTs.

By the way, thank you for the awesome round!

»
11 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

I wasted 15 minutes because I put n instead of 2n as the limit of days to use second op in C, but least my n log²n D didn't TLE'd and I'll need to use magic to become purple again :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my color changed twice in 2 contest :D

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not inserting a test into the pretests for one of the most possible error patterns in C is a bad Christmas gift.

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

c

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A to C was fine. but D was too much

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

actually 2n days will give n points so if we waste 2n days then automatically we will get the max value i.e. n so if we are acquring n points after 2n days it is a waste its better that we just do the second operation then

»
11 months ago, # |
  Vote: I like it -32 Vote: I do not like it

worst round ever

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

Merry Christmas everyone!

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for round! Tasks were really cool.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Beautiful problem F! Thanks!

»
11 months ago, # |
Rev. 6   Vote: I like it +8 Vote: I do not like it
I have a different solution for D than the intended one :p, and doesn't use the fact that p is a permutation

Here is my code : 238726631

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C: Checking over the v sequence only once was enough to pass pretest. At least this major corner case should have been included in pretest which is in test no. 26 :(

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell How Problem B can be solved using DP since in the problem itself the tag is mentioned of DP

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

test 26 of problem C is like the grinch :(

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I liked Problem E very much, thanks _LeMur_! I upsolved it. My idea with 6 was following: if k is small, then print the diamond of 6 ones on the first 3 lines of matrix, then fill squares of 2x2 on the following lines. And symmetrically opposite: if k is large, then subtract k = n*n - k, and do the same with inverted bytes.

Somehow my Perl code is running notably fast. Submission — 238764454.

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

    Problem E-bonus (n can be odd):

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

      Yes, Nice! It's correct. I am happy that you liked the problem :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

C is really good but i didnt solve it during the match TwT

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone tell me the problem in my code for problemm D: submission link: https://codeforces.net/contest/1917/submission/238781581

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys,my rating for recent educational round was taken back.Is there anyone who is having the same problem?

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

    That's because you cheated the contest ...

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

      It seems the same incident happened for you.Have you received the email of plagiarism detection too?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it