Vladosiya's blog

By Vladosiya, history, 13 months ago, translation, In English

Hello! Codeforces Round 913 (Div. 3) will start at Dec/05/2023 17:45 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by pashka, MikeMirzayanov and me.

Part of the problems in this round were in the Cyprus Programming Challenge. If you participated in it, please refrain from participating in this round.

We would like to thank:

  1. peltorator, FairyWinx for red testing.
  2. Vladithur, Valters07 for yellow testing.
  3. stefanbalaz2, FBI, SlavicG, flamestorm, SashaT9, mesanu, trainerherp, Ush1su for purple testing.
  4. dan_dolmatov, Yousef.Osama for blue testing.
  5. Sergey140146659, Pa_sha, gas for cyan testing.

Good luck!

UPD: Editorial

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

| Write comment?
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

hoping to return back the blue handle

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

I hope to be the statements short.. i think this better

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

    Yea I hate long statements usually problem setters try to make the problem in to a story and just extend it by 2 paragraphs which is annoying

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

Tomorrow is my birthday, and I hope to perform well in the contest. Wishing success for everyone.

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

hope problems are interesting .....

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

First time testing :D Good luck to all!!

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

It's been a while since the last contest written by pashka, glad to see him.

»
13 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Inshaallah, In this round I will be Green.

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

My first unofficial Div.3 contest! Hope it will be fun and good luck to everyone!

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

I hope statements are short and legible :D

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

I don't know why I'm not included, but it's my first time testing :D

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

As a tester, I enjoyed the problems, and I hope that you will enjoy them too

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

As a tester, I can say that problems are very interesting

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it
  • Wow Bashka, Mike Mirzayanov contributed to the problems... I'm so excited
»
13 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I might end up in top 100 in this contest.

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

I was wondering, why is that on some rounds (mostly educationals) the number of the problems isn't announced? Surely, authors know the number at least a day before the contest begins, and it's pretty inconvinient for the participants to not know that number (myself and I'm sure many others like to make files for the problems before the contest)

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

Will the round be delayed if this queue continue ?

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

Why is the round delayed by 10 mins?

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

Hope to become expert.

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

Again! one refresh cost me ten minutes

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

if you open author list of this contest using dark reader, you end up with a color scheme of russian flag

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

What are you doing during the few minutes of the contest delay,it is so suffering

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

what does it mean — to be an any color tester?

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

Nice

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

why do i get HTTP Status 403 — Forbidden error after refreshing the page during a contest ? How do i get rid of it ?

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

cool problem G!

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

    How to solve it ?

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

      Let's construct the graph corresponding to. If we have a vertex of degree exactly $$$1$$$, then we either exactly take the edge coming from it, or exactly do not take this edge. We can do this one by one. Then we can prove that the remaining graph is a union of non-intersecting simple cycles. The solution for each of them is approximately the same. Let the cycle $$$v_1 v_2 ... v_k$$$. We have two cases: whether we take the edge $$$v_1 v_2$$$ or not. Each of the two cases is solved in the same way as the first part (if we take it, for example, then all other operations that are necessary are recovered uniquely).

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

hardest div3c I've ever seen.

regular greedy approach simply not hold.

I'm losing hope in cp

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

    yeah i stuck at this problem for entire contest :(

    any idea for this problem?

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

      what if a majority of the characters is equal to the same character? what if not?

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

        how did you come to this idea?

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

          randomly trying stuff.

          If I'm being honest, I found C harder than G...

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

            If I had to improve on such problems, which topics should I practice?

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

              There aren't really any "topics" to practise. Instead, you should just solve a lot of div2B-level problems which often revolve around this sort of idea.

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

          look at his colour ;)

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

      I tried a solution of keep sorting the count array (Of 26 characters) and if I still can find the smallest and biggest count (Both are distinct and > 0), I will decrement them each by 1 unit

      After that I just add all the remaining counts

      It got accepted, I felt so dumb because I didn't try it during the contest lol

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

My thought process of G: build graph i-ai. pressing a switch is flipping endpoints of an edge. each op is xor which is associative so order doesn't matter and no switch will be flipped twice so op is delete an edge and flip its endpoints.start with leafs. corresponding edges are fixed. we are left with a bunch of loops. now what ?? even no of 1s should be present in a loop. 2 possible ways of pairing find the min one.

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

Why does my solution for problem D not work? Any help is appreciated.

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

    If you're sure that your binsearch is correct, then probably you haven't looked through all cases on how 2 slices can be related to each other(I found 6 separate cases)

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

      don't the 6 cases degenerate into:

      l = max(l — k, l2) and r = min(r + k, r2)

      where [r, l] are the current valid range and [r2, l2] are the one we're checking to see if this k is valid.

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

        Idk, I looked through 6 cases just to be sure. It doesn't take much time tho. But you're kinda right

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

          I assume that means you passed? In which case congrats, mine didn't :^(. Clearly some edge case I'm not thinking of, shouldn't have been lazy. Please share your submission, if so.

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

            You can see it, they're open now

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

    1 10 0 17 7 9 8 14 14 19 5 8 2 14 11 14 2 16 2 2 7 9

    Doesn't work on your code

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

How to do problem e?

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

    Solution for n is the product of no of solutions for each digit of n. (So you only need to solve from 0 to 9)

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

      Why is that? Could you explain please?

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

        Since the sum of number and sum of digits is same. Let's say you change sum of digits on ith place by 1 then change in sum of numbers is 10^i. If you compensate this change in sum of digits at other place j then change would be -10^j. Net sum would be 0 iff i = j

        For a general change in sum of digits you can view changes as numbers in base 10.

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

        if sum of three didgits of the same rank >= 10, then the sum of digits of a, b, c > sum of digits of n, since n can contain only 8 digits

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

        There is a bijection between the partitions of each digit of n into a sum of 3 numbers and the solution to the given problem. For Example n=26, the corresponding partitions are [[{0,1,1},{2,0,0}(and their permutations)],[{1,5,0},{2,3,1},{6,0,0},{2,4,0},{1,4,1},{2,2,2}(and their permutations)]]. Combining say {0,1,1} and {1,4,1} corresponds to a=01,b=14,c=11 and the tuple (01,14,11) for the solution.

        Basically, the intuition is that we need a+b+c=n to hold in each decimal position as well for the digital sum property to hold. As a consequence, there must be no "carry-overs" while performing the addition a+b+c

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

Is G something like topo sort? My idea was to use topo sort until the remaining switches are in cycles, then see if every cycle has an even number of on switches. If so, then we are good.

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

    how did u find this, like how do u find the same problem in general?

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

      it just happened that I had seen this before

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

    This ARC B is much easier than current one because all numbers are distinct and also it is guaranteed that operation exist.

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

C ruined the experience

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

    235953756 Can't find the bug for code in C :(

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

      what's idea of this solution

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

        The idea is basically from finding 2-majority element of a array without hashing,

        I am basically first storing the count of each charater occurance in hash array.

        After that, we lets define a process to reach minimum length which will be :-

        (We will take the current majority character x in string and we will remove any pair x adjacent to non-x in string.)

        if there is 2-majority element in array(if a element occured >= n/2 times), It will remain 2-majority after any no. of processes.

        else if there is not any 2- mojority element in array. After some no. or processes, if string length is odd than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that. if string length is even than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that.

        So, execute the process we defined on string and you will reach the answer after some analysis.(the solution I mentioned may seem tough to understand but it is simple when you will understand)

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

      I think it's because of vector of char instead of vector of int

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

      The above comment is true — it's because of the vector.

      Char is in range of [-128, 127] I believe, and the string can be up to 2e5, so if any character appears more than 127 times, char will overflow.

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

Hints for problem E? Thanks.

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

    try to observe a pattern in the given test cases. There is simple formula hidden

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

Solved F 20 minutes after the contest ended.

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

At first I thought G is 2-SAT. LOL

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

I couldn't solve $$$C$$$ , have I really gotten that dumb!!!

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

    Relax, I've solved the EFGA problems :)

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

    don't worry, I took at least 15min to mind-solve it and even then it was just trying random approaches until I found one that worked (then I proved it, of course). And I'm a master...

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

      Hey, Can you just prove your solution for C

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

        First assume that n is even. Then I claim that the answer is 0 if no character occurs more than n/2 times, and maxcnt-(n-maxcnt) = 2 * maxcnt — n otherwise where maxcnt is maximum number of occurrences of any character.

        In the second case, we can see that the last remaining character is necessarily the one that occurs the most times, since it's impossible to remove all of them. (you can remove at most one per operation, and at most n/2 operations are performed so there's no way to remove all of them. The number of operations performed is bounded by the number of characters not equal to this most common character, which is n-maxcnt implying that at most 2*n-2*maxcnt characters can be removed. So the length is at least n-(2*n-2*maxcnt)=2*maxcnt — n. I claim that this can be achieved. Method: always try to remove exactly one non-most-common character per operation. This can always be done by choosing an occurrence of the most common character and one non-most-common character — it will always exist until all characters are made equal, at which point the length is 2*maxcnt-n.

        We can show the first case by induction.

        • Base case: n=2 then s1!=s2, then we can make the length 0.
        • Inductive step: suppose it's true for n-2, now prove for n: we claim it is possible to remove characters so that no character occurs more than (n-2)/2 times in the remaining string. Take the most common character and remove it with any other character. In this way we can see that the condition is satisfied with the remaining string and we can continue until the string is empty.

        When n is odd, the reasoning is similar, but since the parity of the length is constant, replace "0" by "1" in the above.

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

          For the case when n is odd, it is not true that removing a most frequent character with any other character will result in a string with no characters occuring more than (n-2)/2 times. Example: s="aaabccc". In fact, the end case 1 is in itself a counterexample. Fortunately, this only happens when the string has only 3 unique characters with first and second most frequent characters having the same frequency and third character having frequency of 1. This means that the final remaining string will also be of length 1. Moreover, the end case 1 suggests that this special case always occurs during removal of pairs under this algorithm.

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

        You can always remove a pair which contains the most frequent letter, as long as all the letters are not the same...

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

It's my first time to complete 4. Can I turn green?

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

    nope ig , you are having delta +105

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

      I'm confused,what “delt+105”?

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

        Delta is a word used in physics to describe small changes. In CP it is used to describe rating changes. Delta +105 therefore means your rating increased by 105

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

          I see.But how he can predict my delta so accurately? I thought this was calculated randomly based on rankings.

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

            codeforces uses a rating system similiar to the chess elo system. Meaning they have a formula to calculate rating changes deterministically.

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

      can you check my delta?

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

F implementation was tricky

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

it would have been interesting if e would have been not for triplets but n-plets (basically for n numbers rather than 3 numbers).

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

did any one else solve problem F using Hashing ?

my solution

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

    can u pls explain ur solution, I am new to using hashing for strings in cp

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

      I suggest you read This blog, it will give you details about hash functions.

      Here am using hashing to simulate the process of shifting in O(1) instead of O(n) , I achieve this by changing the current hash value in each iteration from :

      currhash = ( a[0]*A^n + a[1]*A^n-1 + a[2]*A^n-2 +..... a[n]*A )%p

      To :

      currhash = ( a[n]*A^n + a[0]*A^n-1 + a[1]*A^n-2 +..... a[n-1]*A )%p

      i.e currhash = (currhash // A — a[n]) + a[n]*pow(A,n,p) )%p

      you can easily see how thats done in my code (using modular inverse and modular exponentiation) . The rest is just checking if the currhash matches the sorted (in ascending or descending order) array hash value.

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

    Nice idea!

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

Can someone please explain problem D, how BS is working there?

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

    [x,y] means interval from (inclusive) x to (inclusive) y.

    We have to jump into these intervals: [0,0] -> [1,5] -> [3,4] -> [5,6] -> [8,10] -> [0,1]

    We can check if this works if we fix k=3:

    [0,0] -> [-3,3] //we can jump anywhere here

    [-3,3] & [1,5] = [1,3] //this is the overlap. We can be anywhere here

    [1,3] -> [-2,6] //we can jump anywhere here

    [-2,6] & [3,4] = [3,4] //we can be anywhere here

    [3,4] -> [0,7] //we can jump anywhere here

    [-0,7] & [8,10] = [ERROR] //we have no overlap and nowhere to jump. K=3 does not work!

    Code:

    bool good(int k, vector<pii> &segs){
        pair<int, int> current = make_pair(0,0);
        for (int i = 0; i < segs.size(); i++){
            current = make_pair(current.first-k, current.second+k); //we can jump anywhere here
            if(segs[i].first > current.second) return false; //no overlap
            if(segs[i].second < current.first) return false; //no overlap
            current = make_pair(max(current.first, segs[i].first), min(current.second, segs[i].second)); //we can be anywhere here
        }
        
        return true;
    }
    
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks a lot for your explanation, bro! I knew this problem was BS but for a value k = mid, I couldn't figure out how we can win the game with k = mid or not.

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

      Thanks brother, it helped me to find how to use mid,

      Updating current to possible range is where i got confused, urs is Very good logic

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

Either brain's not braining or found the problem D much harder that usual don't know why...

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

How to solve G?

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

    Construct the graph $$$i \rightarrow A[i]$$$, this type of graph is well known (Functional Graph). An important property is that it consist of several cycles and nodes that following the directed edges reach some cycle. So obviously if there is a 1 on a leaf you have to change it and switch the next node. In the end you will only have cycles left, some nodes will have 0 others 1. If the number of 1's in a cycle is odd, then it's impossible. Otherwise let $$$A_1, A_2, \ldots , A_{2k}$$$ the nodes that have 1, then you have two ways to convert them to 0. Grouping $$$(A_1, A_2), (A_3, A_4), \ldots , (A_{2k-1}, A_{2k})$$$ or $$$(A_2, A_3), (A_4, A_5), \ldots, (A_{2k}, A_1)$$$. Choose the one that minimize the changes.

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

    Another way of doing it is by considering an undirected graph with edges $$$i \leftrightarrow a_{i}$$$. Now solve for each connected component individually. Notice that each connected component is a tree with one extra edge because there are $$$m$$$ nodes and $$$m$$$ edges, where $$$m$$$ is the size of the component. Try both using the extra edge or ignoring it. Now the problem becomes turning off all the lights in the tree, which we can just do using dfs.

    Submission

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

      Almost did it during the round, but didn't spot the trees and tried to find shortest paths to connect 1's instead

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

      Could you explain the code a little more in detail please ?

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

        We iterate over all the nodes. If $$$vis_{i}$$$ is true, we already processed the component containing node $$$i$$$. The first dfs call flips all the necessary nodes from the bottom of the tree upwards, and also finds the extra edge. Before the second call, we use the extra edge, flipping the two lights associated with it, then run dfs again to see if using the extra edge requires less flips.

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

C>D>B>E>A

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

anyone finding Div3.D harder than usual ?

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

    I found it on easier side than usual, no dynamic programming problem was there also generally there's a question of tree data structure which wasn't.

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

    Question E is the simplest

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

      Explain please how I am confused.

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

        When adding to the digits of these three numbers, it is impossible to generate carry operations. Knowing this, writing code only takes 5 minutes

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

          How did the combinatorics part work?

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

            If a low position generates a carry operations. So the missing digits sum need to be filled in at the high position, but increasing the digit at the high position will increase the sum of these three digits, making it impossible for the sum of the three numbers equal to be N

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

I think that the solution of problem B has been widely shared by cheaters. Here are some examples :

235939705 235936558 235937575 235905766

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

Nice contest! Problems very really good. Thanks a lot for the round Vladosiya pashka MikeMirzayanov and all testers.

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

This is a genuine plea for help, I have no idea how to approach problems like 1907C - Removal of Unattractive Pairs. The first thing my mind tries is a greedy approach, doesn't help, maybe check for DP, still no use. How do you develop the intuition to solve these type of problems, or even more fundamentally, how do we even approach these types of problems, when nothing else matters except a few observations that perhaps never strike you during the contest?

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

    I just saw that if we want to remove the letter with the highest count then pairing it with 2nd highest letter will be beneficial.... that's why I use set to maintain the order of letters on the basis of their count ... I pick the last and second last and delete them and the update them and reinsert it and this will cost log(n) and do this till the size of the set is greater then 1. we will do this for n/2 element so, TC will be nlogn. 235912384 there is math solution also but I come up with this one during contest

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

      Your solution always gives the correct answer, but the reasoning is incorrect: it's not always possible to remove two characters with largest and second largest frequency (remember that you need to remove two adjacent characters):

      $$$\mathrm{acbdaeb}$$$

      • $$$\mathrm{cnt_a} = 2$$$
      • $$$\mathrm{cnt_b} = 2$$$
      • $$$\mathrm{cnt_c} = 1$$$
      • $$$\mathrm{cnt_d} = 1$$$
      • $$$\mathrm{cnt_e} = 1$$$

      The most frequent characters are $$$\mathrm{a}$$$ and $$$\mathrm{b}$$$, but you can't remove both with one operation. This turns out to not matter: it's enough to remove the most frequent character with any other character unless the frequency of the second largest character is $$$\left\lfloor\mathrm{len}/2\right\rfloor$$$, in which case we definitely can remove the most frequent and second most frequent characters at once.

      upd: there are actually some other cases I missed but the main idea is still there.

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

      As adjacency of elements doesn't matter, to remove the element with the maximum count, we need the same amount of other elements, so the answer is the difference between the count of the maximum occurring character and the count of other elements. If the difference is less than or equal to 0, then we give the output as 0 in the case of an even-length string or 1 in the case of an odd-length string; otherwise, the answer is the mentioned difference.

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

    I have noticed that you can transform the string in a compression of it, example: "aaabbc" is converted to 3 2 1,then the new problem is given an array you can rest 1 to an adjacent pair of numbers any number of times and if a number become 0 remove it and refill the space and this new problem look easier for me to solve.

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

      I thought of this too but then consider the test case: vvcvvv. You will compress this to 2,1,3. However, the 2 and 3 cannot reduce each other since they are both instances of v. This is where I faced issue with my greedy approach. I do not know how to account for the fact that after some operations, 2 numbers in the array will become adjacent but they carry the same letter so they cannot reduce each other.

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

        of course the first observation to do is if a character appear more n/2 then you can delete all the others chars with an instace of it an the remaining ones will be the answer

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

        You just have to count the letters. Like a frequency list of size 26. Cuz the order of the letters doesn't matter. vvcvvv -> 0 0 1 ... 5 ...

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

          Cuz the order of the letters doesn't matter.

          You're correct, but can you explain why that is true? On first glance it seems like it would matter as we're removing adjacent characters.

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

            Is it even obvious after many glances? One would be tempted to say so since nearly 5000 people solved the problem but it just doesn't seem like the kind of fact that would jump at you, even if you stared hard enough.

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

              It most definitely isn't obvious to me; even I guessed that it just works during the contest. I believe I would be able to prove it now, but it seems quite annoying.

              Me guessing the solution was the combination of "I had seen similar problems before with similar solutions, this feels correct" and "this is D3C, the solution is probably very simple". Even though guessing isn't generally considered a proper way of solving problems, with strong enough intuition it might be more optimal than proving solutions in modern CF contests.

              Is this a sign that the current problem style is bad? I'm not sure, but this should probably be discussed more.

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

              think of it this way, you can always pair one highest frequency letter with another letter, unless only one type of letter remains(the highest frequency letter will have to border another letter). So the order doesnt matter

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

                But if we consider the test case presented earlier by vgtcross: acbdaeb, we see that the two highest frequency characters a and b turn out to not be adjacent to each other at all. So reducing both their frequencies by 1 is sort of a false move, since a and b can't reduce each other. Sure, you can always reduce the frequency of the highest letter, but it doesn't always end up being reduced with the second-highest frequency letter (which ironically turns out to be the correct greedy solution in the end).

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

                  no, i meant pair (any) of the highest frequency letters at that moment with any other letter adjacent to it. you can always do this until you're left with nothing, or a string with a unique character(so you're not necessarily reducing it with the one with second highest frequency)

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

                I think focusing on the highest frequency letter is more confusing than not : - you can always pair any letter with another letter except if this letter is the only letter.

                Using this fact, the "order doesn't matter" property come in an easier way.

                Then then question is, when do we have letters that are left and the highest frequency letter come in.

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

                  yeah that's it

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

                  This is not true, you need to pick the highest frequency letter, otherwise from aaabc you can end up at aaa, which is a wrong answer.

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

                  That is not what my message above is saying.

                  What it is saying is that you can basically always pick which letter you want and choose to delete it except if its the only letter. It does not say that your choice will be in the optimal answer.

                  So when you find that the letter that you want is indeed the highest frequency letter, you don't have think about IF at any moment, you will not be able to delete it. With the observation above, you know that you will ALWAYS BE ABLE TO.

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

                  That is also not true. Basically you are saying that in abaca, I will be able to pair b and c, delete them and end up with aaa, but that is not the case.

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

                  No, I'm saying that you can pick 'a', 'b', or 'c' and choose to delete it. It will be deleted with an other unknown letter but it is guaranteed that you will always be able to delete the one letter you choose.

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

    А possible logical chain:

    1) In final string you can't make any operation, since it's the shortest possible achievable string.

    2) => In final string $$$s_1 = s_2, s_2 = s_3, \ldots, s_{k-1} = s_k$$$. I.e all symbols are equal in final string.

    3) Quite intuitive thing to do is try to bruteforce that "final symbol".

    4) Then you can see than until there is at least two different letters and at least one "final symbol", than there is an adjacent pair of symbols, one of which is "final symbol" and one of which is not. It's like a simple application of that classic obvious lemma: if there is a binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10".

    From now it's more or less obvious what's next to do (I believe)

    Steps 1, 2, 3 seems very logical to me. Maybe step 4 can be seen like an "observation", but this "lemma" about "binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10"" is way too classical, and it is an easily recognizable pattern after you seen this some number of times. So it all comes down to "solve more problems to be able to quickly recognize such patterns", who could have guessed

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

    FWIW, I'd like to point out that the DP approach for C does work, although it's not efficient (time complexity $$$O(n^3))$$$. But solving it using DP in $$$O(n^3)$$$ is still a good learning exercise, as you might find transitions difficult if you are accustomed to thinking about DP problems in a certain manner, owing to the fact that the neighbors are joined together after deletion of inner elements. I suggest people comfortable with DP to try this out.

    For example, you might define $$$dp[i][j]$$$ as the minimum number of characters remaining at the end when we are only dealing with $$$str[i...j]$$$. Then, you might try collapsing the first pair, say starting at index $$$x$$$. However, there's no way to proceed now because $$$dp[i][x - 1]$$$ and $$$dp[x + 1][j]$$$ cannot be combined.

    The Trick

    Submission

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

I wanted help with problem C please, it is failing in test case 2

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

    maybe, show the code could help make the problem more clear?

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

    Well, I read your submission just now. As I'm not a native English speaker, if I say something confusing, please tell me. I thought you use recursion to delete characters until nothing can be deleted. Firstly, even if you writed the code well and didn't get a WA, this code could be made TLE because it's O(n^2). So it's not a correct solution for this problem. Secondly, your strategy of deleting is wrong. Let's think about such a string: "bbaebbaecccccccc". It's length is 16 and the answer is 0. However, your code will give the answer 6, which is wrong. because once it find a pair of different adjacent characters after same characters, it deletes them. For examples, it delete 3rd and 4th characters which are 'a' and 'e'. But it's possible that we don't delete them right now but later. Actually, to reach the answer zero,we delete the middle two chracters each time. So one correct way to solve the problem is to delete the characters which is the most numerous in the string right now with a character different with and adjacent to it. Obviously, when we can't do this, we can print the answer. You can use priority_queue (heap) to do this in O(nlogn). A better way is not to simulate the deletion process, just count the number of each letters and then print the answer, which is O(n). Here is my code: https://codeforces.net/contest/1907/submission/235898166

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

    What's more, it's usually not a good idea to use vector(bool) due to some historical reasons. Try to use bitset instead.

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

Was this round rated? Why is it showing unrated?

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

Why does my solution give TLE for problem B

https://codeforces.net/contest/1907/submission/235957135

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

    The statement ans = ans + str[i] takes O(n) time where n is the length of ans so actually your solution works in O(n^2). You have to change it to ans.push_back(str[i[) and it will work fine

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

    ans=str[i]+ans; this operating is costly as every time you add new char at the beginning of the string it takes O(size of string) time. instead of doing this you can insert the char at end of the string and after all the operation just reverse the string 236009502

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

Who understands the pain of not being able to load in 20 minutes at the beginning of the competition? I've never been stuck for so long before.

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

pls explain problem E. Thank you

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

    How I solved it, although I'm not sure if I explain it well enough.

    Hint
    The main idea

    I hope this makes sense, lol.

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

why didn't the submission 235883526 solution not work for 1907B - YetnotherrokenKeoard (problem B)? was it because of memory copy?

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

    ans = str[i] + ans

    This works in O(|ans|) which overall is O(n^2)

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

why it is so late to publish ratings nowadays?

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

After 10 contests, I'm finally green!

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

wow

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

Good evening, Everyone (including system).MikeMirzayanov I have just recieved a notification regarding my submission number https://codeforces.net/contest/1907/problem/D for my solution coinciding with others. You can clearly see the name of functions been created to be obvious for the answer and also you can see the trademark of my solution to be genuine on the top. You can verify all of this from any of my submissions from the past few months. You can also go through my style of using the variables and functions from any of my previous submissions. It can be a coincidence as the functions and variables I use are very common among competitive coders but I am sure about my solution being genuine and completely self thought. Thank You
Mukul457 Some of my previous submissions-: https://codeforces.net/contest/1688/submission/217835352 (8 Aug 2023) https://codeforces.net/contest/1207/submission/220195657 (24 Aug 2023) https://codeforces.net/contest/1714/submission/226328908 (2 Oct 2023) https://codeforces.net/contest/31/submission/228841576 (19 Oct 2023) https://codeforces.net/contest/1869/submission/222855817 (11 Sep 2023)

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

NIce contest

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

Why in this contest. I had rank 3xxx and got rating 500, but my friend had rank like 11k and got 620 rating ?

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

May someone please see my latest solution of question B and tell me why is it giving TLE on 3rd testcase even though it's complexity is of order O(N). People even have O(NlogN) solution then why its giving TLE in mine.