This one has a more elaborate editorial :)

190E
653E (a little longer)
920E
1242B

all about components of complement graph :)

Not easier but actually the same. 101945655 Here is the submission for Connected Components. And 101944622 is for 0-1 MST.

Only the output format is different.

I used int at first too, and I realized the error after the first submission.

But this doesn't seem matter according to the data.

Also, $$$\varnothing$$$ has been rendered wrongly as $$$varnothing$$$.

gen please look into this and the above comment.

I suggest you simulation it by vector,vec[i] present the position occurence in s or t, which complexity may be O(n),but n<=50,So,there is unnecessary。

No. complexity is O(n) for div2 B2. here link to O(n) solution https://codeforces.me/contest/1243/submission/64410431

I hacked them by my hand :(

It spent me an hour.

no its complete. if total number of each character is even you can always find a solution within 2*n moves.check this https://codeforces.me/contest/1243/submission/64410431

Can you tell me its sufficiency? The above seems to prove only the necessity. Thank you！

You try all the numbers smaller than sqrt(n) to see if it's a divisor of n, so the complexity if O(sqrt(n)).

It is not similar to this problem, during contest i also thought it is similar to this problem but after making required change it kept giving me wrong answer on pretest then again after some modification i passed pretest but it fail on main test.

And the reason behind that in Div1B is we can have the edge in its own vertex set as well that differ the complete approach. In 1228-D it is strict that we won't have edge in own vertex set but that is not the case here

Think about it in terms of Bezout's Identity.

Let us take two integers $$$x$$$ and $$$y$$$.

Suppose, $$$n = Ax + By$$$

Let $$$g = \gcd(x, y)$$$

$$$n = Agx' + Bgy' = g(Ax' + By')$$$

This means that we can write $$$n$$$ as a linear combination of $$$x$$$ and $$$y$$$ if $$$g$$$ divides $$$n$$$.

Conversely, if we find a combination such that $$$Ax + By = g$$$, we can reach any multiple of $$$g$$$ too.

Suppose, we want to reach $$$kg$$$, then $$$(kA)x + (kB)y = kg$$$

Now, let us take $$$N = p_1 ^{a_1} p_2^{a_2} ... p_k^{a_k}$$$

Now, gcd of any two primes is $$$1$$$. This means that if there are at least $$$2$$$ primes, we can reach all the integers as $$$A p_1 + B p_2$$$

I suspect that this was the idea behind writing gcd of all the divisors. Suppose $$$g$$$ is the gcd, then we can paint $$$[1, g]$$$ with different colours but after that we cannot use any more colours.

The editorial and the intended solution went one step further and noticed that we do not really need to know the GCD of all the divisors since $$$2$$$ primes are always coprime to each other and if there is only $$$1$$$ prime, then that prime number is the gcd.

Let us generalise the question. Suppose we were given a set $$$ S = (a_1, a_2, \dots , a_n)$$$ and told that if $$$(i - j) \in S$$$, then $$$i$$$ and $$$j$$$ have to be the same colour, the solution is the gcd of $$$S$$$. We can reach any integer that is a multiple of the gcd of $$$S$$$. So we can only choose the colours in $$$[1, g]$$$. Whenever we colour $$$x$$$, the colour of $$$x + g$$$ is decided.

However, this question has an additional step that $$$S$$$ is only the divisors of an integer so this allows us to make it sharper. :)

If you use DSU with path compression, the $$$O(\log n)$$$ factor can be reduced to $$$O(\alpha(n))$$$, where $$$\alpha$$$ is the inverse Ackermann function, a function that grows so slowly that it can be considered $$$O(1)$$$ for any data set that can physically fit in this universe. But in my experience uploading DSU solutions with/without path compression, I can't seem to see much appreciable difference.

This was really nice observation and pretty easy to implement as well

Thanks Mango , your codes are the best. :)

Instead of divisors can find prime factors. Since gcd of prime factors is always 1, thus if there are more than 1 prime factor then answer will be 1 and if there is only 1 prime factor then answer will be that prime factor.

Got you! Did you find this somewhere?

Proof of this please: "Now, the answer is Number of connected components of this new graph -1."

I read your code and understood it. But can you explain the complexity since the worst time complexity seems O(n^2). Also why to find the vertex with min degree, I could just merge(union) all the vertex which have 0 weight edge between them in O(n^2)?

Why to take minimum? Edit: I figured it out.

In your code, you find value of cc before building the new graph and if this cc is greater than 1, "0" is printed, can u explain what's the reason behind finding cc here?

I solved it after reading the editorial and implemented each step as it is written, https://codeforces.me/contest/1242/submission/65618215.

Key observation: 1. If number of 0-weight edges are less than<1e5. Then you would have made DSU and answer would #connected_components -1. (This is relatively simple and almost everyone would've got it. ). Tough part was total 0-weight edges could n^2 — m (~10^10). You need to build the same DSU in some other way.

Implementation:

map<int,int> m;
for v in 1..n:
  for(int u: adj[v])
     m[root(u)]++;

This map m will hold number of edges from component of u to v.

for each component: 
    if (sz[component] > map[compnonent]) 
        unite(component, v);

Catch is to how to iterate over all components?

Wrong/sub-optimal Approaches:

1. Iterate only for entries of map. This is wrong.

1. Iterate over 1..v-1. This will TLE.

Right one

Mainatain a set for that. After the vth iteration, push v in it. All those components which got merged, remove them..

101944622 This is the code implemented according to the editorial.

Time limit is strict in this problem(190E - Контрнаступление). TLE verdict is because of high constant factor in the search complexity of C++ std::set. Replacing set by sorted vector passes all test cases(64609809).

On the editorial says "Every interval has exactly one non-self number", it means that the non-self numbers are periodic $$$($$$if n is non-self the $$$n$$$ + $$$k^{2}$$$ + $$$1$$$ is also non-self $$$)$$$; however, with $$$k$$$ = $$$2$$$, the numbers are $$$3, 9, 13, 18,...$$$ and clearly there is not a period. Thanks in advance.

I will try to give you some intuition: Yes, you are right, for every vertex we are going over all the zero-weight-components, and you are right there can be N of them. But the complexity is not N^2, here's why: The number of zero-weight-components you can have at any given time is actually bounded by M/(N — 1), the number of edges. Because in order to leave a vertex unmerged, it needs to have a degree equal to N — 1. In other words, it needs to have an edge between it and every other node. This can happen at most M/(N — 1) times. Since M is actually min(10^5, N*(N — 1)/2), you can see that M/(N — 1) cannot exceed 10^3. And now, every node after that will have all of it's edges with weight 0, because we have already used all our weight 1 edges. So every subsequent node we consider will be merged.

It's not very rigorous I know but I hope I could provide some intuition

I tried to stay as faithful as possible to the explanation in the editorial, you can check my code here: https://codeforces.me/contest/1243/submission/64548383

Type of a is long long int, that is why your second %d buffer doesn't work. Change a to just int or make %lld for a in your printf.

I also think my sentence is bit messy.

Suppose you have $$$k^2$$$ self numbers and $$$1$$$ non-self number in $$$k^2+1$$$ size interval. Then each $$$k$$$ numbers of $$$k^2$$$ self numbers will be appended to $$$s$$$ at the same time, and they will generate new $$$k$$$ non-self numbers in total. Each non-self numbers will be included in next interval($$$k \cdot i, k \cdot i + 1, \ldots , k \cdot i + k - 1$$$ th intervals), because each summation will be fit in corresponding interval as I described as formula in editorial.

Now let's see this formula:

$$$k$$$ numbers of $$$t$$$-th subinterval(size $$$k$$$) of $$$i$$$-th subinterval(size $$$k^2 + 1$$$) will be $$$(i \cdot (k^2 + 1) + t \cdot k + j) + r[j]$$$ for $$$j = 1, 2, \ldots, k$$$ where $$$r[j]$$$ is $$$0$$$ or $$$1$$$, because if non-self number is inserted at the left(or inside) of the $$$t$$$-th subinterval, then part(or whole) of the subinterval will be shifted, so that $$$r[j]$$$ is offset consideration, and $$$\sum_{j} r[j] = offset$$$.

Since $$$0 \le t \lt k$$$ and $$$0 \le offset \le k$$$, this is always true: $$$1 \le \frac{k \cdot (k+1)}{2} - t + offset \le k^2 + 1$$$. This means generated sum of $$$t$$$-th subinterval will always be in $$$(k \cdot i + t)$$$-th interval. ($$$i$$$-th interval represents $$$[i \cdot (k^2+1) + 1, (i+1) \cdot (k^2+1)]$$$.)

For 6 divisor is 2,3. then 1 3 5 (2 difference) is same color and 1 4 (3 difference) is same color.. 2 4 6 (2 difference) is same color.. All are included.. so answer 1

Can you explain your code?