I recently invented a new game called Guess the Statement.

Here's how it works:

1. Open up a Div. 4 or Div. 3 or Educational.

2. Do NOT read any of the tasks.

3. Open the editorial.

4. For each task, read the code, and try to guess what the statement was.

5. Read the tasks and see how close you were!

Recommended contests to start with:

• Codeforces Round 886 (Div. 4)

• Codeforces Round 918 (Div. 4)

• Codeforces Round 570 (Div. 3)

• Educational Codeforces Round 46 (Rated for Div. 2)

I believe this is the only way to enjoy low-rated problems.

I found an unusual similarity between three problems: a POI 2016 task, an Educational F, and a Div. 3 G. While these problems are formulated in different ways, they can be solved in incredibly similar ways. I'm not certain the authors were plagiarizing, this could be a case of parallel thinking. Spoilers ahead.

POI 2016 Parade

Author: Unknown

This task was the oldest one. The task can be summed up as follows: Given a tree, choose a path that maximizes the number of "adjacent" edges. "Adjacent" as in one of its endpoints is in the path, while the other is not. The path has to consist of 2 or more nodes.

For a given path $$$v_1, v_2, ..., v_k$$$, the number of adjacent edges is $$$(\sum_{i=1}^{k} deg(v_i) - 2) + 2$$$. This is because for each node, its contribution is its incident edges, except the $$$2$$$ which are on the path. The $$$2$$$ at the end is to compensate for the ends of the path which only have one neighbor in the path. So let $$$dp(u)$$$ be the best path from the node $$$u$$$ to a node in its subtree. The transitions are: $$$dp(u)$$$ = $$$deg(u) - 2 + \max dp(v, 0)$$$, or $$$0$$$ if $$$u$$$ is a leaf. The answer will simply be the maximum $$$dp(u) + 2$$$ or maximum $$$deg(u) + dp(v_1) + dp(v_2)$$$ for $$$v_1$$$ and $$$v_2$$$ being $$$2$$$ distinct children of $$$u$$$. There is an edge case where the tree is a star. (We have to subtract 1 from the answer).

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

vector<int> adj[200'000];
int dp[200'000], ans = -1000;

void dfs(int u = 0, int p = -1) {
    int mx1 = 0, mx2 = 0;
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        if (dp[v] >= mx1) {
            swap(mx1, mx2);
            mx1 = dp[v];
        } else mx2 = max(mx2, dp[v]);
    }
    dp[u] = mx1 + adj[u].size() - 2;
    ans = max(ans, mx1 + mx2 + (int)adj[u].size() - 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u,v; cin >> u >> v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
    dfs();
    ans += 2;
    int leaves = 0;
    for (int i = 0; i < n; i++) leaves += adj[i].size() == 1;
    if (leaves >= n-1) ans--;
    cout << ans;
}

Education Round 74 1238F - Максимальное поддерево (rated 2200)

Author: Roms

The problem is as follows: Define a good tree as a tree such that for each node, we can assign it a segment, and two nodes will share and edge iff their segments intersect. (As in there exists a point that belongs to both of them). You have to find the largest possible good subtree (connected subgraph) of the given tree.

The most crucial observation is as follows: in a good tree, each node has at most $$$2$$$ non-leaf neighbors. Its leaf neighbors will be contained in its segment, and its $$$1$$$ or $$$2$$$ non-leaf neighbors will share one of its endpoints. If there are $$$3$$$ non-leaf neighbors, They would have to form a cycle. So every good subtree corresponds to a path in the original tree, and the value of a path is equal to $$$(\sum_{i=1}^{k} deg(v_i) - 1) + 2$$$. Sound familiar? We can write the same DP, just with $$$-1$$$ instead of $$$-2$$$. Code can be found 296277443

Codeforces Round 991 (Div. 3) 2050G - Развал дерева

Author: AVdovin

This problem is suspiciously similar to Parade. Given a tree, find the biggest number of connected components you choose a path and delete all nodes and edges in it. This problem is equivalent to the POI problem, the only difference is that you can choose a path with $$$1$$$ node. Code is 296277443. Note: the number of different characters between 296277443 and 296278465 is only 2 (!).

Are there some good segment DP tasks on cf?