Wow, that's quite cool and interesting!

can anyone please explain this simplex algorithm? which type of problem can be solved using this algorithm?

Aliens trick can optimise it to O(NlogN). Interestingly, this was not mentioned. The dimension used to count the number of added elements in the N^2 dp solution can be removed and replaced with a parametric search to force the number of elements chosen. The fastest submissions utilise this.

I'm still unsure about the proof of the function's convexity, though it's trivial near the higher end of the elements chosen.

Let i be the index of the number being removed from the array. Hence, the new sum will be equal to sum(original sum)-arr[i]. Now, let arr[j] be the number for with the property holds true. Therefore, arr[j] = sum(new sum) — arr[j] => arr[j] = sum/2. As all the numbers in the array are integers with their maximum value being 10^6, if such an arr[j] exists, sum should be divisible by 2 and sum/2 should be less than or equal to 10^6. cnt[sum/2] simply tells whether such a number exists or not.

So, think in this manner. For every i, can it be a nice index or not ? How can we think to solve it for every 'i' in reasonable time ? Well, let's try to think what all do we need to calculate to answer that if 'i' is nice or not? So, we need to remove 'i'th element and then check whether the remaining sum is exactly twice of a single element in the array(after excluding ith element).

Finding the remaining sum is easy.(We can have a global sum variable and we will subtract a[i] from it).

Now, How to check whether this is twice of single element or not ? (hash table ?) Sure, we can have a cnt[] array which will say, cnt[5] = 3, that means three 5's are in array. (think of it as occurence/ frequency array).

Now, how this will help in finding the previous question ?

Ans: We have sum(remaining sum after excluding ith element), we can check that if(cnt[sum/2] >1 and sum%2==0). i.e.(sum should be even and there should be an element in array equal to sum/2). But there is a catch. It could happen that ith element itself = sum/2. So. we need to tackle that too. Sure, we can have nasty if else.

Tutorial presents an elegant way, which is:

Find the sum(remaining sum)

subtract this element from cnt array(by decrementing it)

Now check for if(cnt[sum/2] >1 and sum%2==0)

again add this elememt to cnt array.

again add a[i] to sum.

In case of some doubt, feel free to ask.

Great solution! Easier to understand than the tutorial one, thanks mate !

I solved the problem using exact same approach! However, I cannot understand the solution in tutorial :(

Author was not saying it was unsolvable using segment tree, just that their method was easier to code

i got TLE with these data structures :)

why are you doing f[i]/j? please explain.

Can you explain me your idea , please i want to learn

what is DP DnC ?

NOTE: I was not able to solve it during the contest, but I was able to do it afterwards.

This is one type of binary_search problem. You will encounter many such problems. General binary_search which you might have studied(or will study) in the university is done over an array of numbers. In this kind of problems, you need to perform the binary_search over the entire solution space.

For e.g.: In this problem, you can consider the entire solution space as all numbers ranging from 1 to n (as you cannot have more than "n" copies).

So, step 1 of this problem is to find the maximum number of copies which can be cut out from the the given array. Let me call this value as val. How we are going to find val, I will come back to that later. Let us move to Step 2

Step 2

Now, given that if we want to cut out val copies from the given array, can we do that ?

In order to answer this question we need to first construct a frequency array (In this we will store the frequency of all given numbers).

We need to construct an array of length k We iterate over all elements over the frequency array. First we check that whether the given key in frequency array has value more than val. If it has a value more than val. Then this can be used in the construction of the array.

But there is an interesting catch here. Since, duplicates are allowed in the given answer, we might be able to use the same value again. So, we can use that value atmost floor(value/val) number of times.

So this is basically the can function being talked in the above tutorial.

Now coming back to Step 1.

We need to figure out what values of val are valid. Minimum Val = 0 Maximum Val = n If we do a binary_search over this, then we will be able to get the MAXIMUM possible value of val.

Another thing to note is binary_search can only be done when the array(solution space) is monotonically increasing. In this case, as mentioned in the tutorial, if you can create, val copies you can also create val - 1 copies.

Here is my solution: http://mirror.codeforces.com/contest/1077/submission/45915120

As I understood pairwise distinct simply means that none of them should be counted (turned-off) twice or more.

Let's consider the first example

10

1 1 0 1 1 0 1 0 1 0

(Their index is 1-based)

As the statement, No. 3 and No. 6, No. 8 are disturbed (because both people next to them turned on)

To make sure there are nobody "disturbed", you must turn off some lights. One way : we can turn No. 2, 4, 5, 7, 9 off. This way, the testcase turns to

10

1 0 0 0 0 0 0 0 0 0

This was simple way to do the task : turn every light off which contributes making someone 'disturbed'

However, we can do better. note that if we turn No.2 off, we don't have to turn No.4 off. No. 3 is already in peace.

Note one more : if we turn No.7 off, we can make both No.6 and No.8 'not disturbed' by turning only one light off.

If we turn 2 and 7 off,

10

1 0 0 1 1 0 0 0 1 0

Nobody is disturbed.

If we turn 4 and 7 off

10

1 1 0 0 1 0 0 0 1 0

Nobody is disturbed.

We can't do better (i.e. task is impossible by turning 1 light off), so the answer is 2.

Hope this is helpful :)

cause in binary search, the solution used l = mid; if l = 2, r = 3, mid = 2 and can(mid)=true, this will be infinity loop.

so you can see the loop ends where r-l>1 and after that r maybe an answer and l must be an answer.

but at condition above, we didn't check whether r can be an answer, if it can, this will be the real answer because r>=l

I found the mistake.Here is accepted code-https://mirror.codeforces.com/contest/1077/submission/54522333

unordered_map's time complexity is O(k) where k is the size of the bucket, usually it is small hence we consider it to be O(1). In your case, there must've been alot of collison hence getting tle. Ordered_map is LogN always.