around 115

I solved it with Polynomial Hashing with DP Segment Tree.

First calculate the lexicographic order of substrings. Now dp[i][j] = best possible result if (i,j) is your first substring. You will need to maintain suffix maximums to query over only substrings lexicographically larger than first string

It's easy, dp[i][j]=max score if s[i..j] is your last substring. Now the transition is dp[i][j]=score[j-i+1]+max(dp[k][l]) where l<i and s[k..l]<s[i..j]. Now notice that you can easily check this using LCP and Suffix Array. Then it's just some case handling depending on whether the LCP is s[k..l], s[i..j], or both, or neither. Notice that you can maintain prefix max for each row of the DP to quickly get the answer. Then you can take max over all (and 0, of course).

Submission (uncommented)

Sorting (Lexicographically), then calculated all substring which are same because we cannot select substring with same values we need to select strictly increasing in lexicographic order.

Used Fenwick tree to find prefix maximum score.

Now to select each substring (l , r). We need to find the a substring which ends before l (Non overlapping) and is Lexicographically smaller which was maintained by sorting already. So i used fenwick tree to find maximum score till [0 , l-1] and updated current score at r because no substring starting before r can be selected with current subrting. This update also makes a maximum update from (r , n). Please view code for better understanding.

Code for reference Click Here

Solution

Also what would be the CF rating for this problem ?. My guess is 2100+ .

This is what we did(without any Complicated data structures):

Define dp[i][j] as the maximum score for the suffix [i..n] such that the first substring starts at index i and has a length j.

Now, step 1 is to precompute longest_common_prefix[i][j] as the length of the longest common prefix of substrings starting at i and j respectively for all i,j. This can be done naively in O(n^3) time.

Now, coming to the transitions, to calculate dp[i][j], we will iterate for k, that is, the starting point of the next substring. Now if lcp[i][k] is 'L' and s[k+L] > s[i] OR if L>=j, then we can say that dp[i][j] = max (dp[k][L+1] + a[j], dp[k][L+2] + a[j]....).

This can be done quickly by maintaining suffix maximums.

There is no need for seg tree or fenwick tree. Just sort all the substrings in increasing order. Consider a substring $$$[i,j]$$$ as an interval $$$(i,j)$$$. Every interval has some priority (which is of course, determined by its position in sorted order).

Now imagine placing intervals in increasing order of their priority (i.e from smallest lexographical order to largest). Suppose you're at the $$$i^{th}$$$ substring. Let $$$l(i)$$$ and $$$r(i)$$$ denote the left and right endpoint of the substring.

Define $$$dp[r(i)]$$$ as the maximum score you can get if you place the $$$i^{th}$$$ substring at the last operation, so, $$$dp[r(i)] = max ( dp[j] + cost[r(i)-l(i)+1] )$$$ for all $$$j$$$ such that $$$j \lt l(i)$$$.

This is because at last I'm placing the substring $$$[l(i) , r(i)]$$$, so before that I must have placed a substring $$$[l(j),r(j)]$$$ such that $$$r(j) \lt l(i)$$$ (substrings must be non overlapping), and since I'm placing substring in increasing order, its guaranteed that $$$j^{th}$$$ string will be smaller than $$$i^{th}$$$ string (there's a small catch here but you can easily fix it ;) ).

Since there are $$$O(n^2)$$$ substrings and for every substring I will iterate through all $$$j$$$'s, there are only $$$O(n)$$$ right endpoints, so it would take $$$O(n^3)$$$ time.

Note that you can sort all substrings using trie, so that would also take $$$O(n^3)$$$ time :)

When will the final result come?

Same as what I did. Did you fail at test 11 too?

You forgot to resolve 3-length cycles, i guess...

Consider the array,

[1,2,3,1,2,3,1,2,3,1,2,3, 2,3,1]

is your answer 2 for this case?

Even handling n=4 was quite tricky imo.

We failed at test 5.

1. For each triple a,b,c form 3 groups based on mod 0.
2. All elements with mod 3 = 0 should be a, mod 3 = 1 should be b and mod 3 = 2 should be c.
3. All elements that are not a,b,c need to converted so add that many operations.
4. Now swap (a,b) from Group1&2 and similarly (b,c) from Group2&3 and (a,c) from Group1&3. This will each cost 1 swap, so add number of swaps.
5. Atlast add 2 swaps for every cycle (b,a,c) or either (c,a,b).
6. Add number of operations for elements that are still not matched.

But this got WA, can anybody get why?

Code Link : Beautiful Array

Vichitr Any update regarding this?

How do you get this?

It can be proven that it is always optimal to choose the Path as the longest path from among the vertices of the set. (Try to prove by contradiction, it is quite simple)

So the problem boils down to finding the longest path in a given subset of the tree. For this, we used a concept called auxiliary tree (which is basically, making a tree which contains all the vertices of a subset of the tree along with some more vertices to make sure all the LCAs are present in the auxiliary tree). The size of such auxiliary tree is never more than twice the size of the subset of the tree. The weights of the edges of this auxiliary tree is the original distance between the 2 points in the original tree. Thus we can simply find the longest path using 2dfs method.

However, solving each query in MlogN gave us TLE, and we had to use O(1) per query LCA, that was quite strange in my opinion, we lost rank 1 due to those penalties :(

Edit: Refer to radoslav's video on Auxiliary Trees

We will publish it on CodeDrills Discuss and contest pages. Regionals would also publish it on their sites.

When $$$N$$$ is odd then the answer is 1. Now if $$$N$$$ is even then the middle two elements in the array(sorted order) must have the same parity. Consider the number of selections where the smaller middle element is $$$i$$$ and the larger middle element is $$$j$$$ with $$$i \lt j$$$ (We will have to handle $$$i = j$$$ separately). We have to chose $$$\frac{n}{2}$$$ elements from $$$[1,i]$$$ and $$$\frac{n}{2}$$$ elements from $$$[j,m]$$$ with at least one $$$i$$$ and one $$$j$$$ respectively. Number of ways for $$$[1,i]$$$ are $$$i^\frac{n}{2} - (i-1)^\frac{n}{2}$$$ and for $$$[j,m]$$$ it is $$$(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}$$$. Also you have to arrange them in the array so pick $$$\frac{n}{2}$$$ places for the smaller elements.

Your answer is now $$$\sum_{i \lt j,\; j-i\; is\; even} \binom{n}{\frac{n}{2}}[i^\frac{n}{2} - (i-1)^\frac{n}{2}] \cdot [(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}]$$$ plus the number of arrays where both middle elements are equal.

To find arrays with middle elements equal, just subtract all arrays where middle elements are unequal from the total number of possible selections. To find the number of arrays where middle elements are unequal, you need to compute the above expression for all $$$i \lt j$$$.

By EOD according to this message on the telegram group.