Don't worry. I am there.

Problem A was not well described. The side note under the test case was explaining an unwritten test case which means it was misleading. The solution had been rejudged. I see something strange that most of the solutions get WA answer on test 3. check the announcement of the round. Whatever, it is unrated now

Literally everybody did though, I feel like it could still be rated, I don't know

Consider a triangle inside a circle inside a square.

But because the contest is running, the link can't be accessed.

3 1 2 is 6

Right

Absolutely, the Author even can`t solve A. So irritating

some people say otherwise. :D

this but with GCD, divisor and Number theory

Why not try to learn those stuff and be able to solve problems way over your rating range?

love it

This photo really swapped out my bad mood today. www

Unfortunately, the contest is unrated(((

No. The direction of the red triangle should be like the black one.

No. Notice that "each triangle base is parallel to OX".

Hehe, didn't even think of this one!

I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.

just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.

You can solve it with a little bit of DSU.

First of all, use all edges marked as $$$1$$$ to merge nodes into disjoint sets.

Then, the remaining edges — those marked as $$$0$$$ — are considered as the actual edge of the graph (in other words, after using all $$$1$$$ edges to create disjoint sets, we remove them).

From here, we'll perform DFS for the entire graph to find the components of nodes connected solely by $$$0$$$ edges.

For each component, let's denote $$$m$$$ as the component's size. Also, let's denote $$$k$$$ as the number of nodes not within the component, but can be reached from some nodes of the component due to being in the same disjoint set (mentioned at the first step). We'll add $$$m(m-1) + mk$$$ to the final answer.

The calculation of $$$k$$$ is simple — before the DFS traverse initiate $$$k = 0$$$. For each node $$$z$$$ visited, increase $$$k$$$ by $$$sizeof(dsc(z)) - 1$$$, with $$$dsc(z)$$$ is the disjoint set containing node $$$z$$$.

Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$ or $$$\mathcal{O}(n \cdot \alpha(n))$$$, based on how you construct the disjoint set union.

I used Tree DP, with:

dp[0][i]: number of 0-1 path whose lca is child of i

dp[1][i]: number of 1-path which ends at i

dp[2][i]: number of 0-path which ends at i

dp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edge

dp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge

It's also possible to do it in O(n) using dp on trees. Let dp[x][0] be equal to number of vertices to which we can access from vertice x using paths which have only zeroes as their weights and dp[x][1] same thing but which have only ones as their weights.

We can note, that each path we are looking for has a point where ones change to zeroes. Let's assume that our vertice is the vertice of change for some paths. We can easily observe that we need to add to an aswer dp[v][0]*dp[v][1]+dp[v][0]+dp[v][1].

So now the only problem is to find a way to calculate dp array. Firstly let's calculate number of paths which i mention before but only for vertices in the subtree of vertice x. That can be done as follows: if we have dp calculated for our son, and we use a path of weight y to go to him, then dp[x][y]+=dp[son][y]+1.

Now we have the answer but only for a vertice from which we started our DFS (because his subtree is full tree). Now let's start second DFS. An observation is: if we go from vertice x to its son using a path with weight y then dp[son][y]=dp[x][y]. Why? Having in memory that dp[x][y] is number of vertices we can access from vertice x using paths which have only weights y, then we see that this number can't change if we are using a path of weight y.

Lots of tree-DP problems based on paths have a standard procedure consisting of two steps:

• Solve the DP, but the DP of a vertex will only be restricted to the subtree of the vertex.
• Start changing the DP values from top to bottom, so that now, the DP of a vertex describes all paths originating at the vertex. There are only two cases — one, we have already included in our DP state, that the second vertex is a child of $$$v$$$, and the other is when the second vertex of the path is the parent of a vertex $$$p[v]$$$.

Initially, if I define $$$dp[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a valid path, and $$$dp1[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a path by navigating only 1-edges, then in one dfs we can compute these values. Then, in the next dfs, we include in both $$$dp[v]$$$ and $$$dp1[v]$$$ the case where the second vertex of the path is the parent, which gives us the final answer for vertex $$$v$$$. So after this dfs, $$$dp[v]$$$ will be the number of valid paths originating at vertex $$$v$$$ and $$$dp1[v]$$$ will be the number of valid paths originating at $$$v$$$ by navigating only 1-edges. Note that we must change the value of the parent before that of a vertex, because we want to use the second definition of $$$v$$$ for the parent in the second DFS.

Think that there is "An inner circle of a triangle". It is always possible.

Lets represent a, b, c...z as 1, 2, 3, ... 26. Now the best strategy is to club all a's together, all b's together etc. If you keep first all evens and then all odd terms, then we'll just have to worry about junction. For this you can find a pair of (even, odd) which differ by atleast 1.

Let's switch to numbers instead of characters, so the alphabet will be $$$0,1,2,\ldots 25$$$. Notice that a pair can only be ugly if one of them is odd and the other is even. First we have two cases if there're only odd or only even numbers, in that case we're done. Else we have at least one odd and one even number, intuitively we may want to minimize the touching of odds with evens so we may think about an order where first the even numbers then the odds come. This will only be possible if there's at least a pair of odd and even numbers that have a difference larger $$$1$$$ (since then we can put them in the middle and the rest can be placed arbitrarily) and obviously in the case when we have $$$0$$$ such pairs it would be impossible to order them (since in every ordering there is at least one odd-even pair), so we can see that the above statement is equivalent to that there's a valid reordering.

what about z?

Please point out the 5 pairs. TIA.

A simpler test case to prove the greedy approach wrong is:

4 4

1 5 6 9

Thank you!

I guess it is due to size of the array. As segment trees have around 4*N nodes.

Btw if possible then please explain your approach here!

If you order the array and one of the best possible solution has some pairs with both indexes in the first half of the array, you can change one index of each this pairs be indexes of the second half of the array. And this new set of pairs still is one of the best solutions.

Same way if you have some pairs with both indexes in the second half.

You can doing it using a Mergesort tree.

For each element Ai calculate the range in which it will be maximum. That is Li and Ri where Li is the highest index j < i such that Aj > Ai and similary Ri is lowest j > i such that Aj > Ai.

For each Ai, check each j in Li...i-1 to see if Ai — Aj exists between i+1...Ri using the mergesort tree. (You just have to maintain a set on each node in the Mergesort tree and check for each node in the range if the required value exists in its set).

Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once. Each query takes logN*logN time.

Thus the complexity is N*logN*logN.

Not sure if easier approach exists.

divide and conquer

I think that 53648275 is pretty short, easy to understood and O(n log n)

4 3` 1 6 9 10 test like this one will explain the WA for you, if it doesn't i made it clear here https://codeforces.net/blog/entry/66796?#comment-509109

would you please explain your approach

You need to take unique elements in string sort it and keep even indexes in first and odd indexes in second array. For example if string is "dcbab" then it would be like "ac" and "bd" and check if we can return it as "acbd" or "bdac" if two if this replacements are not possible then we return wrong answer, else we would return possible answer.

Cases when we don't get answer..
2
ab
abc

Critaical Test Cases you can check...
2
abd
acd
Output:
adb
cad
How to solve:
You can count the frequency of every letter from 'a' to 'z' in the input string... Then iterate through 'a' to 'z' and if count of it is not zero then insert it in a vector or string as you want... then take the even positions characters in vector1 and odd positions characters in vector2... then check if vector1+vector2 give you a valid solution or vector2+vector1 give you a valid solution if no one give a valid solution then, there exist no solution.. Hope you understand..

You didn't mark one of the six points in the first picture.

try case 10 5 1 2 3 4 5 6 7 8 9 10 ans=5

Try test case:

4 4

1 5 6 9

I thought of this solution but didn't have the balls to write it :D.

https://codeforces.net/contest/1156/submission/53646659 here is a solution using ternary search. it's very similar to the binary search one so i think it isn't necessary to do it using ternary search. i think the easiest solution is using two pointers technique, it's clear that it isn't optimal if we matched any number with another one has index below than n/2 because it may decrease our answer and we could match the two numbers with another two have indices above n/2, so we only have to start the first pointer from 0 and the other from n/2 and increase our answer whenever the condition happen and increase the two pointers too if the first pointer is below n/2, else we increase the second pointer until the condition happen or the second pointer reach n and here is a solution using two pointers https://codeforces.net/contest/1156/submission/53615906

if the solution has one peak or low on the middle of searching range, we can find that by ternary serach . when doing two pointer greedy rolling match p1 = 0 is optimal obviously, and choice of p2 have the property to do ternary search if choose 1 it is not good since best can only be 1 it will be optimal at some middle point and then be bad again at last part since some possible match will be in front of p2

You can Check the following testcase
2
abd
acd
Output:
adb
cad

+1

So are B and C:)

Sorry, it's my fault

After sorting the set of point x, you only need to look at begin and last N points while checking whether N can be an answer.

My submission

I fixed the checker and rejudged your submission, it's ok now.