In such contests there is not interesting to participate alone

it is very hard to handle this type of big website and they are handling it very greatly. you should wait for sometime before this type of comment.

On the other hand, the blog post name suggests to do it as a team (in Russian), and it is a bit optimistic to expect people to put their time into reading the post itself :)

Find the Minimum Spanning Tree

3 cases Maximum Edge is K, less than K and Greater than K

If Maximum Edge is Greater than K then all the lengths greater than K in the MST are to be considered

Otherwise in other 2 cases would be min(abs(edge weight — k)) for all edge weights

I first joint the edge which is closest to k and thae applied mst.... But its giving wrong ans why

the trick from prim's MST + some greedy

There is a property that the Maximum Edge Weight in the MST of a graph is the minimum among all possible spanning trees of that graph. (Not sure if it is true when you find the MST using Prim's Algorithm, but this is definitely true when you find it using Kruskal's Algorithm)

Divide the sets into "big" and "small" sets (more or less than $$$\sqrt{N}$$$ elements). Then come up with three different methods for checking whether two big sets are similar, whether two small sets are similar and whether a big and a small set are similar.

I have an $$$O(n \sqrt{\frac{n}{64}})$$$ bitset solution. You find an implementation of this algorithm in Python here 102487844.

The key idea is to handle the most commonly occurring elements first (lets say occurring $$$ B=100$$$ times or more) using a bitset. After you have taken care of the common elements, you can forget about them and only keep the uncommon elements.

Step 0. Use a hashtable or sorting to split the elements into uncommon and common elements.

Step 1. The algorithm to handle common elements (runs in $$$O(\frac{n ^ 2}{64 B})$$$)

Let $$$m$$$ be the number of common elements. For each set make a bitset of size $$$m$$$ that marks the commonly occurring elements in that set. Now go over every element $$$a$$$ (both common and uncommon), and for each $$$a$$$ go over all sets that $$$a$$$ is in. You then use the bitsets to find some common element $$$b \neq a$$$ that occurs in 2 or more of these sets.

Step 2. The algorithm to handle only uncommon elements (runs in $$$O(n B)$$$)

Go over all sets $$$A$$$, and then go over every element $$$a$$$ in $$$A$$$. Finally go over all sets $$$B$$$ that contain $$$a$$$ and check if $$$A$$$ and $$$B$$$ contains a common element (other than $$$a$$$) using a $$$n$$$ large array.

Finally, note that by letting $$$B \approx \sqrt{n/64}$$$ you get time complexity $$$O(n \sqrt{\frac{n}{64}})$$$.

You basically need to find a cycle of length $$$4$$$ in a bipartite graph, and finding a cycle of length $$$4$$$ in a general graph can be solved in $$$O(M\sqrt{M})$$$ by enumerating in a certain way based on degree of vertices.

if you consider values as the other part of the bipartite graph, the problem now is to find a four-edges cycle.

and that's a classic problem which takes $$$\mathcal O (m\sqrt{m})$$$ time complexity.

You can speed things up using a bitset, to run in $$$O(n \sqrt{n/64})$$$ time, see here. But I doubt a brute $$$O(n^2 / 64)$$$ bitset solution would run in $$$< 1$$$ s.

Answered here

Have you tried the following:

• Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
• Write a program to generate thousands of small (!) test cases
• Using those two, find a test case where your program gives the wrong answer
• Use print statements or a debugger to see where exactly your program does the wrong thing.

98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.

The question you should be asking is "why should this be correct". You should be satisfied with a solution if you have found a proof that it is correct, not if you have no obvious counterexample. I see no reason this should be correct. Why do you think it is correct? Yeah, it seems that it should most of the time give good trees, but there is nothing about this construction that makes it obvious that it always gives the best solution.

The same happened with me as well. The problem with this approach is that it may happen that you had selected an edge which may be nearest to $$$k$$$ however this was originally greater than $$$k$$$. Due to this, there may remain some edges whose weight is originally less than or equal to $$$k$$$, which might have provided optimal answer if used.

The correct solution is:

1. Construct MST only from the edges whose weight is less than or equal to $$$k$$$. Let the closest of such edges used in MST be $$$e$$$.

2. If everything is connected, you need to check, whether there exists an edge whose weight is greater than $$$k$$$, but is closer as compared to $$$e$$$. If so, it would be better to add this edge to generated MST as well (though original MST was already connected).

3. If the obtained MST is not connected, consider edges whose weight is greater than $$$k$$$.

Hope it helps!!

It is obvious that for any almost increasing sequence (AIS) of size 3 $$$b_1,b_2,b_3$$$, we have two cases:

1. $$$b_3 \geq b_2$$$
2. $$$b_3 < b_2, b_3 \geq b_1$$$

Let us consider the first case. We can iterate $$$a_i$$$ from $$$i = 1$$$ to $$$n$$$, and at each point, find $$$a_j$$$ such that $$$j < i$$$, $$$a_j \leq a_i$$$ and the length of the AIS ending at that point is maximum. If that value of length is $$$L$$$, the new value is $$$L+1$$$.

Now to consider the second case. To do this, we find the greatest $$$j$$$ such that $$$j < i$$$ and $$$a_j > a_i$$$. Now, just need to find $$$a_k$$$ such that $$$k < j$$$, $$$a_i \geq a_k$$$ and the length of AIS ending at that point is maximum. If that value of length is $$$L$$$, the new value is $$$L+2$$$.

Both of these operations can be done by finding the last greater element with a stack, and using a persistent segment tree to find the best length.

My submission

Every time you can remove k-1 elements so count of numbers you want to remove must be divisible by k-1 and now when count of numbers is >k-1 , you can bring them down to k-1 by applying operation between them now if any b[i] is having (k-1)/2 elements in left and (k-1)/2 in right you can do last removal ok k-1 elements so ultimately you just need to check that atleast one b[i] should have >=(k-1)/2 elements in left and in right also. English is not so good :(

When I got that accepted during testing authors thought that tests (or checker) are wrong.

This may help. Previous Comment

102317815 runs in 0.140, and probably can be optimized further.

Initially I was getting TLE because of cin>> input straight into double instead of using much faster int :)

I copied your code and wanted to see if the verdict would have remained same if you had used scanf instead of cin. And that's when it happened:

your code submitted in c++ 14 gives WA on test 10

your code submitted in c++ 17 passes that test case.

I don't understand why that happened ?

Nvm, I didn't notice the fact that first element of substring must be greater than $$$k$$$, greedily extending good substrings works knowing that.

However I'm curious about solutions with D&C/Segment Tree. Is there anyone ready to explain it?

Because there are some bugs in your code. :)

it's late, but if u draw two vectors which makes eye contact, and try to move them by clockwise then u will see that it's always collinear vectors with opposite direction