By BledDest, history, 11 months ago, translation, In English

Hello Codeforces!

On Jul/27/2023 17:35 (Moscow time) Educational Codeforces Round 152 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space
WORK & STUDY OPPORTUNITY IN BARCELONA @HARBOUR.SPACE UNIVERSITY

Harbour.Space University has partnered with Giga (Unicef) to offer Bachelor's and Master’s degree scholarships in the fields of Data Science, Computer Science and Front-end Development as well as work experience.

We are looking for various junior to mid level candidates:

Data Scientist:

  • Strong ML knowledge
  • Experience with Data Visualization Tools like matplotlib, ggplot, d3.js., Tableau that help to visually encode data
  • Excellent Communication Skills – it is incredibly important to describe findings to a technical and non-technical audience.
  • Strong Software Engineering Background
  • Hands-on experience with data science tools
  • Problem-solving aptitude
  • Analytical mind and great business sense
  • Degree in Computer Science, Engineering or relevant field is preferred

Data Analyst:

  • Cleansing and preparing data
  • Analyzing and exploring data
  • Expertise in statistics
  • Analyzing and visualizing data
  • Reports and dashboards
  • Communication and writing
  • Expertise in the domain
  • Solution-oriented

Front-end Developer:

This student will work closely with the blockchain developer and product lead to contribute to the design and implementation of user interfaces for the company's blockchain-based prototypes. They will be responsible for translating UI/UX design wireframes into functional and visually appealing web applications, ensuring seamless user experiences. The student will collaborate with blockchain and backend developers and designers to integrate front-end components with server-side logic and optimize application performance. They will also be involved in testing, debugging, and maintaining the front-end codebase. The intern will have the opportunity to gain practical experience in front-end development within the context of blockchain technology and contribute to the Giga’s mission of connecting schools to the internet.

  • Solid understanding of HTML, CSS, and JavaScript
  • Familiarity with front-end frameworks and tools such as React or Vue.js.
  • Strong problem-solving skills, attention to detail, and a passion for creating intuitive user interfaces are essential

Full Stack Developer:

  • Interest and experience in web application development, data products and OpenAPIs
  • Comfortable with on-cloud deployment services (preferably Azure), Git and CI/CD pipeline and deployment processes
  • Experience with open-source projects is highly preferred

All successful applicants will be eligible for a 100% tuition fee scholarship (29.900 €/year) provided by the partner company.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

You will complete 15 modules (each three weeks long) in one year. Daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/day

Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

REQUIREMENTS:

  • Industry experience
  • International exposure
  • Eager to learn
  • Sustainability is a key topic for you
  • You want to work for an NGO
Apply Now →

UPD: The editorial has been published.

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

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

In the post title (рейтинговый для == Rated for), It seems that the Russian words is rather long.. lol:)

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

    Fixed, thank you

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

      Рейтинговый для the participants, this is genialno

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

        Sorry, I don't understand what you're talking about. Could you show me where this phrase is used?

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

Let's take some education from Educational :)

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

I think I will be educated by Educational Round :(

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

orz

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

Hoping to cross 1300 mark

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

I am the coolest and the bestest ^^

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

i think it will cool contest =)

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

I'm really looking forward to today's game.

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

Hope I can become candidate master today!

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

Another chance for solving interesting problems

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

Hope problem statements will be as short as blog.

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

could smbd tell me, what does "orz" mean?

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

    It's just like a man Kneel in worship of someone

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

      well, then i dont understand why to write it hmm... ABOUT EVERYWHERE "stranger things"

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

Thank you for this contest :)

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

hope I can be a master

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

kinda random but can anyone help me https://codeforces.com/contest/469/submission/215875468 why this solution is not tle

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

I am going to have my first Div.2 round!!!

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

I have 185 points to Candidate Master. Good Luck. Hope to get more rating.

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

WA on 2 forces :/

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

Hello, Someone logged into my account, I recieved a message about an hour ago but I just noticed, it was not me I just changed the password. Please don't mistake this for cheating, they might have copied my code.

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

is this round rated for Div.1 as they are appearing in the official standings list?

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

Problems are good, I like them. But unfortunately, I didn't solve the problem E. Can someone provide a solution to the problem E?

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

It seems that my solution for F is an overkill (wow, this never happened before on ERs, right?..), so I would like the participants that solved it to share their approaches. The one approach I'm most interested in is binary search with building an implicit graph and checking that it's bipartite: I had a similar idea when I designed the problem, but the details of handling that graph were a big mess, so I decided to go with a completely different approach. How to check that the cost of the partition is $$$\ge m$$$ easily?

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

    The main observation is that if $$$x<y<z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$. Proof: Define $$$f_i(n)$$$ to be the $$$i$$$-th bit of $$$n$$$. Let $$$i$$$ be the most significant bit of $$$x\oplus z$$$, then every bit higher than the $$$i$$$-th bit of $$$x,y,z$$$ must be equal, and $$$f_i(x)=0$$$, $$$f_i(z)=1$$$. If $$$f_i(y)=0$$$ then $$$x\oplus y<x\oplus z$$$, otherwise $$$y\oplus z<x\oplus z$$$.

    Using this idea, we can prove that if $$$b_1<b_2<b_3<b_4<b_5$$$, then the edge between $$$b_1$$$ and $$$b_5$$$ are useless, because if we have this edge, we already have a triangle ($$$b_1,b_2,b_3$$$ or $$$b_3,b_4,b_5$$$). So there are only $$$O(n)$$$ useful edges.

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

    I tried using a bit trie to do the binary search. Suppose you want >= m, then you can build the graph implicitly by doing the following bfs. You take a current node u, and then use your bittrie to take all values arr[x] such that arr[u]&arr[x] < m, then remove those x you used and add them to your queue. In this way you will prevent n^2 edges and get an implicit forest. Now that you have 2 different partitions, and check your check both of them to make sure their minxor >= m. At first, I tried using a bitTrie to do the checking as well but that TLEs, turns out the approach of sorting and checking adjacent elements as pointed out above will make it fast enough to pass. Also, I had to do alot of constant optimisation to make it work (recursive calls are too slow and pointer based bit trie is also too slow)

    Submission: https://codeforces.com/contest/1849/submission/215997707

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

      I have this approach too, but it runs in < 2 seconds and i only made one optimization from my previous TLE solution

      216109677

      Building the trie once is sufficient for all calls to check() since when you process node x, it is sufficient to find the logA important nodes of the trie which are the opposite color and mark them so you don't process them again. But since all you do in a check function is "remove" elements of a from the trie the first build is sufficient — just reset marked nodes for each call to check().

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

    This is what I did.

    First observation $$$x < y < z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$

    Let's binary search on the maximum possible value.
    So the problem reduces to checking whether a possible partition exists with the cost of both sets $$$\ge M$$$?

    Iterate nos in sorted order. $$$dp[i][j]$$$ is true if it is possible to partition $$$a[1....i]$$$ (where $$$j<i$$$) such that the largest element in one set is at index $$$i$$$ and the largest element in other set is at index $$$j$$$, and false otherwise.

    We can remove one dimension from this dp, letting $$$dp2[i]$$$ denote the smallest possible $$$j$$$, such that $$$dp[i][j]$$$ is true.

    Once we know $$$dp2[i]$$$. $$$dp2[i+1]$$$ is either equal to $$$i$$$ or $$$dp2[i]$$$. So I first checked if it is possible to assign $$$dp2[i+1] = dp2[i]$$$, then I checked if $$$dp2[i+1]=i$$$, otherwise returned it is impossible to create such a partition.

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

    My solution does not construct a graph, but I guess it's one of the easiest for this problem.

    Let's try to check if the 29-th bit is "on" in the answer. One can see that this can hold only if $$$n$$$ is not greater than 4. If $$$n$$$ is greater than 4, then it means that there're atleast 3 numbers whose 29-th bit is on/off, but number of groups is only 2 => their xor will be smaller than $$$2^{29}$$$.

    If $$$n$$$ is not greater than 4, you can easily write a brute force and choose the best option. Otherwise, the answer is smaller than $$$2^{29}$$$. Let's notice that if 29-th bit is "on" in $$$x$$$ and isn't in $$$y$$$, then $$$x \oplus y$$$ is not smaller than $$$2^{29}$$$.

    After this obsevation you can easily come up with the full solution: if $$$n$$$ is not greater than 4, then write a brute force. Otherwise, solve recursievly for number's whose (29, 28, 27..)-th bit is on/off.

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

The problems are nice, but horrible samples and queue issues

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

    Had to wait a few minutes after each submission just to see WA on test 2.

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

The problems were good. It made me use my brain!!

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

I felt D was easier than A, didn't try B, C

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

I think the authors did a great job, I'm very fond of the problem set.

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

Is C solvable with polynomial string hashing? Comparing at most $$$m = 2 \cdot 10^5$$$ hashes by storing them in a set doesn't seem as an unreasonable approach.

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

    Yeah. Submission

    Just use two hashes. "If hash isn't working, it's because you haven't done enough of them"

    I only now realized there is a 12 hour hacking phase. Well, feel free to hack this :(

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

      I also used hashing, with $$$h(s) = \sum_{i=0}^{n-1} 2^i \cdot s_i$$$.

      Even if my hash function is terrible, my out $$$\leq$$$ actual answer, but it fails while giving the output $$$=$$$ actual $$$+1$$$.

      this is my submission.

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

        Collisions in this problem will decrease the answer, since two different strings may be mapped into one value. However, there are other problems with your implementation, mainly on this line: hash = (h[l - 1] + h[n] - h[r] + (mod2[r] - mod2[r - c]) + mod) % mod;

        Here, I see two problems:

        1. using int may result in an overflow inside the paranthesis (which in this case I expected to produce two values for the same string, and your ans should be $$$>$$$ the real ans).

        2. whats inside the parenthesis could be, for example, $$$0 + 0 - 1 + (0 - 1e9+7) + (1e9+7) = -1$$$ and when you take mod, since $$$-1 \,\,(\textrm{mod}\, 1e9 + 7) \,= -1$$$, not $$$1e9 + 6$$$ (using the standard % operation)

        Fixing these two issues (submission) gives WA on Test 4. This test consists of a string of size 2e5. Since the real answer is $$$136468$$$, the expected number of collisions will be approx. $$$\frac{136468^2}{2 \times 10^9} \approx 9$$$. Thus, the answer we get, $$$136460$$$, seems reasonable.

        We could also use ull ($$$2^{64}$$$ mod) hashing, it could easily be broken, although I suspect the setters didn't bother creating a testcase to break it.

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

          Here, I see two problems:

          Damn! should have moded carefully

          the expected number of collisions will be approx. $$$\frac{136468^2}{2×10^9}≈9$$$

          And hence the statement

          If hash isn't working, it's because you haven't done enough of them

          Thanks man

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

    just notice that if you have a pair {l,r}, this gives same as {l, r+1} if s[r+1] = 1, and this gives same as {l-1,r} if s[l-1] = 0.

    so you just take each pair, remove all the extra ones on right side and zeros on left side and put in set, and output set.size(). you also have to add 1 if there is a pair that doesn't change s.

    it is clear that this is sufficient, because if two pairs {l,r} are different after having removed the extra 1s and 0s, they will create different strings when sort.

    you have to use a set.upper_bound or something to quickly remove extra 1s and zeros otherwise it will TLE because n*m = 10^11

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

      @piaolianggg

      why I have to add 1 if there is a pair that doesn't change s please..?

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

how to solve E? I overkilled it with 3 segment trees and binary lifting lol, didnt manage to finish implementing during contest, can smb slease tell a normal solution?)

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

    See here for a relatively simple D&C solution. It can also be optimized to $$$O(n)$$$.

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

      thank you!

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

        The main observation is: let L[i] be the last index in prefix i that p[L[i]] > p[i] and R[i] be the first index in suffix i that p[R[i]] > p[i]. Then Sum for all i min(i — L[i], R[i] — i) is O(N log N).

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

      This problem is literally the same!? (Actually it's easier due to the limitation of n) Is this allowed to have duplicate problems in Edu rounds OR duplicate problems from other sites or olympiads? I searched but couldn't find anything about this.

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

        I guess it's just a coincidence. The statement is short, so it's not surprising it many people come up with that statement independently.

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

Well-balanced contest, thank you! Why there is too small memory limit in problem E? I've got ML with sparse and rewrote to segtree. But anyway, E is pretty good :)

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

    Agree. Had to optimize binary lifting up to linear memory

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

    Can you write your approach also? That will be of great help.

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

    Odd, stable worked just fine for me

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

from problem C

is this approach accepted?

store prefix and suffix of given input string

store number of 1s and number of 0s of all the prefixes

create two vectors v0 and v1 such that v0[i] represents no of 0s and v1[i] represent no of 1s

ex:v0[3]="000" v1[5]="11111"

for given l and r can we create a new string like

pre[l-1]+v0[n0]+v1[n1]+suff[r+1]

where n0 and n1 are number of 0s and 1s in the range [l,r]

using all above data i did but i was getting memory limit exceeded

is this correct?

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

How to solve C.

I got wrong answer 2.

Can anyone tell me what should I correct

Here is my submission

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

    Is my approach correct?

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

      based off the wrong test case number which i also got it might be that you didnt account that the original string only counts if its duplicated at least once, i havent understood your idea though

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

    You should not insert the original string at the beginning. You can only count it if some copy is same as the original string after the sorting operation. Anyway, you are sorting the range for each copy and there could be 2*10^5 of them. So, in worst case the complexity would be O(n*m) ~ 10^10. That means, even if you fix the issue, you will likely get TLE.

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

editorial?

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

why dp doesn't work on D?

my submission https://codeforces.com/contest/1849/submission/215977499

there will be at most 1.6*(10^6) operations

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

Got stuck on B but it was interesting to me.. -ve delta for sure this round :(

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

where can i read editorials for this contest?

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

What was solution for B?

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

    reduce everything to equal or less than k, then use sorting or heap.

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

      Thank you. I was using that idea during contest but just realised that i was getting WA for a mistaken symbol '<'

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

Seems like the trick in F has appeared quite a lot times recently, e.g. abc308g and 1851F. So it may seem more solvable for me than E...

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

+123 Delta in Recent Div.3 Contest and -121 Expected Delta in this Contest

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

My 2 pointer approach failed in D :( 215981454

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

How to solve C questions. Every time I can manage to finish 2 questions but can't go to the next

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

    Hashing

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

    It was already explained by few folks in the comment section. However, I would like to share my approach. Let's say you have a range [l,r]. Let's consider a function S(l,r) which returns a string after sorting the range [l, r] on a copy of the original string s. S(l,r+1) = S(l, r) only if s[r+1] = 1. Similarly, S(l-1, r) = S(l, r) only if s[l-1] = 0. We can extend it further to S(l-a, r+b) = S(l, r) only if s[l-a...l-1] = 0 and s[r+1...r+b] = 1. Now, for each range, find the pair (a, b) where S(l, r) = S(l-a, r+b), a is minimised, and b is maximised. Then insert the pair into a set. The output would be the size of the set. However, you need to handle the cases where S(l,r) returns the original string. I guess if you understand the above approach, you would be able to figure that out easily.

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

Problem A — Greedy + Implementation
Problem B — Greedy + Implementation
Problem C — Greedy + Implementation
Problem D — Greedy + Implementation

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

    C wasn't really greedy (it was precomputation using datastructures e.g. an array so that you could answer each query in O(1)). I don't see how C involved the use of a greedy idea. And D could have been solved using DP, although the greedy D solution is more intuitive.

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

      what is greedy for D?

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

        First you compress the array. By this I mean if you have a contiguous subarray which only contains elements >= 1 then you compress it down to a single number which is the maximum number in the subarray. For example if the array was [0,0,1,1,1,0,1,2,1,1,0,1,2,0,1], I will compress it down to [0,0,1,0,2,0,2,0,1]. Now I spend coins on each position which isn't a 0, changing that position from blue to red. Notice that if the position is a 2 then both of its neighboring elements can also be changed from blue to red and if it is a 1 then only one of its neighbours can be changed from blue to red. I iterate through the array and if the current element is a 1, I first check if there is a neighbouring 0 to the left of it which is still blue. If there is, I change it to red. (This is the greedy idea to check the left neighbour first before the right neighbour as the left neighbour has no chance of being changed in the future so it is always optimal to change the left neighbouring 0 from blue to red if it's possible). If there isn't a neighbouring blue 0 on the left then I change the 0 to the right of the 1 to red instead of the one on the left. If I encounter a 2 while iterating then I just change both of its neighbouring 0s to red. After iterating, I then check how many 0s are still blue and spend coins individually on each one. Now the whole array is red.

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

        Lets say there is a subarray 1 2 1 2 2 1 1 , coloring any 2 in the subarray will make it act like a single colored 2.

        Similarly, if there is a subarray of continuous 1s, coloring any one will make the whole subarray act like a single colored 1.

        So your answer would be no of subarrays of 1s and 2s counted above + the 0s which cannot be colored by any 1 or 2.

        Submission Link — https://codeforces.com/contest/1849/submission/216052987

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

    IMO, A is just simple math. I don't see how it fits to be a Greedy problem.

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

How to solve F?

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

Spent an hour and wasted 6 submissions on B because of tunnel vision. And then solved D 10 mins after contest. It was nice being cyan.

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

    I also wasted my entire contest on B revolving around customized sorting of priority queue and ending up in TLE.

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

      Btw, you can pq.push({a[i],n-i}) so that standard pair order works.

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

Can someone explain the DP solution for D?

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

    It is not DP, it is purely Greedy.

    First, we group all the continuous 1 and 2, and replace them with max.

    For example, If the array is

    [0, 1, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 1]

    We can replace it with

    [0, 2, 0, 1]

    It is purely Greedy now, we take a covered array. We spend a coin for 2, and mark its adjacent as covered, then we check for 1.

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

      I know about the greedy solution but there are some people who have submitted a DP solution as well

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

        Oh, okk. Below one has commented with DP code :D

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

    215975523

    Basically dp[i] is the minimum cost to color the first i elements, with three cases:

    • index i was colored by index i+1

    • index i is able to color index i+1 (i.e. a[i] > 0)

    • none of the above

    Then you have to write 20 different transitions and hope that you haven't missed an edge case.

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

    Check my code I think it really is clear

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

      what is parameter j?

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

        it's a condition. $$$j=0$$$ means there is no condition. $$$j=1$$$ means that I can color the current index from the previous index. $$$j=2$$$ means that I want to color the previous index from my current index

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

I felt like D was quite easy, just a matter of implementing it properly. I kept doubting whether I had come up with the right approach since it seemed too easy and wasted time. Although it does have less solves than C, so there's that..

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

Is there any way of reporting a cheater in CF? Like, a self-hack with a secondary account. I'm refering to this submission: 215982877 in the Educational Codeforces Round 152 (Rated for Div. 2)

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

    The open hack phase does not give a rating, so its only kinda necessary to report him

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

How to solve c? Please give me hints

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

    Imagine we have to sort substring [L, R]. Let P be the length of longest prefix, consisting of 0, and S be the length of longest suffix, consisting of 1. Then, we actually have to sort only substring [L + P, R — S] (notice, if L + P > R — S, then substring is already sorted). In other words, L + P and R — S are the leftmost and the rightmost positions, which will have opposite bit after sorting. So, we have to count the number of distinct segments [L + P, R — S].

    P.S. Sorry, if my English hurts you

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

    If you like please upvote.

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

in problem b i tried using priority queue but got tle,can anyone help me with that,https://codeforces.com/contest/1849/submission/215983479

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

    think about case where k = 1 and all health of monsters are 1e9, then it is O(n * logn * 1e9) that's pretty slow

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

    array elements are upto 10^9 so if k = 1 then your solution takes upto n * 10^9 operations for single test, in other words TLE.

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

    In case k = 1 and some a[i] = 1e9 then it's easy for your solution to get TLE.

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

    Notice that you can subtract every a[i]the same multiple of k until one the a[i] reaches 0. Observe that the final array b where b[i] <= 0 for all i is given by b[i] = a[i]%k — bool(a[i]%k > 0)*k. By sorting b in decreasing fashion, you obtain the order of elimination (you can use a custom sort with a vector of pairs to keep track of the index).

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

I got stuck on problem B because I don't know C++ STL very well and don't know how to use a pair. Sadge, but the contest was educational.

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

getting tle in problem B using priority queue and i thought complexity is in o(n log n) only

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

    No. If you use priority queue the complexity will be O(n * log(n) * 10^9) so it is too slow

    You can think about getting remainder

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

    same approach but my submission was accepted, i used heap in python

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

Can someone find an issue with my solution? I am getting TLE using priority queue.

I used binary search find the multiple of k I need to subtract if the top element is too large but still TLE.

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

can C be solved using binary search on prefix sum??

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

Problem E. I wrote a double pointer method.

The idea is to take the 1-n enumerator as the minimum value of Subsequence like the ruler method. Obviously, there is a range, that is, double pointers. But the complexity is strange. I want to seek help to prove its complexity. I also hope that everyone can come and hack more often. thx
the code

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

Can Someone give me some detailed approach on C...I was getting TLE from brute and seg Tree..

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

    My approach:
    Let's iterate through string S and remember indexes of 0's and 1's.
    Now for every l and r binary search index of the first 1 and the last 0 in that range.
    If the 0 index is lower than 1 index then there was no 'movement'.
    Now insert pair {idx1, idx0} to the set.
    The answer is set.size() + 1 if the string stayed the same.
    Code

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

      gotcha

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

      thank you, I wanted to know the solution for this problem very much

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

      hi woonder

      can you explain why we should add this code in your solution

      if (ans0 < ans1) st.insert({ 0, 0 }); thanks in advance

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

        ans0 = index of the leftmost 0 in the given range
        ans1 = index of the rightmost 1 in the given range

        if ans0 < ans1 then string won't change.
        So I just add {0, 0} to the set and then I don't need to add 1 to the answer at the end.
        I hope I helped.

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

      I got it thanks alot

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

    Here is my comment to similar question.

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

Thank you for this contest! The problems were fun and enjoyable, and statements were short. I guess C was a little difficult and D was easy, but that's not too bad. This was also my first time AK'ing in Div.2. I'd say this was one of the best Div.2's in a while.

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

Hashing approach for C:
First calculate hash value of the initial string. Now if we apply the operation in range $$$[l,r]$$$ then the hash value of segment $$$[1,l-1]$$$ and $$$[r+1,n]$$$ will remain the same. Let there be $$$x$$$ number of zeros and $$$y$$$ number of ones in segment $$$[l,r]$$$ and the base used for hashing be $$$p$$$. let $$$x=3, y=4$$$. So, after the operation the new hash value will be:
$$$($$$hash value of segment $$$[1,l-1])$$$ $$$+$$$ $$$($$$hash value of "$$$000$$$" $$$\times p^{l})$$$ + $$$($$$hash value of "$$$1111$$$" $$$\times p^{l+x})$$$ + $$$($$$hash value of segment $$$[r+1,n])$$$
hash values for strings with all zeros and all ones can be pre-calculated.
store this new hash value in set. So answer will be size of the set.
My submission: 215990369

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

    256127907 Can u please tell me what is wrong with this? It would be a great help!

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

How we can store the suffix of string efficiently?

For problem C:-

My idea was to store suffixes and prefixes of string and prefix count of one zero ..

And in query..just make string temp

Temp=PREFIX [L-1]+prefixOne+prefixZer+SUFFIX[R+1]

It gave me mle..

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

why my solution to problem B TLEs at TC 6? Someone pls help me...

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

    i got it too, tho now i understood that suppose a[i] is of order 1e9 and k=1 (in simpler words a[i]>>k) , then to make a[i] to zero and then finally popping it out from priority queue will take time of a[i]-k which will be approx to 1e9 operations and yeah for popping and pushing consider logn as well so net complexity will be O(n*logn*(a[i]-k))

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

Here is my solution to E by using some binary search. The time complexity is $$$O(n(logn)^2)$$$ https://codeforces.com/contest/1849/submission/215980613

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

Is there any penalty for unsuccessful hacking attempts in this contest?

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

https://codeforces.com/contest/1849/submission/215999156
Can someone please help me to find error in my code for problem D

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

Problem B was really cool!!!

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

    could you help to understand problem b?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ignore typos and pardon for being late
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the greedy solution for D?

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

Video Editorial for problem A,B,C and D.

https://youtu.be/LrroyicG0mg

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

For question C, I tried to use a hashmap to store the pairs after i modify them according to the nearest out of order character between the pair, where the right number is mapped to the first 1 on its left and the left number is mapped to the first 0 on its right. I use an array to store whats the nearest 1 on left and 0 on right for each doing a linear pass for each. I got a WA2, and my solution is attached here https://codeforces.com/contest/1849/submission/215973791. Is there anything wrong with my idea? Thanks for any help!

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

I really like E and F, very good and educational problems!

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

RIP

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

Remember to use long long

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

Here is my solution to E which runs in $$$O(n \log^2 n)$$$. Hack attempts are appreciated.

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

Hi,I am unable to find the mistake in my greedy approach for problem D. It is failing on test case 28. Can someone please help me.

Here is my solution to Problem D

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

    I don't know where the mistake really is, but I found some hack cases.

    In:

    4
    0 1 0 1
    

    Out:

    3 (should be 2)
    

    In:

    6
    0 1 0 1 0 1
    

    Out:

    4 (should be 3)
    

    The hack cases also works with n=8,10...

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

Below 2100...

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

Can anyone please help me out with problem C. Submission 1 Submission 2

according to me Submission 1 should not fail as there would only be valid answer between the range (first 1 and last 0) both inclusive but by removing this condition I got accepted. If someone could point my mistake where I am going wrong.

Sorry for such a bad implementation. Thanks in advance

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

    Still looking for help!!!

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

    This test case gives different outputs for your submissions. Notice how 2 7 still gives you a different sort, but the indices are both outside of the first 1 and last 0, which are 3 and 6

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

      thanks didn't thought of this case got it accepted after adjusting the condition

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

Q3 and Q4 was easy but tricky

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

Why does my profile show that this contest is unrated? I'd become a specialist if they would increase my rating :(

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

Can someone tell what is mistake in my approach for problem 3. In this i used trie data structure to store every possible string. But, still i am getting WA in test case 2.please find the mistake in 216055609

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

    When you are posting such a long piece of code, you need Spoiler and Block, which you can easily find up the textbox where you write your comments. It looks like:

    My solution for C

    this is my solution for problem C btw.
    In my opinion, you may fix your formatting first, otherwise it will be difficult for anyone to understand your code. Hope this helps.

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

cool contest

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

Can anybody explain the dp solution of Problem D ( I know it can be solved using greedy)

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

Orz

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

still waiting for rating changes :_)

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

How to solve E? pls help.

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

    Spoiler: You can solve it using diramida to find first / last element which is more/less then x. Another spoiler: iterate the minimum from 1 to n

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

      what is diramida

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

        Sorry) I meant treap)) I thought that in english this data structure is called like this))

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

      i tried to think in that direction, but seems difficult

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

    First , for each element you can find the right most position that is more than a[i] using stack;(and find the right most position that is less than a[i]) Now lets define dp[l] = is position of max more than position of min in [l,r] for a fixed r: Now lets check how does dp[i] change after we increase r by 1; for all i such that a[r] is max in [i,r] , dp[i] will be changed to 1 , and in the same way for all i such that a[r] is min in [i,r] , dp[i] will be changed to 0;and the other dps will remain the same(because a[r] is not the max nor the min of that array so it will not affect dps condition); So sum of dp[i] for a fixed r will be the number of segments that we should count that the segment ends at r So for solving this problem we can increase r 1 by 1 and update dps using sum data structures like segment tree and we can solve this problem in O(n*log(n));

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

    Imagine two stacks: one for increasing elements, the other for decreasing elements. If you draw it, you get a diagram of points consisting of two lines (one for increasing, one for decreasing). Then, for each point in the decreasing line, connect it to the first point smaller or equal to itself. The answer for a single index $$$i$$$ is the sum of the lengths of such segments. In order to maintain it while going left-to-right, use two sets with two stacks.

    Code: https://codeforces.com/contest/1849/submission/216019848.

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

will the rating still change later? qwq

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

Where can I find editorial?

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

Can someone expalin the segment tree approach of problem E.

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

Why is the rating not updated yet?

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

For problem E, I did divide and conquer, maintained prefix and suffix max and min values, and did 2 pointer kind of approach.

Let's say I want to calculate $$$Ans(L, R)$$$ using divide and conquer. (L, R both inclusive) we can see that
$$$Ans(L, R) = Ans(L, mid) + Ans(mid+1, R) + X$$$
where $$$X$$$ is the count of valid subarrays whose left pointer in the left region $$$(L, mid)$$$ and right pointer in the right region $$$(mid+1, R)$$$.

To count this $$$X$$$, we have the following cases:

Case 1) When both $$$max$$$ and $$$min$$$ are in the left half.
Case 2) When both $$$max$$$ and $$$min$$$ are in the right half.
Case 3) When $$$min$$$ is in the left and $$$max$$$ is in the right half.

For working out all of the cases, it can be seen that fixing the $$$i$$$ pointer in the left/right subarray and finding the count of the valid $$$j$$$ pointer in the right/left subarray approach will work. It can further be optimized to a 2-pointer by observing that the $$$MAX$$$ value keeps increasing in the prefix, and the $$$MIN$$$ value keeps decreasing. And some recalculation can be made from previous value of $$$i$$$ pointer.

Each case mentioned above can be worked out in $$$O(N)$$$
Overall time complexity is $$$O(NlogN)$$$.

Code: https://codeforces.com/contest/1849/submission/216111032

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

It's my first time participating in an educational Codeforces round. It said, "This round will be rated for the participants with rating lower than 2100". However it shows as unrated on my profile. Can someone please tell me it shows unrated?

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

    Hey, it's rated round, it takes some while sometimes to update ratings so hold on buddy :)

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

    Because it isn't rated YET

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

When will the ratings get updated?

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

why not still rated? lol

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

I hope rating changes will update before i get to sleep.

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

I'm excited for $$$myRating \ mod \ 10 = 0$$$

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

Why the rating is still not given for this contest

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

I hope rating changes will update before i get to sleep.standings

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

Are they including hash table hacks on the testcases? After the contest they added testcase 9 on B where I got TLE 216129676. By just changing the hashes I get AC 216106308. Should I always during contests avoid using sets and dicts with integers keys (Python)?

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

    absolutely yes. all of the system testing point were came from the user’s hack point. when hacker view someone’s codes using hash and have some bugs, they will generate the unique point to make the AC to WA or other result.

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

    In the TLE submission, this line pos[p].append(i+1) you can change to pos[str(p)].append(i+1) and submit again.

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

The editorial has been posted 3 hours ago and still there's no rating changes

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

Has it become unrated?

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

TLE on rating change! mike should find a better algorithm

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

could smbd help me: is it okay that my rating wasnt changed after this ed round?

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

Is this round unrated? Someone answer please

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

Slow tutorial :(

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

Can you teach me the DP method of D, how the state is designed, and how to transfer?

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

    State --> For each index, maintain color(current color of the index), need(whether previous index need to be made red).

    Transition --> Case 1: If need is active, current element must be >0. Case 2: If you choose to paint it red or if current element is red, check if you can make its adj element red as well. Case 3: If you leave it blue: if need is active, case 1 should be satisfied.

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

      Could you explain the definition of $$$dp[i][0/1/2]$$$,and the meaning of transfer, thank you!

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

        I used slightly different state. dp[color][need][index]. Iterating over each index, we have to make transition depending on current value of color and need. Try breaking down each cases, you will get the transitions. Here's my messy code if it might help. 216205936

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

Hello, please help me. I am trying to solve D but got the wrong answer on test case 28. Correcting my error would be very helpful for me.

my submission — SUBMISSION LINK

Thank you.