okay so I had this idea

imagine you get 100 coins and you have to build the best competitive programmer possible by buying different skills

every skill has a price and you can't spend more than 100 coins

here's the shop:

Mathematical intuition — 25, Algorithm knowledge — 25, Implementation speed — 15, Debugging — 15, Creative problem solving — 25, Pattern recognition — 20, Proofs and correctness — 15, Contest pressure management — 15, Consistency — 20, Optimization — 15, Reading statements carefully — 10, Learning from editorials — 15, Time management — 10, Finding counterexamples — 15,

you can buy whatever combination you want, as long as you stay within 100 coins.

now the interesting part is that you obviously can't buy everything.

would you spend most of your coins on algorithms and maths? or would you invest in things like debugging, consistency and not panicking during contests?

also, don't just drop your build. explain why you picked those skills. feel free to argue with someone else's choices too.

I'm curious what kind of builds people at different ratings come up with.

100 coins. what's your build?

Round 6.

Today's code is supposed to be pretty straightforward. We have an array of positive integers, and we need to find the sum of all its elements.

Nothing fancy. No segment trees, no DP, no 200-line template.

Just a loop.

The code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int sum = 0;
    for (int x : a)
        sum += x;

    cout << sum << '\n';
}

Looks completely fine, doesn't it?

It compiles. It runs. It gives the correct answer on small examples.

But the constraints are:

• 1 <= n <= 200000
• 1 <= a[i] <= 1000000000

Your mission

Find a valid input for which this code fails.

1. Give a counterexample that makes the output incorrect.
2. Explain exactly what goes wrong.
3. What's the smallest change needed to fix it?
4. Bonus: can you explain why the same bug might go unnoticed during local testing?

Try to keep the counterexample small. No need to paste 200,000 numbers when a much smaller test can expose the problem.

Let's see who catches it first.

Round 5.

I swear some of the worst bugs are the ones where your logic makes perfect sense until someone finds a test case you somehow never thought of.

Here's today's one.

The problem

You are given an array of positive integers. You need to select some elements such that no two selected elements are adjacent.

Find the maximum possible sum.

For example, for [3, 2, 7, 10], choosing 3 and 10 gives a sum of 13.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int ans = 0;

    for (int i = 0; i < n; ) {
        if (i + 1 < n && a[i + 1] > a[i]) {
            i += 2;
        } else {
            ans += a[i];
            i += 2;
        }
    }

    cout << ans << '\n';
}

The idea is basically to avoid taking an element when the next one is bigger, and otherwise take the current element.

Seems reasonable at first glance. If the next element is bigger, why bother taking the current one?

Except… maybe looking only one step ahead isn't enough.

Your mission

Find a counterexample that makes this code return the wrong answer.

• Keep the array as small as possible.
• Explain what the code prints and what the actual maximum sum is.
• Give a correct algorithm and explain why it works.

Bonus: can you solve this in O(n) using dynamic programming?

And please don't just throw a random huge array at it. I want the smallest counterexample that breaks the idea.

Let's see who gets it first.

Alright, round 4.

This time it's binary search. The code looks normal, the idea seems reasonable, and it even works on the examples I tried.

But I'm pretty sure there's a test case waiting to ruin my day.

The problem

You are given a sorted array of n integers and an integer x.

Find the index of the first element that is greater than or equal to x. If no such element exists, print -1.

Use 0-based indexing.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for (int &i : a) cin >> i;

    int l = 0, r = n - 1, ans = -1;

    while (l < r) {
        int mid = (l + r) / 2;

        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << '\n';
}

The idea is simple: if a[mid] is at least x, save that position and search to the left. Otherwise, search to the right.

Pretty standard binary search, right?

Your mission

Find the smallest counterexample you can.

• Give an input for which my code prints the wrong answer.
• Explain exactly why it fails.
• Fix the code with as few changes as possible.
• Bonus: can you explain what invariant a correct binary search should maintain?

Please don't just say "use lower_bound." I know it exists. I want to see the actual bug.

Let's see who catches it first.

I've been thinking about this for a while.

We all know what rating is supposed to do. It gives us an idea of our performance in contests, helps us compare ourselves with other coders, and gives us something to work towards.

But I feel like different people see it very differently.

For some people, reaching the next color is a huge goal. They want to become Specialist, Expert, Candidate Master, or even go way beyond that.

For others, rating is just a number. They participate in contests, solve problems, learn new things, and don't really care that much about the number next to their handle.

And then there are people who are genuinely happy after gaining 20 rating but spend the entire evening thinking about losing 30.

I think the interesting part is that two people with the same rating can have completely different goals.

One person might be trying to reach 1400. Another might be trying to reach 2400. Someone else might just enjoy solving problems and not have a target at all.

Personally, I think rating is useful because it gives us a way to track progress. But it can also be misleading if we start treating every contest as a judgment of how good we are.

One bad contest doesn't erase everything you've learned, and one good contest doesn't mean you've mastered everything.

I'm curious about how other people here think about this.

A few questions:

What is your current rating, and what rating are you aiming for?

Do you genuinely care about your rating, or is solving problems more important to you?

Have you ever changed how you practise because of your rating?

I'm interested in hearing different perspectives, especially from people at very different rating levels.

Let's hear it.

I genuinely don't understand this sometimes.

You open a Codeforces problem rated 800 and think, okay, this should be easy.

You read the statement. Seems simple enough.

You start thinking about the solution.

5 minutes pass.

10 minutes pass.

You try something. Doesn't work.

You try another approach. Still doesn't work.

At this point you're convinced there's some observation you're missing, because surely an 800-rated problem cannot be this annoying.

Then you open the editorial.

And the solution is so simple that you just sit there staring at your screen.

Like bro, HOW DID I NOT THINK OF THAT

The worst part is that once you see the solution, it makes complete sense. You understand every line. You could probably explain it to someone else.

But coming up with it yourself? Apparently that's a different problem.

And then, just to make things worse, you solve a 1000-rated problem the next day in 10 minutes.

I guess that's competitive programming.

Sometimes the problem isn't difficult because the algorithm is advanced. You just fail to notice one small thing, and that one thing costs you an hour.

Anyway, I want to know if this happens to everyone or if I'm just exceptionally talented at making easy problems difficult.

What's the lowest-rated Codeforces problem that took you an embarrassingly long time to solve?

Drop the problem ID. I need to know I'm not alone

Hi everyone!

I'm not a high-rated guy (just ~1300), so this isn't some deep post. I just noticed that gcd and lcm show up in a LOT of problems, and every time I would forget some tiny detail and lose time on it. So I wrote everything in one place. Maybe it helps someone who is at the same stage as me, and if I got something wrong please tell me in the comments, I'll fix it :)

1. Euclid's algorithm

The whole idea is one line: gcd(a, b) = gcd(b, a % b), and when b = 0 the answer is a.

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

If you use C++17 you can just write std::gcd(a, b) (it's in <numeric>). On older compilers __gcd(a, b) works too.

It runs in O(log(min(a, b))). Reason: every two steps the bigger number becomes at least half of what it was. So even for numbers around 10^18 it's like 90 steps, nothing to worry about.

One small thing: gcd(0, x) = x. This is useful because you can start the gcd of an array from 0 and not worry about the first element.

2. LCM (and the overflow trap)

lcm(a, b) = a / gcd(a, b) * b

Please divide first, then multiply. If you do a * b / gcd(a, b), the product can overflow even when the final answer would fit. If a and b are up to 10^9, the lcm can be up to 10^18, which fits in long long but definitely not in int.

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

Also remember gcd(a, b) * lcm(a, b) = a * b. It's handy more often than you'd think.

3. GCD of an array

long long g = 0;
for (long long x : a) g = gcd(g, x);

A trick that appears a lot: "what is the gcd if I remove one element?" For this, build prefix and suffix gcd arrays:

// pre[i] = gcd(a[0..i]),  suf[i] = gcd(a[i..n-1])
// gcd without a[i] = gcd(pre[i-1], suf[i+1])

(be careful with the borders, i = 0 and i = n-1. This is where I usually get WA.)

4. Some properties worth remembering

• gcd(a, b) = gcd(a, b - a), so gcd(a, b) always divides |a - b|.
• gcd(a + k, b + k) also divides |a - b| for any k. This helps in problems where you add the same number to two values and want them to share a factor.
• If g = gcd(a, b), you can write a = g * x and b = g * y with gcd(x, y) = 1. A lot of problems become much easier after this substitution.
• While you go through an array, the prefix gcd changes at most log(M) times (M is the max value), since every time it changes it becomes at most half of the previous value.

5. Extended Euclid

It finds x and y such that a * x + b * y = gcd(a, b).

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Where it's useful:

• The equation a * x + b * y = c has an integer solution if and only if gcd(a, b) divides c.
• Modular inverse of a modulo m when gcd(a, m) = 1: run exgcd(a, m, x, y) and take x modulo m (make it positive!). This works even when m is not prime, unlike Fermat's trick.

6. Mistakes I (and probably you) make

• Using int for lcm and getting overflow.
• Multiplying before dividing.
• Forgetting that gcd(0, 0) = 0, and then dividing by it.
• Forgetting that the lcm of a whole array grows really fast, so it may not fit in long long after a few elements.

7. Problems to practice

Easy ones to start with:

• 1325A - EhAb AnD gCd
• 1498A - GCD Sum

After that, go to the problemset, filter by the tag "number theory" and rating 800 to 1500, and solve a few. I'm still doing this myself.

That's all, thanks for reading!

Question for you: what is the most interesting or surprising problem you have seen that uses gcd? I would like to add it to the list. Also if you know a nicer way to explain any part here, please share.

Hi everyone,

Unpopular opinion: below roughly 1700, Codeforces is mostly a pattern-recognition contest, not a problem-solving contest.

Look at what actually shows up in Div. 2 A to D:

Prefix sums, two pointers, binary search on the answer “Sort it and greedy” Parity, gcd, and constructive tricks you either know or don’t DP states that are variations of problems you’ve seen before

People who’ve seen 500 problems solve them fast. People who haven’t get stuck, no matter how smart they are. That makes the rating at this level partly a measure of how much you’ve grinded, not how well you think.

The counterargument (and I half believe it): patterns are skill. Recognizing which tool fits is exactly what good problem solvers do, and the same people climb to 2000+ anyway.

So where do you stand?

A) Early rating is mostly memorized patterns

B) It’s real thinking, and grinding just builds that skill

C) It’s a mix, and the balance changes as you climb

Reply with your letter, your current rating, and one problem that convinced you. I’m especially curious whether people above 2000 think the answer flips at higher levels.

Alright guys, round 3.

I have a piece of code that looks reasonable, passes the examples I tried, and has absolutely no intention of telling me where it goes wrong.

Your job is to prove me wrong.

The problem

You are given an array of positive integers (a).

You can perform the following operation any number of times:

Choose two distinct indices (i,j) such that (a_i \ge a_j), and replace

[ a_i \gets a_i-a_j. ]

Determine whether it is possible to make all elements equal.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int &x : a)
            cin >> x;

        sort(a.begin(), a.end());

        bool ok = true;

        for (int i = 1; i < n; i++) {
            if (a[i] % a[0] != 0) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

Looks fine, right?

We sort the array, take the smallest element, and check whether every other element is divisible by it.

If all of them are multiples of the smallest element, surely we can reduce them until they match.

...right?

Your mission

1. Find a valid counterexample.
2. Explain why the answer printed by my code is wrong.
3. Give the correct condition and prove it.
4. Can you solve it without simulating the operations?

Constraints:

• (1 \le t \le 10^4)
• (2 \le n \le 2\cdot 10^5)
• (1 \le a_i \le 10^9)
• The sum of (n) over all test cases is at most (2\cdot 10^5).

No random giant test case with 200,000 numbers, please. I want a counterexample that hurts my code with as few numbers as possible.

If you find one, post it in the comments and explain the reasoning. If someone beats you to it, find a smaller one.

And don't just drop code. Convince us that your condition is necessary and sufficient.

Let's see who gets it first.

Only the counterexample matters. Consider this function:

long long f(vector<int>& a) {
    int n = a.size();
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int mn = a[i];

            for (int k = i; k <= j; k++)
                mn = min(mn, a[k]);

            ans += mn;
        }
    }

    return ans;
}

The function is supposed to calculate

[ \sum_{0 \le l \le r < n}\min(a_l,a_{l+1},\ldots,a_r). ]

Assume all array elements are positive integers.

Challenge: The logic is correct, but the implementation may still fail under the right constraints.

1. Find a valid input that breaks it.
2. Explain precisely why it fails.
3. Give the smallest fix that makes the implementation correct for all valid inputs under your chosen constraints.

Bonus: Can you derive an (O(n)) solution without enumerating every subarray?

No hand-waving. Give an actual counterexample and justify it.

Okay, here's a challenge.

The code below is supposed to find the maximum element in a non-empty array. It compiles, and it looks pretty normal.

int ans = 0;

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

cout << ans << '\n';

Find a valid input for which this code fails.

Rules: - Give the smallest counterexample you can find. - Explain why the output is wrong. - Bonus: fix it without changing the overall approach.

Try to find the bug before opening the comments.

Let's see who catches it first

deleted