r/codeforces

What is your motivation for CPP when you have AI writing code?

I used to solve 1300-rated problems in around 30–40 minutes, but I didn’t do competitive programming for the last 4 months.

Now I’m struggling with 1100-rated problems — sometimes taking more than an hour, and sometimes not being able to solve them at all.

Has anyone gone through something similar? Any suggestions on how to regain speed and problem-solving ability?

->I will be targeting 1100(3),1200(4),1300(4) level questions initially (as my rating is 1169) daily from c2ladder

->i will learn new topics as i encounter them in questions and then use cses to work on the same....if i encounter a new topic on day x then on day x+1 i will include questions from same topics in the above 11 questions(may disturb the split mentioned earlier)

->give each and every contest on codeforces

->share daily report on this sub from June 1

if u have any suggestions feel free to share

Any good resources for getting good at graphs and DP? For interviews?

Finally that XVIII guy got banned.. any other cheaters who got banned this time?

I got a positive delta of 10 in current rating

How did your ratings change guys?

Title(absolute beginner I don't even know how to write function in c++)

So I am quite a mathematician and I like proving things.

Problem: Container with most water.

https://leetcode.com/problems/container-with-most-water/description/

What I have tried:

Brute approach done. Optimal approach - done but UNABLE to visualize, even from the hello-interview website.

Proof I made for that optimal solution that somehow works it out, but doesn't convince me:

Aim: To maximize f(x,y) = (y-x) * min (ax, ay), where let x and y be left and right indices (x < y). Let array be 1-indexed from a1, a2, ... an.

for some x < k < y.

Also remember the result that min (a, b) <= a and min (a, b) <= b. Its handy in this proof.

Case-1: If ax < ay.
In this case, then using basic inequalities we can work out that f(x, k) < f(x, y)
So areas formed using (x, x+1), (x, x+2), ..., (x, y-1) are all less than the area found using just (x,y). So they can be rejected for analysis.

Similarly for case-2: if ax > ay, we can show that f(k, y) < f(x, y). Thus prune more unwanted search space.

Case-3: ax = ay. In this, we can just change any one of them or even both doesn't matter. Just change them.

Then I also dry run it on set of inputs a lot of times.
Here:

https://preview.redd.it/nral4rizjq2h1.png?width=1816&format=png&auto=webp&s=813ede99e60259eb80b2744ac3992f0d1067cbac

and had a few more images but can not add.

After this also I was not convinced. So I try to generate the matrix itself. Example for the image above the symmetric matrix with diagonal entries zeros would be:

0 4 8 12 16 20 24 28 32 36 40 44

4 0 6 12 18 24 30 36 42 48 54 50

8 6 0 8 16 24 32 40 48 56 56 45

12 12 8 0 10 20 30 40 50 54 49 40

16 18 16 10 0 12 24 36 48 45 42 35

20 24 24 20 12 0 15 28 *270 36 35 30

24 30 32 30 24 15 0 14 30 27 28 25

28 36 40 40 36 28 14 0 14 18 21 20

32 42 48 50 48 270 30 14 0 9 14 15

36 48 56 54 45 36 27 18 9 0 7 10

40 54 56 49 42 35 28 21 14 7 0 5

44 50 45 40 35 30 25 20 15 10 5 0

with 270 being maximum.

If you look at it we start from the upper rightmost element of this matrix in most two-pointer problems. As it denotes l = 0 and r = n-1.

Now we have two options either go down the matrix or go left of matrix. Both ways, the width decrease by 1.

But the height VARIES and has no such pattern. There's just no way to tell anything.

So any normal person would go in the direction where height increases.

But what if the height DOES NOT increase. In that case - we are STUCK.

So we decide to remove away the element that controls heights - the lesser of the two - just for exploration.

Then WHY this so random exploration leads to the solution. Why it doesn't skip any other potential solution. That is what I wish to understand.

Using matrix helped me visualize two-sum and prove it intuitively. But in that problem, the array was sorted. But here it is not.

So I realized I AM AT MY LIMIT quite literally.

My not-so-optimal code O(N):
(the else block I put there was because I was getting stuck whenever hh <= h into an infinite loop.)

#include <iostream>

using namespace std;

int main (void)

{

int n = 0; cin >> n;

int a\[n\] = {0}; for (int i = 0; i < n; ++i) { cin >> a\[i\];}



int l = 0;

int r = n-1;

int max\_area = 0;

while(l < r)

{

	int w = r-l;

	int h = min (a\[l\], a\[r\]);



	int area = w\*h;

	if (max\_area < area)

	{

		max\_area = area;

	}





	int h1 = min(a\[l+1\], a\[r\]);

	int h2 = min(a\[l\], a\[r-1\]);

	/\*

		respective areas

		a1 = h1(w-1) and a2 = h2(w-1).

		This means a1 and a2 are proportional to the new heights h1 and h2.

		So just pick whichever height is greater than old height h.

That leads to the greater area.

		BUT else case, if out height is already more - why would we want to move??

		as h\_old > hh, this means that any new area you calculate = hh \* (w-1).

		Its guaranteed to be strictly less than the oldarea = h\_old \* w.

		THIS causes an infinite loop if not handled carefully.



	\*/

	int hh = max(h1, h2);

	if(hh > h)

	{

		if(hh == h1)

		{

++l;

		}	else

		{

--r;

		}

	}

	else

	{

		if(a\[l\] < a\[r\])

		{

++l;

		}

		else if(a\[l\] > a\[r\])

		{

--r;

		}

		else /\*they are equal\*/

		{

// change any one of them OR change both. doesn't matter.

++l;

		}

	}

	

}

cout << max\_area << endl;

return 0;

}

I did a lot of research on the “best way to practice” when it comes to competitive programming, and here is what I got from it:

Don’t bother reading theory, just dive straight into pumping out problems on codeforces. Always do problems in these 2 types of categories:

Speed runs: Doing problems at your rating or lower as fast as possible to build up intuition and speed.

Thinking/suffering runs: Do problems of a rating that is 200-400+ higher than your own (or a rating in which you can only solve the problems 30% of the time),
this helps you get better at solving harder problems and thus actually progressing in rating.

(I heard that it’s best to just do random problems of a certain rating on codeforces rather than doing problems by individual topics like on USACO guide, because you would be spoiling yourself of the problem’s topic, which I definitely agree with)

Read editorial for the problem if you cannot make any meaningful progress after 20 minutes of thinking, don’t just read the entire solution, read hints, then try again for another 5 minutes.

Always write down your solution in brief detail after you solved it, so that you can refer back to it later, and always keep your mind fresh on previously seen tricks so you can keep reapplying them on similar problems, thus improving your pattern recognition.

Always participate in contests, and upsolve the problems that you couldn’t solve/were stuck on.

The only time you should solve problems by individual topics/read up theory is when you haven’t learnt a certain algorithm/technique and you literally don’t know how to implement it in code, and you want to get better at these specific implementations (such as DP, graph algos, etc). Good sources for learning these individual topics are CSES or again, USACO guide.

What do you guys think of this routine?

https://preview.redd.it/j0giqm5lno2h1.jpg?width=1019&format=pjpg&auto=webp&s=ea74580dca7f47706c341d36980f5740b03e5d26

I finally hit the Specialist rank. I solved 4 problems in Round 1099 (Div. 2) and got a +201 rating increase, which put me at 1582.

I spent a lot of time trying to get the core concepts right: greedy, algorithms, implementation, basic math, and breaking down problems quickly under the time limit. It feels good to see that effort translate into a solid rating jump and crossing the 1500 mark.

Next goal is Expert.

I upload all my C++ contest code and accepted solutions to this repo:https://github.com/yusuf-husayn/Competitive-Programming

If you are at Expert or above, what specific topics actually helped you make that next jump? What should I focus on right now?

How’d you guys solve this problem and what topics or problems helped you reach the soln of this particular problem.

In yesterday's Div2........ I am going through top peoples solutions
there are many new accounts and the solutions looks very fishy
Using camel casing lol

also many handles they are jumping their ranks out of no where

Should I start with cp 31 sheet or CSES problem set , if CSES what order should I follow to solve it.

P.S. :- I am doing dsa from 1 or 2 years but want to increase my level.

problem 2231C

Instead of tracking everything, we can exploit the fact that numbers shrink incredibly fast under these operations (even 10^9 drops to the bottom cycle in at most around 60 steps).

1. Pick initial target `T`: Start by setting `T` to the smallest even number in the array (or `a[0]` if all are odd. Now that im thinking after the contest it could fallback to the smallest number if no even numbers exist).
2. Shift the target: Loop through the array. If the current element `a[i]` cannot reach `T`, it means our target is currently too high or on an unreachable branch. Instead of restarting or tracking states, we just reduce our target down (T = reduce(T))until `a[i]` can reach it. `T` will quickly converge to a matching point.
3. 1 to 2 check: Since 1 and 2 loop into each other at the bottom, one might save a few extra steps depending on the array. We handle this edge case with a clean, linear check at the very end to see if flipping `T` between 1 and 2 gives a smaller total answer.

```

ll reduce(ll x)
{
    if (x%2 == 0) return x/2;
    return x+1;
}


bool can_reach(ll x, ll target)
{
    for (int i=0; i<100; i++)
    {
        if (x == target) return true;
        x = reduce(x);
    }
    return false;
}


int get_steps(ll x, ll target)
{
    int steps = 0;
    while (x != target)
    {
        x = reduce(x);
        steps++;
    }
    return steps;
}


void solve() {
    int n; cin>>n;
    vl a(n);
    ll T = -1;
    
    for (int i=0; i<n; i++)
    {
        cin>>a[i];
        if (a[i]%2 == 0)
        {
            if (T==-1 || a[i] <T) T = a[i];
        }
    }
    
    if (T == -1) T=a[0];


    for (int i=0; i<n; i++)
    {
        while (!can_reach(a[i], T))
        {
            T = reduce(T);
        }
    }


    ll total_steps = 0;
    for (int i = 0; i < n; i++) {
        total_steps += get_steps(a[i], T);
    }


    if (T==2 || T==1)
    {
        ll alt_target = (T==1)? 2:1;
        ll alt_steps = 0;
        for (int i=0; i<n; i++) alt_steps += get_steps(a[i], alt_target);
        total_steps = min(total_steps, alt_steps);
    }


    cout << total_steps << "\n";
}ll reduce(ll x)
{
    if (x%2 == 0) return x/2;
    return x+1;
}


bool can_reach(ll x, ll target)
{
    for (int i=0; i<100; i++)
    {
        if (x == target) return true;
        x = reduce(x);
    }
    return false;
}


int get_steps(ll x, ll target)
{
    int steps = 0;
    while (x != target)
    {
        x = reduce(x);
        steps++;
    }
    return steps;
}


void solve() {
    int n; cin>>n;
    vl a(n);
    ll T = -1;
    
    for (int i=0; i<n; i++)
    {
        cin>>a[i];
        if (a[i]%2 == 0)
        {
            if (T==-1 || a[i] <T) T = a[i];
        }
    }
    
    if (T == -1) T=a[0];


    for (int i=0; i<n; i++)
    {
        while (!can_reach(a[i], T))
        {
            T = reduce(T);
        }
    }


    ll total_steps = 0;
    for (int i = 0; i < n; i++) {
        total_steps += get_steps(a[i], T);
    }


    if (T==2 || T==1)
    {
        ll alt_target = (T==1)? 2:1;
        ll alt_steps = 0;
        for (int i=0; i<n; i++) alt_steps += get_steps(a[i], alt_target);
        total_steps = min(total_steps, alt_steps);
    }


    cout << total_steps << "\n";
}```

It was a quite difficult contest especially the problem C what the hell was that couldnt solve it solve A B D
Got TLEd 4 times on C