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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/contest/984/problem/D).

Solution one (https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/contest/984/submission/276544726. Crazy. Thank you for your help!

For this problem https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/blog/entry/122386) and now Python 3.12.1 is live. As an example of why that would be useful: https://mirror.codeforces.com/contest/356/submission/240013817 is accepted whilst the exact same solution (https://mirror.codeforces.com/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.