do you have the code?

please share the code !

you need to find the position k that divides the array in a way that the product of elements from the start until element in position k = the product of all elements after this position k

Array only consists of 1 and 2, you can notice that multiplying by 1 does nothing, so we count the number of 2's in the array, to divide the array into two equal parts, there must be an equal number of twos on each part, using a second variable we can loop from N to 2 and check if the array value is 2, if it is, we add 1 to the current variable, and subtract 1 from the original count, when 2 variables are equal, means we can create equal parts by splitting the array at current position

in the multiplication, only 2 matters. So you need to divide the array such that number of 2's on left part is equal to number of 2's on right part.

Divide the array into two arrays of i and check whether the number of twos in the two arrays is the same.

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if 2 not in a:
	print(1)
	return

    for i in range(n):
        if a[:i].count(2) == a[i:].count(2):
	    print(i)
	    return
    else:
        print(-1)

for i in range(int(input())):
    solve()

I found the error in my code. I made very stupid mistake...

Got AC with single line change :(

https://mirror.codeforces.com/contest/1788/submission/192977880

wish I could spot error during contest.

Amazing! Can you explain your intuition behind this approach?

Notice that the odd differences are nested within each other, and so are the even differences. Swapping the shown pairs produces.

Wow, this is exactly what I thought about but I couldn't get the last observation of nested swapping for the same parity. It took me the whole round thinking about how to perform swapping in vain.

Nice idea, maybe better than my construction idea.

Here is my construction idea.

For some integer $$$x$$$ and $$$y$$$, $$$(x, y), (x+1, y+1), \ldots, (x+k, y+k)$$$ will give an arithmetic sequence of common difference $$$2$$$.

Arithmetic sequence from $$$x_1+y_1$$$ will cover the even part, and another arithmetic sequence from $$$x_2+y_2$$$ will cover the odd part. After some work, you can find $$$x_1, y_1, x_2, y_2$$$.

how you were able to construct this idea so fast? Will studying number theory help me with this problem?

Hi Everule,

I think I have a much simpler construction for this problem. A bit of math will tell you that the smallest sum will be 3(n + 1)/2.

Let,
S = 3(n + 1)/2

Now break up the sequence [1, 2n] in two parts [1, n] and [n + 1, 2n].
First pair is (1, S — 1)
Second pair is (2, S — 1 + 1)
and so on...
Just make sure to loop around the first number of the pair in the range [1, n] and second number in the range [n + 1, 2n]. You will generate all sums in the range [S, S + n — 1].

Proof left as an exercise for the reader. :)

https://mirror.codeforces.com/contest/1788/submission/193235034

I suppose the edi glossed over it because there are a lot of valid constructions.

For example mine https://mirror.codeforces.com/contest/1788/submission/193410581.

I realized all the sums have to be different mod n so if I increase one of the numbers by 1 and decrease the other by 2 it it will always be different mod n.

It became obvious for me after I wrote down on paper the pairings (and the sums) by the formula for n=9 (m=4, k=15).

counter-test for your last submission:

-1 -1 2 -2 -1 1

your solution returns 4 (segment [3, 6]), while the answer is 5 (segments are [1, 3], [5, 6]).

Here's how alternate solution you said works.

Note the recurrence in the official solution:

Solving it with brute-force costs $O(n^2)$ time. But we can solving it in almost linear time with a technique similar to Monotonous Queue.

We find that when there's a pair of index $$$(x,y)$$$ s.t. $$$dp_x-x<dp_y-y$$$ while $$$p_x\ge p_y$$$, if we use $$$k=x$$$ in one recurrence, we can always use $$$k=y$$$ (since $$$p_y \le p_x \le p_i$$$) with an better value, so $$$x$$$ can never be the optimal decision in a recurrence.

We use a set to maintain all pair $$$(dp_k-k, p_k)$$$ (sorting by $$$p_k$$$) possibly optimal for a recurrence. When adding $$$i$$$, we can maintain it by erasing all $$$x$$$ with $$$dp_x-x<dp_i-i, p_x\ge p_i$$$, and check if $$$i$$$ will be erased after adding $$$i$$$. And then it satisfies something similar to Monotonous Queue: if $$$p_x<p_y$$$ then $$$dp_x-x<dp_y-y$$$. So we can search for the maximum $$$p_k$$$ for the optimal decision($$$O(\log n)$$$ per recurrence).

code (Note that this solution calculate the minimum count of numbers not present in any segment you choose instead.)

precompute all the possible prefixes of the given array and then map them to the range 0 — k-1 based on their relative values (k is the number of unique prefixes). eg- if the prefixes or -3 4 2 -1 then this will be converted to 0 3 2 1.

My Submission

my solution was something like dp[i][j][dir] -> number of collisions if you are standing on the ith index, you chose the jth index before you and the jth index had a direction left/right.

It is because in the question it is mentioned that if its a tie the point will move left so if a point is equal to 2*a[i]-a[j] i will move left instead of right.

If you change $$$p_{r_k}$$$, $$$p_i$$$ would also change. Here is one example.

If $$$G'$$$ has $$$3$$$ vertices, $$$r_k=2$$$ and the edges are $$$(1, 2, 3), (2, 3, 1)$$$

$$$p_3=p_2 \oplus 1$$$ and $$$p_1=p_2 \oplus 3$$$.

Odd degree vertices are $$$1$$$ and $$$3$$$, so we get $$$p_1 \oplus p_3 = p_2 \oplus 1 \oplus p_2 \oplus 3 = 2$$$

In this case, $$$c=2$$$.

Pattern finding is the case for me. I first tried getting the sum of $$$(a_1 + b_1)$$$ with a little bit of math which turned out to be $$$\frac{(3n + 3)}{2}$$$ and noticed that from pair $$$(a_i,b_i)$$$, we can get to the next sum $$$(a_{i+1}, b_{i+1})$$$ with a difference of $$$1$$$ by adding $$$+2$$$ to $$$a_i$$$ and $$$-1$$$ to $$$b_i$$$. After randomly testing many ways to do the matching, setting $$$a_1 = 1$$$ and $$$b_1 = \frac{(3n+3)}{2} - 1$$$ worked. I also stress-tested this with a bunch of random test cases to confirm. (I left out some details which you can check in my submission if interested).

You're trying to compute the products, but this would not even fit long long if there are many 2s. If there are 1000 $$$2$$$s, the result is $$$2^{1000}$$$, which requires around 1000 bits. The long long type only supports 64 bits.

Rather than calculate the products directly, I would suggest that you instead keep track of the power of 2 that the product has, i.e., how many 2s were present in this desired product.

Suppose you take a specific subset of $$$\geq 2$$$ dots. You can then represent each dot as L or R based on whether it moves left or right, and construct a string of Ls and Rs. String always begins with R and ends with L. The number of distinct stopping coordinates for this subset is equal to the number of instances of the substring "RL" (each R stops at the same place as its next L, and each L stops at the same place as its previous R).

Therefore, the objective is to output the sum of the number of RL substrings in ALL possible subsets of size 2. However, this can be rephrased as follows: for each pair of dots $$$i$$$ and $$$j$$$, count the total number of subsets where dot $$$i$$$ and dot $$$j$$$ form an RL substring, and output the sum for all pairs.

Given $$$i$$$ and $$$j$$$, when will dot $$$i$$$ and dot $$$j$$$ form an RL substring? This arises only in a subset for which dot $$$j$$$ is the closest dot to dot $$$i$$$ (no ties allowed, since $$$i$$$ breaks ties by going left, away from $$$j$$$) and dot $$$i$$$ is the closest dot to dot $$$j$$$ (ties allowed, since $$$j$$$ breaks ties by going left, towards $$$i$$$). To count how many of these there, we can first count the number of dots, excluding $$$i$$$ and $$$j$$$, such that the presence of these dots will not prevent $$$i$$$ and $$$j$$$ from moving towards each other.

Let $$$d = x_j - x_i$$$. Dots with positions $$$< x_i - d$$$ are allowed, since $$$i$$$ still moves to $$$j$$$, and the dots with positions $$$\geq x_j + d$$$ are also allowed, since $$$j$$$ still moves to $$$i$$$. We can count how many such dots there are with two binary searches: one for $$$x_i - d$$$ and another for $$$x_j + d$$$. If we have $$$s$$$ such dots, then there are $$$2^s$$$ subsets of these $$$s$$$ dots that we can include alongside $$$i$$$ and $$$j$$$ to generate a subset (of all dots) where $$$i$$$ and $$$j$$$ form an RL pair.

The final output is the sum of $$$2^s$$$ for each $$$(i, j)$$$ pair, modulo $$$10^9 + 7$$$.

My submission: 193040606. The pw vector stores the powers of 2 modulo $$$10^9 + 7$$$. The variables lsz and rsz denote the number of allowed dots that are left of $$$i$$$ and right of $$$j$$$ respectively. The way the built-in lower_bound is defined conveniently fits with how ties are handled in this problem.

We need to count pair of dots that adjacent to each other amony all subsets, and instead of iterate the subsets, it's eaiser to iterate all pairs of dots that moves toward each other and count how many subsets contain them. (my english is bad, if you still can't understand I don't blame you QAQ)

I think you understood the question, but your approach is incorrect. Consider $$$N = 19$$$, where $$$N/2 = 9$$$ (whose digits sum to 9) and $$$N/2 + 1 = 10$$$ (whose digits sum to 1). There are many other edge cases (like if you have consecutive 9s) that this kind of approach would not be suitable.

long cannot store values larger than $$$2^{63}-1$$$. Due to how integer overflow works, after the true product you're trying to store in currProd becomes $$$2^{64}$$$, the actual value stored in currProd becomes $$$0$$$. You're trying to divide by this, so you get an error.