Hi MikeMirzayanov.

I believe many people have cheated in the most recent contest, this behavior should be unacceptable. It also appears there are groups of people helping each other cheat.

Take note of the comments in this submission: 174424727.

// if a[i][l]==a[j][l] then d+=a[i][l] else d+=3-a[i][l]-a[j][l] //this is the line that I don't know how to translate into cpp. I tried to use ternary operator but it doesn't work. Please help me! Thank you!

// return 0 in python is return 0 in cpp? I'm not sure about this one too! Please help me! Thank you! :)</code>

It is clear that this person is cheating.

I believe this has significantly effected the ratings of competitors, including me, in this most recent contest. I would put heavy suspicion on all long-standing newbies who have recently skyrocketed to the top 1500 in this contest. It is almost assured that they are cheating. You can notice the unusual spike in the rating graph of the user whose submission I have linked.

I have also found that all of these submissions are exactly the same. There are more, I will find them later: 174418316 174422837 174422837 174422426 174428235 174428573 174413648 174424155 174427490 174422837 174413565

Thank you for your time.

Hello I have the following problem. Does anyone know of a solution.

Consider a grid of NxM (NM<=1e5) with grid values that are either colored or not colored. We start with a blank grid and in each operation you can choose any 2x2 subgrid of the grid and paint it. If a grid square ever is painted it cannot be unpainted again. Determine the minimum number of operations to get the original grid or determine if it’s impossible.

Yet again I fail the USACO competition. This time I used repeated subtraction instead of floored division which caused me to TLE. I checked my code with the floored division instead and it ACes. Unfortunately I wouldn’t have been able to change it in time since I ran out of time just as I was about to submit the solution. Now I must wait another month for the next competition. I guess all I have to do now is just work on implementation skills but it’s kinda disheartening to be so close to promoting to gold, something I’ve been working towards for over a year. I don’t really have any questions, I’m just venting.

Hi, recently I've been trying to do problems that are way too hard for me and stumbled across the following problem from Deltix Summer 2021: https://codeforces.net/contest/1556/problem/E. I would recommend people actually go and try the solve the problem first before looking at this post as there will be problem spoilers here.

I took the day trying to think of solutions to this problem and I actually made a handful of nice observations but ultimately got stuck at some point and didn't really figure out what to do. After a lot of frustration I eventually decided to look at the editorial, but even after viewing the solution I was still stumped about the intuition behind the answer. I looked on youtube as well and didn't find much of use which led me to some sort of upset state about not being able to understand the problem well.

Regardless I kept thinking throughout the day and recently the problem solution has hit me in a very elegant manner that I'd like to share with you. I'll start from my original thinking about the problem. The problem statement basically summed up to how we should fix some subarray so that the elements of a and b are the same while using operations that alternate between incrementing a and incrementing b. I wrote out the sample case and it became apparent pretty quickly that the actual solution would only depend on what the difference between a_i and b_i would be. I made note of storing some difference array dif and continued on.

After some fumbling around and realizing I read the criteria of the operations wrong I stepped back and thought of the problem as one where we should be choosing the closest positive value for each negative value. The greedy method made me think a bit about bracket sequences as I noticed a lot of similarities between those types of problems and the one I was currently facing. For example if the value of dif_1 was positive it would be impossible to deal with such a case because there would be no negative values to "balance" it. Likewise for a case where we had some negative value at the end there would be no way to deal with a case b balancing it out with positive values further down the segment. I began to write the problem as a regular bracket sequence where a negative number n would signify using n ( brackets and a positive value p would signify using p ) brackets. Of course I had no proof that such problems were even remotely similar but to my intuition this seemed like the most logical step to reduce the problem. In fact, the idea checked out, such a sequence was only possible if the bracket sequence was regular, else we would run into a case where no matter how many negative values were incremented before a ) we would never be able to balance out the ) and would run into a case where we had a ) at the beginning which would be impossible to remove. Likewise for ( if we did not have enough ) after it we would be forced into a bad position. Aha! Done with the problem onto another―― oh it's asking for the minimum amount of such operations... So I slumped down in my seat a little bit.

This seemed like a much more difficult problem, with some thinking I eventually came up with the idea to split our bracket sequence into pieces of similar types. For example: (((( | ))) | ( | )). With some further thinking I convinced myself that we should always take as many brackets as we could which becomes the number of such segments. My reasoning for this was basically that if we didn't we would have to do later, so we might as well do so now. So this left me with the following problem, how are we supposed to figure out for any subsegment the amount of times it would take for us to make such a subsegment empty while using this sort of method.

I was stuck here for a while, I thought we could maybe do this operation once for the original sequence and then use that as our best result for every subsegment but that seemed complicated and I didn't really see a clear way to deal with the fact that the whole array and each subsegment didn't really line up too well when trying to take this approach. There would be issues regarding how we could quickly find exactly which operation made this whole subsegment 0's and having values we removed have to update multiple possible queries. It just didn't make sense to me. After a lot more diagrams (one in which I accidentally found something very useful but never bothered to think about it) I eventually gave up and turned to the editorial, a bit disappointed that I was stuck on this one step. The editorial gave me the solution and a proof, but this left me still unsatisfied, I didn't think I could simply solve this by just guessing the solution and I wanted a way to intuitively find it. I also looked in the comments and on youtube but I didn't totally understand how people were coming up with the solution and I still wanted to find if the things I was doing before could translate nicely into a solution.

I eventually relaxed a bit and came back to the problem, hoping to simplify things. As I put my pencil down onto the paper and drew out a RBS it suddenly occurred to me that I had done something before which might be very useful. When I was simulating my approach I was doing the following:

The thing I was doing was essentially crossing out very close brackets that were of the form () to make my life easier when writing down the simulation on paper. Only now did it occur to me that such a way of representing operations was actually incredibly useful as it allowed for the following:

Essentially what I had constructed before by just writing stuff nicely on paper was actually a direct representation of the depths of a bracket sequence where the maximum depth was the amount of operations I needed. I was excited by such a nice way of representing the problem and quickly proved myself correct. It turned out that something very hard could be simplified into a much easier problem through just some concepts I had used before and a little bit of luck. It also made me have a deeper appreciation for such problems which, if worked out completely, actually are very instructive.

That's really all I have to say for this story, not sure why I posted it but I guess I just felt like I had to share my excitement a bit~

Hi recently I took a contest that I've been studying over a year for and barely failed. My mind keeps thinking about all the things I could've done better and I'm pretty angry about all the things that I missed. I did improve, but it seemed that even with so much studying I still couldn't pass. I'm also pretty demotivated to do cp now. Any suggestions or similar experiences from you guys?