Reading the editorial of this atcoder problem agc028_b (editorial), I noticed that the solution was similar to the solution of D. Score of a Tree (editorial).

Both of those problems define a function to calculate a value based on a random initial configuration of elements. The problems then ask for the sum of values for every possible initial configuration. The editorial solutions involve calculating the expected value of the result and multiplying it by some other value (the contribution of each element or the amount of possible configurations).

My question is, how can we relate the expected value of a result to the exact sum of every possible result? Do you guys have other problems involving that technique or sources that explain it?

Thanks!

I'm aware that if $$$2x \leq y$$$ then $$$x \leq \lfloor y/2 \rfloor$$$, and that if $$$2x \geq y$$$ then $$$x \geq \lceil y/2 \rceil$$$

I usually remember that by writing examples like $$$x \in$$$ {$$$2,3$$$}, $$$y=5$$$. But I don't quite get the logic behind that and I'm not sure if it's a general rule that $$$kx \leq y \rightarrow x \leq \lfloor y/k \rfloor$$$.

Any help with understanding that or resources to read about it would be greatly appreciated. Thanks!

I figured you'd have to check the edges that are saturated, and if there's a path of saturated edges with the same capacity, choose any of them. But I'm having trouble on cases where there may be many of those paths or the saturated edges are connected by non-saturated edges with higher capacity in between.

I came up with checking every path that has at least one saturated edge, but I think that would be too slow as it may check too many edges just to get one of the saturated ones, in something like $$$O(|minCutEdges| \cdot E)$$$.

How do you do it efficiently?

If it's relevant, I'm trying to solve this problem (can find the optimal profit but can't print the solution): szkopul — Travel Agency (biu)

I'm trying to solve this problem 103708A - Anya's gifts, in more detail, we need to do this.

Given an array $$$A$$$ of length $$$n$$$ ($$$n \leq 10^5$$$, $$$a_i < 2^{50}$$$), divide it into two subsequences $$$X$$$ and $$$Y$$$ such that $$$(x_1 \oplus ... \oplus x_{|X|}) + (y_1 \oplus ... \oplus y_{|Y|})$$$ is maximum. Print the maximum $$$xor\text{_}sum(X) + xor\text{_}sum(Y)$$$.

It is obvious that for each $$$2^p$$$, if the ammount of elements $$$a_i$$$ such that $$$a_i \text{ and } 2^p = 2^p$$$ is odd, the answer will always have its $$$p$$$-th bit on. I don't know how to handle the case where it's even.

Any help would be appreciated. Thanks!