It was over two years ago when I cheated (for the first and last time) on Codeforces. It has been a long time, and over the period, many MANY more sophisticated methods of cheating than the one I used (copying code from another) has come out. Nowadays, I still find myself thinking about it from time to time, and today I've decided to come clean.

It is mightily embarassing for such an occurence to be displayed squarely at the first page of my submissions. If Codeforces allowed for the privating or deletion of submissions, these bozos would have been long gone. But the reality is that unless you are a cheater (or doing some really shady stuff), there is literally no good reason for you to delete your own submissions.

In a way, I am thankful to Codeforces for that. The submissions today mark to me the beginning of my journey into actual Competitive Programming, and more abstractly my personal growth in two years. All the while, perhaps a bit more sentimentally, they remind me of a bygone time when CP was basically the world to me, when I would be excited every other day thanks to some technical blog on Codeforces. It's a bit different now with the added complexity that comes with time.

That might not be the case for the community though. Maybe two years is not enough to prove anything, even if I swear that I have not cheated in another contest ever. Especially now with all the Cultural Revolution-style cheating purges, I might regret having ever come out as an ex-cheater. I just want to get things off my chest first.

Oh well this has been long-winded. Give me your contribution points or whatever

I have been stuck on this problem for a few days now. It seems to be an expansion of the Project selection problem (PSP).

For those unfamiliar with PSP, it goes something like this: There are $$$n$$$ projects to be completed, the project $$$i$$$ will add $$$a_i$$$ money to your total ($$$a_i$$$ can be negative), and there are $$$m$$$ dependencies, where the project $$$u$$$ requires the project $$$v$$$ to be completed before being completed itself. Your goal is to choose projects to complete so that the total sum of money is maximized. This can be easily solved using a minimum cut model as described in this blog.

We can restate the problem a bit more formally: Maximize the sum $$$S = \sum_{1 \le i \le n} a_i \cdot t_i$$$, so that $$$\forall 1 \le i \le n, t_i=0$$$ or $$$t_i=1$$$, and $$$\forall 1 \le j \le m$$$, if $$$t_{u_j}=1$$$ then $$$t_{v_j}=1$$$.

What my problem deals with, is the dependencies taking on different forms, such as "if $$$t_{u_j}=0$$$ then $$$t_{v_j}=1$$$", "if $$$t_{u_j}=1$$$ then $$$t_{v_j}=0$$$", and "if $$$t_{u_j}=0$$$ then $$$t_{v_j}=0$$$".

I'm also aware of this blog, which seems very reminiscent of the matter, but I was unable to derive a definite solution from it on my own.

I would love some help from Codeforces!

You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. You are also given two positive integer constants $$$P$$$ and $$$Q$$$. The constraints are $$$n, a_i, b_i, P, Q \le 10^6$$$. You must choose $$$n$$$ non-negative real coefficients $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ so that all of the conditions hold:

• $$$\sum a_i x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + ... + a_n x_n \ge P$$$

• $$$\sum b_i x_i = b_1 x_1 + b_2 x_2 + b_3 x_3 + ... + b_n x_n \ge Q$$$

• The expression $$$S = \sum x_i = x_1 + x_2 + x_3 + ... + x_n$$$ is minimum.

What is the minimum value of $$$S$$$?

The limits are the usual 2 seconds and 256MB. I couldn't find an online version of this problem, only a plaintext version from some local archive. I'm guessing this is some kind of greedy problem where you only need to "choose" no more than two pairs, but so far I have no luck trying to prove my strategy (nor have I confirmed its correctness).

I have thought about simplifying down to the case of $$$n=2$$$ then hoping some algebra magic will take it all the way to every integer $$$n \gt 2$$$. Again, I'm stuck on the transitioning part.

I would love some help from Codeforces!

I was solving 1839D - Ball Sorting which was a standard DP problem, when I submitted and got WA on test 1. This was so strange to me since I just pasted the input into my own IDE and the outputs were identical. But sure enough, the moment I submitted the same exact solution, the output was different. I had to spam multiple submissions onto Codeforces to see what went wrong.

WA solution vs AC solution

280230092 280230005

The only difference between these two pieces of code were ++n; a[n]=n; and a[++n]=n;. At first I thought, shouldn't these have the exact same effect? That's what my compiler told me!

After another WA on test 1-to-debug submission, I realised that it is possible that Codeforces' compiler had put the original value of $$$n$$$ into some temporary memory first, and only then update $$$n$$$ and put the temporary value back into the array.

I have used this kind of assignment a[++n]=n so many times, I'm surprised that only now I'm discovering this! Which is so dangerous because imagine the devastation this could have caused me in offline contests where you only get one chance.

Is it bad practice to put any thing but a single variable into the index of an array? I hope to learn more from all of you.

Today I tried to solve 1932F - Feed Cats, and finally got Accepted, though not after some hard debugging. You can give a try at the problem first before reading this.

Here is my original submission with WA on test 3 268592520 and here is my AC submission 268597071.

My thought process went like this:

• I thought of a segment tree with sweepline style solution

• Though using segment tree with n=10^6 is very risky (high constant time)

• So I went ahead and compress the coordinates of the start point and end point of each segment.

• Query an addition at the compressed start point and a removal at the (compressed end point) +1.

This is WRONG, however. Since there is a chance of nothing happening at the compressed end point and something else happening at the (compressed end point) +1 that might influence the answer, this can give a wrong result. The really important part is the compressed (end point +1) where the removal ACTUALLY happens, which I failed to realise for 90 minutes.

Did I learn my lesson? Yes. Did you waste your time reading something you already know/ don't need to know yet? I hope not. Either way, perhaps I will leave this blog here as a cautionary tale for myself, to better tackle future problems I will have to solve.

The problem goes as follows:

You are given an array a of N non-negative integers, indexed from 1 to N. Define prev(x) such that prev(x) is the largest integer that satifies both following conditions: prev(x) < x, and a[prev(x)] < x. Print prev(i) for each i from 1 to N.

This is a basic problem that can be solved using stacks. However, I've seen an interesting implementation that avoids data structures altogether. Here's the main code for it:

cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
a[0]=-inf;
for (int i=1; i<=n; ++i){
    int p=i-1;
    while (a[p]>=a[i]) p=sol[p];
    sol[i]=p;
}
for (int i=1; i<=n; ++i) cout<<sol[i]<<" "; cout<<"\n";
return 0;

It seems to me that this runs in O(n) on average, but I cannot find its worst-case complexity. I suspect it to be O(n^2) but have had no luck proving it so far (I once used this implementation in a practice problem and got TLEed). Any help would be greatly appreciated. Thanks!