The origins of the idea

So, I participated in Codeforces Round 1089 (Div. 2) recently and solved ABC1, and when I moved on to C2 I thought to myself "wow, that's a big difficulty jump!"

The process

After the contest was over, I also thought about whether there is a way to put a number to this, and after a bit of thinking, I came up with the following process:

• Take the solve counts of each problem (the green numbers at the bottom of the Standings page). Call it $$$\mathrm{solves}$$$. This is used as an estimation for how easy the question was.
• Say that there are $$$n$$$ problems. Define the array $$$\mathrm{ratios}\left[i\right] = \frac{1+\mathrm{solves}\left[i\right]}{1+\mathrm{solves}\left[i+1\right]}$$$. (The $$$1+$$$ part is to prevent division by zero.)
• The imbalance is calculated as $$$\mathrm{stdev}\left(\ln\left(\mathrm{ratios}\right)\right)$$$.

So I decided to test this method on some recent contests. After playing around, I decided that this function was good to use and then I wanted to make a CSV containing the contest ID, contest starting time in UTC, contest title, and measured contest imbalance.

The way I did this was to first check an already existing CSV file for any data already computed, then for each contest not recorded in the CSV file:

• Query the Codeforces API for standings information.
• For each participant, if their score is greater than zero for problem $$$i$$$, count that as an accepted solution to compute the $$$\mathrm{solved}$$$ array.
• Use the contest information returned by Codeforces API contest.standings to get the contest start time as a Unix timestamp in UTC, and the contest title.
• Use the $$$\mathrm{solved}$$$ array we computed to calculate imbalance as given above.
• For any contest, if the API gives status code 400 (e.g. contest 1597) or returns empty standings (e.g. contest 399), write that to a file named status400.txt so that these contests can be skipped on the next run.

You can find the source code, computed CSV, and status400.txt in this GitHub repo.

The meaning of the measure itself

Now, what is imbalance actually measuring? I like to think of it as an estimate of how rough the difficulty jumps between problems are. For example, if until some problem each problem is slightly harder than the last but the next problem is much harder, this makes the imbalance high. On the other hand, if the difficulties progress smoothly the imbalance will be low. The difficulties of the problems are estimated by accepted counts.

Imbalance is technically a logarithmic scale since the standard deviation computation computes $$$\ln\left(\mathrm{geometric standard deviation}\right)$$$.

Some statistics

The mean contest imbalance is ~1.1489, with a standard deviation of ~0.5816 (sample) or ~0.5814 (population). The median is ~1.0451, belonging to Codeforces Round 557 (Div. 1) [based on Forethought Future Cup - Final Round] and Codeforces Global Round 17.

Out of the last 10 rated contests, the highest imbalance belongs to Codeforces Round 1101 (Div. 2) at around 1.676, while the lowest imbalance belongs to Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2) with around 0.538.

The planned-rated contest with the highest imbalance that is also supposed tıo be ordered by difficulty is Codeforces Round 421 (Div. 2) due to the fact that the author solution failed on a hack, and most of the accepted solutions for C FST'd. The rated contest with the lowest imbalance is Codeforces Beta Round 1 at around 0.078.

Here's a histogram showing the distribution:

Goodbye, that's it for now :3

PS: I got IP banned multiple times trying to adjust the interval between each request 🥀

I'm studying for TÜBTİAK's second step of Middle-School Competitive Programming branch, which is OI-style. I have translated the problem statement into English, keeping all Turkish proper names.

In the cute town of Ilgınkent, there are $$$n$$$ regions and are connected by $$$n-1$$$ roads, forming a tree-like structure. The distance between a region and all of its neighbors† is equal to 1 unit.

The mayor, Ms Kaya, has decided that it would make certain tasks easier if she organizes the complicated tree structure into roads‡ of length $$$k$$$. Ms Kaya wants you to design an algorithm to determine, for a given $$$k$$$ and a tree $$$T$$$, whether it is possible to split up $$$T$$$ into roads of length $$$k$$$.

  1
  |
2-3-4-6
  |
  5

examples of roads of length 2 are 1-3-5, 2-3-4, and 3-4-5, but not 1-3-6, 2-3-6. An edge may not be in two roads at the same time, making 1-2-3, 2-3-4; 2-3-4, 3-4-6 etc. invalid.

Input.

The first line contains the integer $$$n$$$. The next $$$n-1$$$ lines contain a description of Ilgınkent, where the line "u v" (w/o the quotes) means that there is a road between region $$$u$$$ and region $$$v$$$.

Output.

The output should be a single line — a bit array made of $$$0$$$ and $$$1$$$. For every $$$k$$$ output $$$1$$$ if the tree can be split up into roads of length $$$k$$$ and $$$0$$$ otherwise, left to right.

Constraints.

• $$$2 \le n \le 10^{5}$$$
• $$$1 \le k \le n-1$$$
• $$$1 \le u, v \le n$$$

//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pb push_back

const int MAX = 1e5+5;

int N, sz[MAX], cur[MAX];

vector<int> adjlist[MAX], num[MAX];

bool bad = 0;
 
void dfs(int a, int b) {
    sz[a] = 1;
    for(int& t: adjlist[a]) 
     if (t != b) {
        dfs(t,a);
        sz[a] += sz[t];
        num[a].pb(sz[t]);
     }
    if (sz[a] != N) 
        num[a].pb(N-sz[a]);
}

bool ok(int K) {
    if ((N-1) % K != 0) 
        return 0;

    for (int i = 0; i < K; ++i) 
        cur[i] = 0;

    for (int i = 1; i <= N; ++i) {
        int count = 0;
        for (int& t: num[i]) {
            int z = t % K; 
            if (z == 0) continue;
            if (cur[K-z]) {
                cur[K-z]--; 
                count--;
            }
            else {
                cur[z]++; 
                count++;
            }
        }
        if (count) 
            return 0; 
    }
    return 1;
}
 
int main() {
    cin >> N;

    for (int i = 1; i < N; ++i) {
        int a,b; cin >> a >> b;
        adjlist[a].pb(b); 
        adjlist[b].pb(a);
    }

    dfs(1,0);

    for (int i = 1; i < N; ++i) {
        if (ok(i)) cout << 1;
        else cout << 0;
    }
    cout << endl;
}