Yeah I really hope!

CF's servers U_U

"hope it will be rated" — M_H_H_7 April 2, 2018

It is not the first time dude. we are everywhere ^^

next week

N < 6

In the case of n>5, you just printed two different correct trees...

This formula is actually always work for the "rep(i,n-1) printf("%d %d\n",i,i+1);" type of graphs. You could easily check this.

U have to read condition one more time =)

The first tree is a correct case.

oddCnt = 7 and evenCnt = 1, therefore the answer is 1, which is correct because you can choose the root vertex and all edges will be covered.

In the first case, the algorithm will give the correct result — 1

Can you post the link?

Yes

Because the number of test cases is small, only around 25 — 50 lol

You can unite in groups of 2 for price 1, then in groups of 4 for price 2 etc. This is for n that's power of two. For all other n for some steps you just don't unite last two groups. Straightforward code is O(logn).

1. Write brute force code(O(n^3)) to generate answer for n=2 to 20.
2. Search sequence on OEIS.
3. Profit!

If you don't want to use OEIS, then here is a solution -
Lets assume you have a MST for a complete graph with n - 1 nodes. Main observation is when you add the node with number n - 1 to the graph (resulting in graph with n nodes), the new edges will not replace any edge of the previous MST. So, you can just choose the minimum cost edge from this new node. So we have . And is just the maximum power of 2 that devides n. So our final answer is sum of maximum power of 2 that divides i, for i ranging from 1 to n - 1. Now all you need to do is, insted of counting them one by one, count how many of them will have 2^x as the maximum divisor. Then just add 2^x × count to answer.
As = count of numbers in [1, n] that are divisible by 2^x. So number that are divisible by atmost 2^x but not 2^x + 1, that is just (assume all divisions are integer division).
So the answer is .

cal(int n){ if n == 1 return 0; return n / 2 + 2 * cal (n — n / 2) ; }

got AC with few line of codes :))

You missed #include <bitset>.

Painting says that for n <= 5 there no incorrect trees. For n >= 6:

First tree -
1 2
1 3
1 4
4 5
4 6
...
4 n

There incorrect algo gives 3. Correct answer is 2.

Second tree -
1 2
1 3
1 4
... 1 n

There both algos give 1.

"scratch your head" a little bit more

Iterate over each number, saving its prime divisors in a visit array, once you find a number that has a divisor that came before keep increasing that number by 1 and try again.

Once you found a good number for that element, the rest of the array(to the right) can be any number you want, let x be the number of elements left in the array, start from 2 with the visit array you have, find x good numbers and put them in the elements left.

If you didn't find any bad one, just do nothing.

1. Generate primes up to x (I used x = 10^7);
2. If nums a[1]..a[i — 1] are coprimes then a[1]..a[i] are coprimes if and only if all primes divisors of a[i] doesn't exist in set of prime divisors for a[1]..a[i — 1].
3. Use set of prime divisors. For current index i you can factorize a[i]. While a[i] cannot be used, you can increase a[i].
4. If there was increase of a[i], then a[i + 1]..a[n] can be initialize with first primes that don't exist in set.

Example:
5 2 4 1 5 10

a[1] = 2. Set is { 2 } a[2] = 4. 4 = 2^2. You need to increase. a[2] = 5. Set is { 2, 5 }

There was increase. So a[3] = 3, a[4] = 7, a[5] = 11.
And answer is 2 5 3 7 11.

Please wait until system testing ends.

No OEIS needed. 36926019

Don't worry, everybody who use OEIS write MST too

Got one too!!

In bipartite graph, the number of minimum-vertex-cover is equal to the number of maximum-matching.

A tree is a bipartite graph, when you regard nodes with depth of different parity as different bipartite parts.

Therefore, the answer by "wrong algorithm" is true if and only if the calculated minimum is equal to the number of maximum-matching, and is false otherwise.

To explicitly find a case where the calculated minimum is not equal to the number of maximun-matching, you can refer to the Hall's Theorm Hall's Theorm