Only administrators can do this, not me.

I guess Trial and Error rocks even at IG level lol.

My question is, isn't the maximum sum of weights supposed to be much bigger?

I dont know about the formulas, but you should use long long instead of int.

Bro your code won't return any output if k is equal to sum of all elements of the array.

Try

1

3 6

1 2 3

Comment if you want me to fix it

I also want to know "why?" Otherwise it's not a proof.

I did a similar claim, proves pretty much the same thing.

Suppose we took an optimal subset whose weights sum up to $$$S$$$, and let's fix some $$$(p, w)$$$ taken ($$$p \lt 1$$$). Then optimality implies that the solution without this element, is not better. We can ignore the product of probabilities on both sides of the inequality and get:

$$$S - w \leq pS \to S \leq \frac{w}{1-p}$$$. If we took $$$k$$$ elements of probability $$$p$$$, with differing weights, then denote by $$$w$$$ their minimal weight. So $$$S \geq kw$$$, and $$$w$$$ can be plugged in the inequality above to get $$$k \leq \frac{1}{1-p}$$$.

The intuition behind the whole idea was easier for me to see in contest when I tried to bound the number of elements taken for $$$p = 0.5$$$, and certainly you won't take an element if it doesn't double your current sum.

What's wrong with the proof provided?

Another solution is to sort the arrays by comparing pairs $$$(min(a_{i,1}, a_{i,2}), max(a_{i,1},a_{i,2}))$$$. We can observe that if we move the array with minimal element to the left (and among these with the least maximum), the number of inversions cannot increase, so that's optimal order

I solved this problem by just randomly trying different methods of sorting the arrays..
sort ascending by first then by second
or vice versa
or by min in pair .. etc
and then one of them by luck was successful

I didn't like the problem because I couldn't reason about it in any way but this shows that one can learn sth from this problem, like what is an exchange argument

It will be quite more difficult because we can't use exchange argument anymore

For lists of size four or more, this problem is known to be NP-complete, as you can read in, for example, "A Note on the Complexity of One-Sided Crossing Minimization of Trees" by Alexander Dobler. For lists of size 3, this problem is conjectured but not proven to be NP-complete.

A simpler solution for 1E:

When you choose a node as the root node, our answer is at least $$$\sum_{i=1}^n \frac12 s_i(s_i-1)$$$, where $$$s_i$$$ is the number of children of node $$$i$$$.

However, such a construction may not be able to satisfy some edges that pass through both the son and father at the same time. Let's consider the contribution of this situation to increasing the answer.

We set a dp state $$$f_i$$$ to represent the number of residual paths that can be uploaded through the parent when the node $$$i$$$ calculates the necessary contribution internally (i.e., the above equation).

Transfer as follows:

$$$f_u = \sum_{v\in son_u} \max(1 - [u\text{ is root}], f_v - (s_u - 1))$$$

After calculating $$$f_ {root}$$$, we must pair the extra paths pairwise, and when we choose the node with the highest degree as the root, we can prove that there must be a match to make the scheme valid:

[tbd, prove is hard]

So we can calculate $$$f_ {root}$$$ and add $$$\lceil\frac{f_{root}}2\rceil$$$ to the equation at the beginning.

using translator.

287001804

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
long long dp[MAXN]; vector<int> G[MAXN];
long long ans = 0;
void dfs(int u, int f) {
	int d = 0; for (int v : G[u]) if (v != f) dfs(v, u), d++;
	dp[u] = 0; for (int v : G[u]) if (v != f) dp[u] += max((u == f ? 0ll : 1ll), dp[v] - (d - 1));
	ans += 1ll * d * (d - 1) / 2;
}
int main() {
	int t; scanf("%d", &t); while (t--) {
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++) G[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v; scanf("%d %d", &u, &v);
			G[u].push_back(v); G[v].push_back(u);
		}
		int rt = 1; for (int i = 2; i <= n; i++) if (G[i].size() > G[rt].size()) rt = i;
		ans = 0; dfs(rt, rt);
		printf("%lld\n", ans + (dp[rt] + 1) / 2);
	}	
}

Just a FYI the source code was visible for few mins I think after the contest ended. I'm not sure was it intended or was it some kind of bug.

A bit late, but here. Consider a cycle of length k in one of the two graphs. Enumerate the vertices along the cycle as the official solution does. So the first vertex gets label 0, second 1, and so on to k-1 which is connected to label 0. Imagine that the cycle branches at the node labeled 5.

Because the graph is strongly connected if that edge is incident to vertex "e" then there must be a path from e to the node labeled 6 that does not use any edge more than once.

(why? we have used only 5->e and by definition there must be a path between any two vertices. Any path from e->...->6 that includes 5->e can be done without it because it must include e->6 after it (e->...->5->e->...->6)).

e->...->6 must have a length of a multiple of k because then we would have a cycle of length not a multiple of k.

(why? We can go from 5->6 in 1 move, or we can go from 5->e->6 in |e->...->6|+1 moves. We know we have a cycle of length k through 5->6 so |0->...->5| = 5 and |6->...->0| = k-5-1 so |0->...->5|+|5->e->...->6|+|6->0| = lk. then (5)+|5->e->...->6|+(k-5-1)=lk then |5->e->...->6|=(l-1)k+1)

So every path must conserve this coloring property and this is the only property required. (proof: collapse every node of the same color into a single node and conserve edges the only cycles remaining are of length k, longer cycles just represent going around this graph more than once).

Now we can just add edges from k -> k+1 as needed to solve the problem.

Yes, task D2D has a solution with a Segment Tree, some participants of the olympiad and rounds wrote it, but it seems to me that the solution with Dijkstra looks more concise :)

I had done the same thing initially. I suggest you read the following if you are not aware of transitive conditions for sorting.

Exchange argument: Suppose there is a correct arrangement of the arrays. The editorial proposes a solution that says the arrangement created by sorting based on sum. We now only have to prove that any optimal arrangement can be transformed into the exact arrangement based on ascending sum, without worsening the answer.

Transitivity: Now the condition of sum is transitive, i.e. sum(a) < sum(b) and sum(b) < sum(c) means sum(a) < sum(c). Now, if the correct arrangement has a pair of indices which doesn't follow this sum order, then we can argue that there is at least one adjacent pair such that they are out of order. The proof is simple. Assume there are non-zero number of elements between the closest pair of out of order pair, hence all the elements in between them are individually in correct order with either of them. Pick a random element x in between them. a < x and also x < b, so it must be that a < b, but we just assumed a > b. Hence the closest pair cannot have correct order elements in between them.Now when we flip the order of the two adjacent arrays, their ordering doesn't matter to the rest of array, but only on the relative order of the two adjacent elements which we show can be flipped without worsening the solution. We can keep arguing and flipping adjacent pairs until there is no pair out of order. Hence we can transform the correct arrangement to our preferred arrangement without worsening the answer.

Since sorting by (min, max), (max, min) or sum are all transitive conditions, all of them have a similar exchange argument and are all correct.

TL; DR: The count of inverse for ab and ba is not transitive and it cannot be guaranteed that the optimal answer will have adjacent out of order pairs (ordering based on Inv(ab) < Inv(ba)), if they are not adjacent then swapping them affects all the elements in between and thus it cannot be guaranteed to not worsen the answer.

Uphacked. Also, I think it's not hard to prepare a few of such cases with different "shifting" of the node numbers so that these "lucky" codes cannot pass. Since its average number of iterations would be something like $$$\cfrac{K^2}{4}$$$, it's very unlikely for them to run in the TL even for like 2 of such cases.

submission

Yes, sorry about this. It seems we didn't have good tests against cyclic shift checking in O(k^2), and you hacked one of the solutions, that was marked correct in polygon.

About your analysis and your commentary about checking if something is minimum/maximum, you only need to check if $$$f"(x)$$$ is greater/lower then 0 at the points where $$$f'(x)$$$ equal $$$0$$$. This makes your analysis easier, as $$$f"(x)$$$ only assumes the sign required to be maximum overall $$$x \gt 0$$$. From this you only needs to compute $$$f(1)$$$ and $$$f(99)$$$ to check the inequality, removing the need to verify points with $$$f'(x)$$$ equal $$$0$$$ for $$$x \gt 0$$$.

It's because we defined the subproblem as we can move on to each problem, no matter if we already solved them or not.

It's the same issue as https://mirror.codeforces.com/blog/entry/135370?#comment-1210592