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.