Hi all

I'm pretty new to heuristic things and I tried to implement both Hill Climbing and Simulated Annealing for this begginner-friendly and considered-as-a-tutorial problem for heuristic contests on AtCoder https://atcoder.jp/contests/intro-heuristics/tasks/intro_heuristics_a.

It looks like Hill Climbing and Simulated Annealing yield similar results ( SA: https://atcoder.jp/contests/intro-heuristics/submissions/64189473, HC: https://atcoder.jp/contests/intro-heuristics/submissions/64189544 ).

I'm trying to understand why, and the only reason I could come up with was that there are "loads of neighbours" for each state ((26-1)*365 neighbours per state) so it's basically impossible to get stuck in a local optimum? I guess it could be deeper than that — I'm sure there are actually local optima (it makes sense when you read the problem), so what am I missing? Why wouldn't SA yield to better results here? Maybe I just implemented it wrong? Maybe Hill Climbing would only be bad if the algorithms were allowed to run for 15 hours? I checked locally the initial temperature and temperature decay, there are some "bad transitions accepted" early on and then very few when we get close to 2 seconds. So I don't think the problem is that my temperature + temperature decay are set up such that I'm actually never accepting bad transitions and hence degenerating to HC.

Any help is appreciated, keep it beginner friendly please :). I should add I'm not really looking for micro optimisation tips (although they're welcome*), but rather trying to grasp a better understanding of when SA >>>>> HC.

*if you just say code everything in C it'll be ever so slightly faster than C# AOT and will yield better results for both HC and SA, it won't be really helpful, I know that.

https://kenkoooo.com/atcoder/#/submissions/recent

Can't see any new submissions since the 15th of March 2025

Just wanted to share a way to solve https://atcoder.jp/contests/abc395/tasks/abc395_f. Tried 1000 random test cases to make sure it wasn't wrong against some top 10 solutions and they all matched so I think the claims I make and the proofs associated with them work but you're welcome to prove me wrong.

My idea was to:

• First satisfy $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$

• Check all the sums $$$ U_i + D_i \text{ with } 1 \leq i < N. $$$ and take the minimum sum.

• Iterate through all the indices $$$ 1 \leq i < N $$$ and remove $$$ U_i + D_i - min_{sum} $$$ to the bottom tooth in priority and then the upper tooth if the bottom tooth size goes to 0.

Two things need to be addressed:

• How can I satisfy $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$ in O(N)? If I do something like:

        for i in range(n-1):
            if u[i] - u[i+1] > x:
                cost += (u[i] - u[i+1] - x)
                u[i] -= (u[i] - u[i+1] - x)
            if u[i+1] - u[i] > x:
                cost += (u[i+1] - u[i] - x)
                u[i+1] -= (u[i+1] - u[i] - x)

Then this array $$$U = [10, 8, 6, 4, 2]$$$ with $$$X = 1$$$ is not correctly changed, since it would become $$$ U = [9, 7, 5, 3, 2]$$$. We can obviously do that $$$N$$$ times but then it becomes O(N^2).

The hack here is to do in both directions (for i increasing and for i decreasing). Indeed those "blocks" such as $$$U = [10, 8, 6, 4, 2]$$$ that make our algorithm fail are completely solved if we consider it the other way around. It looks like this:

    for i in range(n-1):
        if u[i] - u[i+1] > x:
            cost += (u[i] - u[i+1] - x)
            u[i] -= (u[i] - u[i+1] - x)
        if u[i+1] - u[i] > x:
            cost += (u[i+1] - u[i] - x)
            u[i+1] -= (u[i+1] - u[i] - x)
    for i in range(n-1, 0, -1):
        if u[i] - u[i-1] > x:
            cost += (u[i] - u[i-1] - x)
            u[i] -= (u[i] - u[i-1] - x)
        if u[i-1] - u[i] > x:
            cost += (u[i-1] - u[i] - x)
            u[i-1] -= (u[i-1] - u[i] - x)

We have to consider both directions because only considering the reverse direction would encounter a similar problem on $$$U = [2, 4, 6, 8, 10]$$$

• When I iterate through all the indices $$$ 1 \leq i < N $$$ and remove $$$ U_i + D_i - min_{sum} $$$, how do I know I won't break $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$

If I need to remove some upper tooth $$$i$$$'s length, it means that $$$D_i = 0$$$ at this point and the minimum sum $$$min_{sum}$$$ is smaller than $$$U_i$$$, so if $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is bigger than $$$U_i$$$, it will have to decrease as well, and $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$ won't break. If $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is smaller than $$$U_i$$$, well I'm bringing $$$U_i$$$ closer to them, so it shouldn't be a problem (and if I'm bringing $$$U_i$$$ below them, we get back to the first point where $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is bigger than $$$U_i$$$).

And that's it, feels very hacky, but seems to do the job and there's currently no editorial yet so I don't know if it was the intended solution.

Python submission: https://atcoder.jp/contests/abc395/submissions/63338450

C++ submission: https://atcoder.jp/contests/abc395/submissions/63338490

I was solving 2063C - Remove Exactly Two and my idea (close to the editorial) is to brute force the first vertex to remove. And then to be clever, after updating the degrees of all adjacent vertices of that first vertex, when it comes to finding the subsequent max(degrees). Using a max-heap, that's easily doable in O(nlog(n)) and the editorial partially points in that direction.

The solution I wrote is similar but consists of having this list:

    degrees_list_counter: list[int] = [0] * (max(degrees) + 1)
    for degree in degrees:
        degrees_list_counter[degree] += 1

This allows me to brute force in that manner:

    best_ans: int = 0
    for node_first in range(n):  # BRUTE FORCE THE FIRST VERTEX
        ans: int = 1
        ans += degrees[node_first] - 1
        # UPDATE DEGREES_LIST_COUNTER
        for neighbour in graph[node_first]:  # THIS IS, LIKE IN A DFS, NOT MAKING ANYTHING QUADRATIC
            degrees_list_counter[degrees[neighbour]] -= 1
            degrees[neighbour] -= 1
            degrees_list_counter[degrees[neighbour]] += 1
        degrees_list_counter[degrees[node_first]] -= 1
        degrees[node_first] = 0
        degrees_list_counter[degrees[node_first]] += 1
        # NOW THAT DEGREES_LIST_COUNTER IS UPDATED
        # FIND THE VERTEX WITH THE HIGHEST DEGREE
        i: int = len(degrees_list_counter) - 1
        while i > 0 and degrees_list_counter[i] == 0:  
            # THIS LOOKS LIKE THIS MAKES THE SOLUTION QUADRATIC
            i -= 1
        ans += (i - 1) if i > 0 else -1

        best_ans = max(best_ans, ans)

Here, I claim that the solution is linear despite this while loop:

• If there is a vertex with super high degree and all the others have a low degree, I will end up with a linear time in that while loop only once.

• If there is (strictly) more than one vertex with super high degree, I will literally never end up with a linear time in that while loop.

• If there is no vertex with super high degree, well, no need to worry about traversing that while loop.

Is this true? Or am I wrong and this is hackable?

Full solution: https://codeforces.me/contest/2063/submission/306341538

Context: Find the maximum flow through a directed graph from s to t. Capacities are all integers.

If I'm not mistaken, Edmonds-Karp runs in O(VE²); and if we don't use a BFS but a DFS instead, it runs in O(E*f) where f is the maximum flow (https://en.wikipedia.org/wiki/Maximum_flow_problem) (proofs: https://enos.itcollege.ee/~japoia/algorithms/GT/Introduction_to_algorithms-3rd%20Edition.pdf chapter 26).

I was a bit surprised that Edmonds-Karp wouldn't pass (but I guess it makes sense looking at the constraints) on a cses problem ( https://cses.fi/problemset/task/1694 ). What really surprised me is that the O(E*f) solution passed (https://cses.fi/paste/aba73738dacf15c9ac0337/ even though the capacities can go up to 10^9 so the max flow can definitely go up to 10^9). I'm now trying to hack my own DFS solution, so I tried to hardcore brute force it by generating billions of inputs and seeing if my DFS would time out on one of them: https://pastebin.com/ijUZDn3G. But that ran so fast (within a minute..) without finding any bad cases...

The worst-case example on wikipedia for that O(E*f) (https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) doesn't work for a fixed adjacency list. It just shows that if a bad actor could choose what order DFS goes through the graph, then the algorithm could become crazily slow.

I heard there is this test case generator to hack those O(E*f) solutions but I'll be honest, I don't speak Japanese and I'm not advanced enough to figure out what's happening: https://web.archive.org/web/20211009144446/https://min-25.hatenablog.com/entry/2018/03/19/235802

TL;DR: this code passes https://cses.fi/paste/aba73738dacf15c9ac0337/ even though it's O(E*f) and the capacities can go up to 10^9; please hack me.

(EDIT: my comment in the code saying "DFS to find shortest s-t path" is wrong, it's a remnant comment from when I was coding BFS)

This code gets MLE but only uses, if I'm correct, three arrays of size n <= 2*10^5 for that problem: https://codeforces.me/contest/2038/problem/B.

Am I missing something?

I thought one long long was 8 Bytes and therefore 3*8*2*10^5 = 48*10^5 would be 4.8 MB?

Would love to be enlightened, thanks! Note that I'm not asking how to solve that problem, but rather why in the world I am getting MLE. Link to the MLE verdict: https://codeforces.me/contest/2038/submission/292217786

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void solve() {
    long long n;
    cin >> n;
    vector<long long> a(n), a_copy(n);

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

    auto is_feasible = [&](long long target) -> bool {
        for (long long i = 0; i < n; i++) {
            a_copy[i] = a[i];
        }
        bool first_time = true;
        while (a_copy[0] > target || first_time) {
            first_time = false;
            for (long long i = 0; i < n; i++) {
                long long a_i = a_copy[i];
                if (a_i > target) {
                    long long excess = ((a_i - target) / 2) + ((a_i - target) % 2);
                    a_copy[i] -= 2 * excess;
                    long long nxt_idx = (i + 1) % n;
                    a_copy[nxt_idx] += excess;
                }
            }
        }
        return all_of(a_copy.begin(), a_copy.end(), [&](long long x) { return x == target; });
    };

    long long total_sum = accumulate(a.begin(), a.end(), 0LL);
    vector<long long> targets;

    for (long long i = 0; i <= total_sum / n; i++) {
        targets.push_back(i * n);
    }

    long long l_ptr = -1, r_ptr = targets.size() - 1;
    while (l_ptr < r_ptr) {
        long long mid = (l_ptr + r_ptr + 1) / 2;
        if (is_feasible(targets[mid] / n)) {
            l_ptr = mid;
        } else {
            r_ptr = mid - 1;
        }
    }

    if (r_ptr == -1) {
        cout << -1 << endl;
        return;
    }
    cout << total_sum - targets[l_ptr] << endl;
}

int main() {
    long long n_tests;
    cin >> n_tests;

    for (long long test_nb = 0; test_nb < n_tests; test_nb++) {
        solve();
    }

    return 0;
}

I saw somewhere that if you were to pick randomly the next element to insert when building a binary search tree from an array, you would have 1/3 on the left and 2/3 on the right (or conversely) on average. I get that the best case is half-half and the worst case in everything in one of the branches but how do get formally to the 1/3-2/3?

I am looking for a problem that applies shortest path in a DAG using topological sort to get linear time (V + E). I couldn't find this kind of problem on the internet even though that's (I assume) a relatively standard problem, am I not looking correctly? Do you guys have an idea where I could find such an algorithm on an online judge (hackerrank, leetcode, codeforces, codechef, I don't particularly care about the platform).

Ideally, some edges are negative, otherwise Djikstra also works.

Thanks!

This problem https://codeforces.me/contest/285/problem/B says "Consider all glasses are moving simultaneously during one shuffling operation.".

I don't understand how simultaneously makes sense, I solved the problem assuming one shuffling operation means moving the glasses in sequence* but I was just wondering if there is something I misunderstood.

* "if glass at position 1 goes from 1 to 2 and glass at position 2 goes from 2 to 3 then if marble was in glass at position 1 it ends up in glass at position 3" was my assumption.

Thank you for your help.

Consider this problem (https://codeforces.me/contest/984/problem/D).

Solution one (https://codeforces.me/contest/984/submission/276446617) uses two recursive self-explanatory functions (compute_f, and compute_max_xor) that use unordered_map for memoization. It does not pass (2000 ms TLE).

Solution two (https://codeforces.me/contest/984/submission/276446798) is the same from a logic point of view (dp corresponds to compute_f and dp_max corresponds to compute_max_xor), except it uses Dynamic Programming. It passes in 546 ms.

I thought it could be that different because of hash collisions. Some people hack some other people by using clever inputs that blow up hashmaps ... but adding a random custom_hash did not help whatsoever.

Is the overhead of using an unordered_map that HIGH? Big enough to bring a x4 in time? Or am I missing something else?

Thank you!

EDIT Keeping memoization but using a 2D array instead of an unordered map did the trick. https://codeforces.me/contest/984/submission/276544726. Crazy. Thank you for your help!

For this problem https://codeforces.me/gym/103708/problem/G, the "proper" way to solve it is to use Multi Dimensional Ternary Search.

If I were to solve it with random search (it passes: https://codeforces.me/gym/103708/submission/274048924 — very much easily), would this be considered a valid solution? I feel like saying no would invalidate the use of string / polynomial hashing but saying yes feels very much wrong.

What is the CP community opinion on this?

Consider this code:

#include <stdio.h>
#include <float.h>

int main() {
    double a = 100.0;
    printf("a: %.6lf\n", a);
    return 0;
}

It should print 100.000000 right? It does on https://www.onlinegdb.com/online_c_compiler, it does on my local computer. But on codeforces: https://i.imgur.com/P2CCY7Q.png

I'm more of a Python user so maybe I'm missing something big and it's actually not a bug?

Coincidently I was wondering a few weeks ago why codeforces was using such an outdated version of Python (https://codeforces.me/blog/entry/122386) and now Python 3.12.1 is live. As an example of why that would be useful: https://codeforces.me/contest/356/submission/240013817 is accepted whilst the exact same solution (https://codeforces.me/contest/356/submission/233016779) was not a few months ago. Probably not the best example since PyPy was able to go through for that particular example but I thought it was worth sharing.

The general consensus is that competitive programming is competitive so if you're going to choose a slower language (like Java or especially Python) you need to be ready to deal with the potential setbacks and advantages of your chosen language. It's fair to say that Codeforces isn't supposed to accommodate your language choice by increasing the time limits according to the language especially if it's a poor one that is known to be slower than something like C++. HOWEVER, Python version on codeforces is currently 3.8 (out for 4 years) and versions 3.11 and 3.12 both bring speed improvements (3.11 for a lot of stuff (https://docs.python.org/3/whatsnew/3.11.html#:~:text=Python%203.11%20is%20between%2010,See%20Faster%20CPython%20for%20details.) and 3.12 for comprehensions (https://docs.python.org/3/whatsnew/3.12.html#:~:text=This%20speeds%20up%20execution%20of%20a%20comprehension%20by%20up%20to%20two%20times.)). I know loads of people use PyPy (and it does seem to work very well, cf. https://i.imgur.com/v9iOJnw.png) but it would seem relevant to allow newer versions of Python (**I would even argue it will help lower the CPU demand on codeforces servers since both versions are known to be faster** so realistically ... why not ...).

I've just started codeforces so maybe this has been discussed before but I haven't seen any topics talking about it and i honestly don't think there'd be any drawbacks in getting a newer, faster version of Python on the website.