Auto comment: topic has been updated by Errichto (previous revision, new revision, compare).

Can we use CenTroid Decompositions for problem D div 2 ??

And why my solution for F works? I tried to prove it for an hour and only after that decided to submit anything at the end. Why is it sufficient to suggest halfplanes between nearest points (sorted by angle) and the furthest from some till 180 degrees?

771C "Tutorial is not available"? edit: nvm

Where is your code for problem C?

All tutorials are already imported from Polygon. At the end of each tutorial you can find my code in C++.

in problem "Different Names"

"If the i-th given string is "YES", make names i and i + k - 1"

i think you meant if it is "NO"

Can "Different Names" be explained a little better?

Not allowed to see the code

Can we solve problem B using BFS?

For the Different Names editorial, it should be

First generate n different names. If the i-th given string is NO, make names i and i + k - 1 equal. Note that it doesn't affect other groups of k consecutive names.

I am not allowed to see the code !!!!

My solution to the tree jump problem is O(nk). Precompute total path sums and count for each modulo for each subtree starting from bottom, then solve it again going down by subtracting your subtree from your parent node. Then sum up all the nodes, for runtime of 2nk+n

Code:25623074

There is something I don't understand about 771C - Bear and Tree Jumps solution.

what am I missing here? Isn't that the ceiling function? @.@

And, suppose k = 5 and a simple tree with edges 1 - 2 and 1 - 3. There are two paths with remainder 1, they have f(L, k) = 4 so I must add 2·4 to the answer?

Sorry if this is an extremely stupid question

Can someone explain merging and how reminder is calculated in C, please?

Can someone please explain this solution of problem A(Bear and Big Brother)

submission link : 25610202

cheater caught anantheparty 25623078 jiangIy 25623055

just find some keywords in both codes like 0x3f enjoy the rating changes :D

It's a known problem to count the sum of distances for all pairs of vertices.

Is there some book that describes it?
Where does this problem come from?

After I read tutorial for Div1-D (E in official round), I still don't get what exactly I have to do to improve the DP to O(n), especially how to calculate C_i. Can anyone elaborate that part more specifically? Thanks in advance.

Can somebody explain this line of code in the given solution for the problem 771C Bear and Tree Jumps : int remainder = subtract(i + j, 2 * depth); why 2*depth?? Sorry if it's a silly doubt. Thanks in advance :)

Can anyone explain to me this part of code in problem C? I don't understand it even after reading the editorial and the comments.

for(int i = 0; i < k; ++i)
		for(int j = 0; j < k; ++j) {
			// compute distance modulo k
		        int remainder = subtract(i + j, 2 * depth);
			// compute x such that (distance + x) is divisible by k
			int needs = subtract(k, remainder);
			answer += (long long) needs * count_subtree[a][i] * count_subtree[b][j];
		}

Can someone please try to rephrase the explanation for Div2-D Bear and Tree Jumps? I followed both the text description and the author's code.

I could not understand the part with the two imbricated for loops over k inside the DFS. The author states he's "computting distance modulo k" then proceeds to subtract 2*depth from i + j, which are remainders as far as I can tell. What distance is this? What are we actually trying to achieve here?

Any visual explanation or suggestion for how to make sense of this?

LE: Alright, I think I got it, given two subtrees rooted in vertices u and v respectively, and given: number of paths Pu from the (global) root, having length i (mod k), that end in u's subtree, as well as number of paths Pv from the (global) root, having length j (mod k), that end in v's subtree, we're trying to compute the lengths of the paths between those vertices in u's subtree where paths Pu end and those vertices in v's subtree where paths Pv end, hence we employ the LCA-like formula...

If problem div2 D. Bear and Tree Jumps asked to print the sum of the number of jumps from every node, could it still be done using one dfs? Or two dfs must be applied in that case?

Can someone explain to me what's wrong with this submission please: http://codeforces.me/contest/791/submission/25671681

How to solve Bear and Tree Jumps? Can someone please explain in detail?

In problem 771D, what is the intuition behind coming up with that particular state ? I could not come up with anything like it when I thought of it on my own. My ideas revolved around having states for a n length string and relating it with answer for (n-1) length string but I could not come up with anything that worked. Is this (the one in the editorial) a common way of choosing states for these type of problems ? If not, could you suggest how to learn to come up with them during contests ?

I am confused with statement that is given in Bear and Tree jumps's editorial...

" We know the sum of L/k because it is S/k in total. "

it might be S/k ,,, and it might not be equal to S/k...

Even the first statement in the same paragraph says that answer is "AROUND" S/k, not exactly S/k... so am I understanding anything wrong there ???

It was a very interesting contest. It is sad that it is over

Does anyone have a proof of correctness for the solution for 771B — Bear and Different Names?

I can't seem to understand why the other groups of k consecutive names are not affected if we place a duplicate at the start and end of each window of size k.

I can see that the the duplicate element at the start of each group will be shifted out at the next iteration. But why doesn't the duplicate element at the end affect the other groups?

For 771C — Bear and the Tree Jumps, how did the author manage to derive that the solution for the sum of path length between all pairs of nodes is S/k?

Also, I do not understand why f(L,k) contributes to the answer. How does it help us to minimize path length between nodes?

Please advise.

Почему данный код не проходит проверку?

27540821

Решение написано на основе кода KAN

25627860.

Why this code does not pass the tests?

27540821

The solution is based on KAN's code.

25627860

In 771C - Bear and Tree Jumps author states "For each subtree we compute the k values: for each remainder modulo k how many paths (starting from the root of this subtree) have this remainder." What does it mean that path starts in some vertex?

In problem E(Rectangular strips), can anyone explain how to do the update operations in the dp and still manage to get overall complexity of O(n) ?? I am stuck on this part. Thanks!

Hi KAN! In 771A's code 25627860, shouldn't the type of "cnt_edges" be "long long"?

I dont' know if this was a stupid question or not. Tutorial : "It's a clique if and only if edges = (vertices)*(vertices-1)/2" but in your solution you only check 'edges = (vertices)*(vertices-1)'. what's the difference ? And how could your solution work? Thank you very much!!

#include <iostream>
#include <vector>
using namespace std;
const int N = 150000;
int n, m, v_cnt, e_cnt;
vector<int> g[N];
bool used[N];

void dfs(int v)
{
    v_cnt++;
    used[v] = true;

    for (int next : g[v]) {
        e_cnt++;
        if (!used[next])
            dfs(next);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }

    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (!used[i]) {
            v_cnt = 0, e_cnt = 0;
            dfs(i);
            if ((long long) v_cnt * (v_cnt - 1) != e_cnt) {
                cout << "NO" << endl;
                return 0;
            }
        }

    cout << "YES" << endl;

    return 0;
}

This code is for https://codeforces.me/contest/771/problem/A

I have taken this code of one of the user. Can anyone tell me why values of a and b are decremented by 1 before push_back operations?

My Limak and Tree Jumping Problem is based on rerooting and has better complexity than the editorial: 92087472

Can we solve 771A — Bear and Friendship using dsu ? Someone please share solution using dsu if possible. Thanks

i solved problem C. Bear and Tree Jumps using REROOTED technique. i guess this approach is more easier to understandable than editorial solution.

sorry for necroposting.

for problem A, Bear and Big Brother, we want to find some year $$$k$$$ such that $$$a\cdot(3^k) > b\cdot(2^k)$$$

why it ends in some finite amount of operations? the editorial says we don't need more than $$$6$$$ operations