Интересно. Хорошая идея. Я думал, не прокатит (у меня не прокатило:))

10^9 has 10 digits, which means that the highest reachable number can be 999999999; S(999999999)=81.

same mistake TT

done same and got hacked

Изначально предполагались более жесткие ограничения — количество точек до 8, радиус до 50. Использовались некоторые оптимизации перебора и умение решать задачу за O(1), когда n четно. Потом мы пришли к выводу, что следует сделать задачу более решабельной без использования математических рассуждений (т.е. чтобы мог зайти хитрый рандом или простой перебор) и ослабили ограничения. 2x действительно упало до (3/1.653 = 1.8)х, но учитывайте, что достаточно очевидное наблюдение о четном n снижает время работы до 400мс. Таким образом, ваше заявление о том, что мы подгоняем тайм-лимит под авторское решение кажется несколько безосновательным.

You learn from your mistakes. Be glad that it's only an online competition. I lost a national olympiad silver medal because pow(10,2) gave me 99, but I knew what to do now. :)

Я сам не понял. Я решал что-то вроде динамикой. Создал два массива b[] и c[]. В b хранилось сколько раз я полил i цветок, а в c — сколько раз полил i цветок, при этом этот цветок является первым в поливе. Поэтому формула имеет следующий вид: b[i] = b[i - 1] - c[i - w]. То есть данный цветок мы полили столько раз, сколько полили и предыдущий, за исключением тех случаев, когда мы начинали поливать цветок находящийся на расстоянии w от данного. То есть полив цветка на расстоянии i - w влияет на полив цветка i - 1, но не влияет на i.

I also couldn't understand the check() function,do you make it??

Suppose you're going from left to right, and the current position is i. This means that all flowers before i have already been watered enough. Now if the flower at position i is too short, then we conclude that we need to water it x times, and that there is no point in watering the flowers to the left -- it does not improve the answer. So the only choice left is to water the [i, i + w) segment x times.

Yes. Think like this. You start with the first from the left: if its high is more or equal to the solution you're trying, then there is no problem and you continue to the next one; if high is less than the solution, then you have to water that flower (solution-high)times and, of course, you water also the flowers to the right (because the ones to the left are already ok).

Hope this helps :)

The default pow() from the C++ STL (the one in <math.h>) returns a double, not an integer.

By using a double you are prone to rounding errors (if you are not aware why, research on how are doubles stored), which can sometimes offset a whole number when casting to integer (2.9999999999 can be cast to 2), which can give you a wrong result.

These rounding errors might seem rare, but in ~100 test case at least one is sure to produce it. This is why you should use your own pow function instead, something like :

long long power(int a, int b)
{
    if( b == 1 )
        return a;
    else
        return a*power(a,b-1);
}

This will return an integer, making sure you don't get a rounding error.

2 2 2 4 3 3 the maximum height of the smallest flower is 2. it does not mean the height of the smallest flower in the 1st day, but in the m-th day.

Если r  -  l  ≤ 4, то можно перебрать все варианты

The main idea of our solution is to prove, that optimal rearragement of points lies on the convex hull and brute-force it. Could you explain your solution?

I solved the problem using Sqrt-Decomposition.

What you basically do is that, break the array into sqrt(n) groups of about sqrt(n) elements. Read Here( I read it after translating to English via Google Translate ) Then for each group, you store the minimum element in an array(of size sqrt(n)), with its index.[ Complexity: O(n) ]

Repeat this process m times-> - Find the minimum element in the new array(of size sqrt(n)).[ Complexity: O(sqrt(n)) ] - Then for the minimum element in the whole array, you update the indexes from i (of the min element) to min(i+w-1,n-1) by +1. The process of updation is explained quite well in the article above.

After this process, find the minimum element in the sqrt(n) sized array, and thats your answer.

Overall Complexity: O(m*sqrt(n)) 7558102

I'm new to this concept, but I liked it a lot. All those familiar with Sqrt-decomposition, pls give me some tips as to when and where to apply this concept.

There could be other solution, which use data structure, but doesn't use binary search

link

In English

You forgot to initialize the variable sum in sum(). And you assign the result of the formula computation to long int, but it may require long long.

In addition to andreyv' remarks: You don't check that your answers are in the allowed range. From the problem statement: "Print only integer solutions that are larger than zero and strictly less than 10 ^ 9."

We can use mathematical induction on this. Suppose that by having n pairs of socks, Vasya receives a pairs of new socks and lasts for b more days since his last gift; thus Vasya lasts for am + b days.

Now, if we increment n by 1, we can ignore this extra pair of socks and let Vasya to get a pairs of socks and survive for b more days. Now we introduce our new pair of socks. If b ≠ m - 1, then our new pair of socks don't give Vasya any extra pair of socks; just one more day of surviving. On the other hand, if b = m - 1, then after using these socks, Vasya will get another pair, so this increments a and sets b = 1.

Now observe that b goes 1, 2, 3, ..., m - 1, 1, 2, 3, ..., m - 1, 1, 2, 3, ... in a cycle, so we can be sure that , since it is a repeating sequence of increasing integers of period m - 1, and it begins with 1. By a little trial and error, we get , so .

What about a? It begins at 0, and increases when n = m, 2m - 1, 3m - 2, ...; exactly when b = 1 (except for the first time where n = 1). Thus we need , so that we have a jump every m - 1 steps. Turns out that is n - 1, since we need in order for the floor to increase.

Now we have , we plug these into our formula: . Ouch, this will be messy.

Let's split m = (m - 1) + 1. Then is simply the largest multiple of m - 1 not exceeding n - 1, and will add for the remainder, so we have , exactly. Hey, this isn't bad! Adding the  + 1 remaining, we get n, the first term of the sequence.

We are left with , which is just the second term of what we want to prove. So Vasya survives for exactly days with his socks, and he really needs to start doing laundry with his possibly 199 pairs of used socks present.

How do you prove that only border points are worth looking at ?

Did you compile without -O2 locally?

Iterate the input array from left to right. if you visit a flower with the height less than your fixed height, begin some watering from there, and continue. Now when you check the height of flower, consider your watering before (I call that Y), and add Y to current flower's height.
Because of each watering ends at some position, just subtract the amount of watering that start at position i-w from Y. So it's better to store st[j] which means the amount of watering you start at jth position.

See here. Basically you're generating numbers in the form 2·2ⁱ - 1, 3·2ⁱ - 1, 3·2ⁱ, which can be shown to have XOR of 0.

Maybe you meant ∑(ai − aj) ^ 2 / 2 (i != j)?

In this case you can add to the left part ∑(ai − aj) ^ 2 / 2 = 0 (i == j), because (ai — ai) ^ 2 / 2 = 0.

pow function..got it!

You binary search for the maximum height possible for the lowest flower. And you validate the 'mid' of your binary search greedily. This is how you do it. Suppose you are at position i of the array. You already know how many times you have watered the w-length segments starting at each of 1,2,3..i-1 (you have stored these somewhere, i.e. ops[] in my code linked below). Then some of these already-watered segments will affect index i too, more specifically the segments which start at i-w+1, i-w+2,..i-1. Sum up the number of operations on these segments (let it be S). If current_height_of_i + S >= mid, then you don't need to do anything and you can move on to i+1. Else, you need to fill the deficit by watering the w-segment starting at i.

You can look at my code for reference. Hope that helps! :)

can you explain why we took mod? I mean i get the problem that we were having where the last sock wasn't getting counted(like in 10,2 example). But why mod for that? Bear with me i'm a newbie :)