Given an array $$$A$$$ of $$$n$$$ integers, the elements are shuffled to form an array $$$B$$$.

Let the array $$$B$$$ be $$$b_0,b_1,...b_{n-1}$$$.

We define $$$f_i = b_0$$$&$$$b_1$$$&$$$... b_i$$$.

We need to find the minimum possible value of $$$\sum_{i=0}^{n-1} f_i$$$.

Constraints:
1 <= n <= 1000
0 <= $$$b_i$$$ <= 10¹⁵

Sample input: 10, 1, 21, 1

Answer: 1

Here is my solution, which just kinda solves it, but I am not satisfied

There are basically 2 processes in the solution. Each process returns an answer. Do the first process, obtain the first answer. Do the second process, and obtain another answer. And return the min of both these answers.

Process 1:
Find the min element, and swap it with the 0th element, make it the prefix_and. Now loop on i from 1 to n-1, and find the element which gives the smallest and with pref_and, and swap that element with ith element, and now make pref_and &= ith element. Return the pref_and as the answer.

Process 2:
Consider all the pairs of 2 elements in the array, and find that pair which results in the smallest and. In this pair, swap the smaller element with 0th element and the other with the 1st element. Now loop on i from 2 to n-1, and continue as in Process 1. Return the pref_and.

The thing is that I don't know why this works. I.e., I don't have a formal proof, or a convincing enough proof. I just tried Process 1, and half the cases passed, and when I changed my solution to Process 2, the other half test cases passed.

So I just merged both these solutions, and got an AC. So not sure why this works.

Note:
Sorting in decreasing won't work. Eg: 1, 1, 2 sorting -> 1, 1, 2 optimal -> 1, 2, 1

Question

This question has been asked by adobe.

There are N number of production facilities. Each of which can produce either vaccine or an antibiotic. The ith facility can produce G[i] number of vaccines, or S[i] number of antibiotics per day.

You have a choice to decide which facility will produce which item.

You are given the task to find the number of unique ways to choose a contiguous range of production facilities, from L to R (1 <= L <= R <= N), such that the following conditions are satisfied.
1. You need to set the production units such that, each facility produces either vaccine or antibiotic.
2. The number of vaccines produced should be equal to the number of antibiotics produced.

Any two ways of production are considered different if:
1. L or R or both are different.
2. If L and R are the same, then there exists at least one facility which is producing a different item in both the ways.

Return answer module 10^9 + 7.

Constraints:
1. 1 <= N <= 10^3
2. 1 <= G[i] <= 10^4
3. 1 <= S[i] <= 10^4
4. Sum of all G[i] is <= 10^4
5. Sum of all S[i] is <= 10^4

My Approach

We could count each vaccine as a +1 and each antibiotic as a -1. Hence the question would be to find the ways to make a sum = 0 between any two indices. But I am able to find an O(n^4) solution (using subset-sum for each n^2 index pair), and with some thinking, I might get it down to O(n^3). But that's my best.

But I believe (by looking at the constraints) that the question demands some O(n^2) solution or O(n * sum(G[i], S[i]).

O(n^3) -> start from index i to n-1, and build the subset sum set, and find the ways to reach 0 at each instance. This can get it down to O(n^2*sum). But not O(n^2) or O(n*sum)

But I am unable to get to the solution. Please help.

I have these two codes for the recent Codeforces Educational round 99.

AC
TLE

Both of these have a really small difference, yet one gives AC, and the other gives TLE.

I have used vectors, which allocate memory dynamically, (even though it is a function call), but I think reducing the allocations by just 24 is too less to make any difference at all, that too I am allocating a vector of size only 4.

In the case of AC, exec time = 1.5 seconds, where as int TLE case, exec time > 2 seconds.

In the AC case, the func function is called log₂(10⁹) = 30 times, and each time one dynamic allocation is done of size = 8 (2 vectors of size 4), total = 240.

Whereas in the TLE case, the func function is called log₂(10⁹) = 30 times, and each time 24 dynamic allocations are done of size = 8 (2 vectors of size 4), total = 5760.

Why is such a small difference in allocation making such a huge difference. These differ only by a factor of 24 in memory allocation. Considering the array size of only 8 * 8 bytes, and the memory allocation is very fast, why does this make a huge difference.

I was expecting both to have similar running time, but the reality was quite different, can someone tell me the reason.