you are expecting prize or laddus ??? I was expecting lunch

I did Greedy. submission

I don't think it's dp. $$$d\cdot a[i]-a[j]$$$ is like adding $$$a[i]$$$ when visiting $$$i$$$, and subtracting $$$a[j]$$$ when stopping at $$$j$$$. When you stop at some cell (that's not n), the contribution of starting and stopping cancels. So you can initialize the answer to $$$a[1]-a[n]$$$ and iterate over $$$i$$$. Each non-endpoint cell contributes $$$a[k]$$$ to the answer, for some $$$k \lt i$$$. We can greedily choose each cell's contribution as the smallest $$$a[k]$$$ passed so far.

Precalculate prefix sums of 1/i. The ones remaining are the sum of 1/i for some i in [l,r].

You can expand the choose, cancel some factorials, and reduce it to a sum of telescoping sequences.

This problem was more of a math test than a coding problem. I started from a different formula:

The interpretation is that for every $$$j$$$, I let $$$a[i] = x$$$. Then, every other element at a position $$$ \lt j$$$ has a value $$$ \lt x$$$, so choose and permute that. Then the value after $$$j$$$ can also be permuted. This is the contribution to the sum of every pair $$$(i,j)$$$. Then use Hockey Stick Identity and a bunch of boring reductions to get to:

You can manipulate the expression to get O(1) solution. It turn out answer is simply factorial[n] * (sum_inv(n-1) — sum_inv(k) — (n — k — 1)/n). here sum_inv(i) = 1/1 + 1/2 + 1/3 ... 1/i. my soln

i guessed the pattern lol!

k = n-k-1

Ans = (n-1)! *( 1/(n-1) + 2/(n-2) + 3/(n-3) +...+ k/(n-k) )

Can you explain your formula for O(N) solution ?

Hey, could you give a brief explanation on how to solve this problem ? Is the editorial available ?

And similarly for next one (min, max rotation) I was able to think only 2 cases. If the white & blace form a pattern i.e. (BWBWBW or BBWWBBWWBBWW or BWWWBWWW, etc... ), then the diffenence is not available for the length of the pattern i.e (if pattern is BWWBWW, pattern length 3 etc.. then from 1, we cant choose elements at 4, 7, etc... similarly at other positions). Else if there are 2 patterns eg (BBWWBBWWBWBWBBWW, ...), then just prinnt the max — min of the array. I could not find a case where it will go wrong. Could you give a case... Actually only for cases like these, I would like codechef to provide test cases, but it seems that they dont provide as per discussion forums..

Can check convex hull trick dp?

So clearly we must start at $$$1$$$ and end at $$$n$$$, so the simplest possible process has cost:

$$$(n \cdot a_1 - a_n)$$$

Lets suppose we make a single jump at position $$$i$$$, the equation will then become:

$$$(i \cdot a_1 - a_i) + ((n - i + 1) \cdot a_i - a_n)$$$

Rewriting this, it becomes:

$$$(i \cdot a_1) + ((n - i) \cdot a_i - a_n)$$$

This equation is smaller if $$$a_i \lt a_1$$$, and we can repeat this process for some $$$j \gt i$$$. So clearly it is optimal to perform this for every $$$i$$$ that satisfies $$$a_i \lt a_{i - 1}$$$.

While it isn't necessary to get AC, we can notice that this effectively means the answer is equivalent to $$$a_1 + \sum_{i = 2}^{n} min(a_1, a_2, \ldots, a_{i - 1}) - a_{n}$$$ which is even easier to implement.

Submission

You count good pairs over all permutations(not permutations).

Permutation [1, 2, 3] adds 2 to the answer: pairs (1, 2) (2, 3)

Permutation [1, 3, 2] : (1, 3)

Permutation [2, 1, 3] : (2, 3)

Permutation [2, 3, 1] : (2, 3)

1
12
1719 4299 8716 943 3778 2499 463 6865 85 715 7852 3721
WBBWBWWBWBBW

The answer is 8631

• That was not the intended n.root(n) solution for the subtask.
• Test case — 4 is not a special one (random generator).

Regarding intended solutions

Let's call a value 'p' periodic if rotating array by p doesn't change the array. The least periodic value divides all other values. If we find this value, we can easily find the answer

• $$$O(n\sqrt{n})$$$: Find the least periodic value by naive checking for every divisor. (It's not actually nrootn)

• $$$O(nlogn)$$$: As n is also a periodic value, converge to the least periodic value from n by dividing with appropriate prime factor every time.

• $$$O(n)$$$: Use Z-algo/KMP to check whether a value is periodic.

This probably might be the first problem in at least one year that I found really enjoyable!

My solution ( I upsolved ) : Find all the bridges in a connected components , and no. of elements visitable by that node .Notice even though graph is not a tree , but for a bridge the elements can be treated in a subtree of v , where (u,v) is a bridge . We can choose the v which has greater in value to find no. of nodes in its subtree. So the connected component can be divided into x,m-x , where x is size of component visitable by v and m-x is size of component visitable by u . Now I used bitset (U can use dp as well) , notice that a component can be divided into many ways , so make 3 bitsets , one which will store which sizes are possible , 2nd one will.store which sizes are possible not considering this component , and last one will store which sizes are possible taking x and m-x in account . Transitions are in the code ( I think it's simple enough to understand ) . BTW Editorial is out . My solution

You can also store the DP for each connected component as a polynomial and use FFT to get an $$$O(n * log(n) ^ 2)$$$ solution.

Pick a random sorted array $$$A$$$ of distinct nos. Generate B using it. Then look at properties of B. Then try to see how can one get back $$$A$$$ the array you started with using this $$$B$$$.

The video should help you out.

You have to minimize the absolute difference between GCD and LCM. This implies you should try to make GCD and LCM as equal to each other as possible.

From my understanding, it generally helps to think in terms of prime factorization when dealing with GCD/LCM. You can prime factorize N. Now you want to choose X which would make GCD(N,X) as close to LCM(N,X) as possible. What if X has it's prime factorization exactly same as N, except the lowest prime factor of N?