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!"

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}$$$.
• Say that there are $$$n$$$ problems. Define the array $$$\mathrm{ratios}\left[i\right] = \frac{\mathrm{solves}\left[i\right]}{\mathrm{solves}\left[i+1\right]}$$$.
• The imbalance is calculated as $$$\mathrm{stdev}\left(\mathrm{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 information of contest ID, contest starting time in UTC timezone, 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 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 Unix in UTC and 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.

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.

It's time for some statistics. Out of the last 10 rated contests, the highest imbalance belongs to Codeforces Round 1089 (Div. 2) at around 1.341. The rated contest with the highest imbalance that is also "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 FSTed. The rated contest with the lowest imbalance is Codeforces Beta Round 1.

Goodbye, that's it for now, also here's a reminder to not go harassing the contests with the high imbalance.

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;
}