When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

nitin12384's blog

By nitin12384, history, 14 months ago, In English

https://codeforces.com/problemset/problem/1215/B

https://codeforces.com/contest/1215/submission/60611022

Here's a problem and Um_nik's solution to it.
I was thinking about a lot of things, tried DP etc. and was unable to solve it.
Then I saw this crazily concise solution of Um_nik.
Can someone explain, what's his approach?
Like, I understood what he's doing, but didn't understand why it's working, or I should rather say, how he came to this solution.
Like the idea, or some convincing observation behind this idea.

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
14 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

He first calculated the number of prefixes whose product is positive pos or negative neg. Then to get all negative sub-arrays whose product is negative the answer will be pos * neg. All sub-arrays count is n * (n + 1) / 2 so we subtract the number of negatives to get the positives.

You may have heard of prefix sum.

»
14 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Consider two positive integers $$$l_1$$$ and $$$l_2$$$ and a function $$$f(x) = a_{1} * a_{2} * .. * a_{x}$$$. Let $$$f(l_{1})$$$ be $$$-ve$$$ and $$$f(l_{2})$$$ be $$$+ve$$$. Now, if $$$l_{1} > l_{2}$$$, it's easy to see that product of segment $$$a_{l_{2}+1} .. a_{l_{1}}$$$ is $$$-ve$$$ and if $$$l_{2} > l_{1}$$$ then product of segment $$$a_{l_{1}+1} .. a_{l_{2}}$$$ is negative. So the number of negative segments is the product of a number of prefixes with $$$+ve$$$ product and the number of prefixes with $$$-ve$$$ product.

»
14 months ago, # |
  Vote: I like it +69 Vote: I do not like it

Someone can.

It's basically a prefix sums problem.

The product is negative if and only if there is an odd number of negative multipliers (since we don't have zeroes). So if we say that the positive number is 0 and the negative is 1, we are asked to calculate the number of segments with odd/even sum. The sum on a segment is the difference of prefix sums in borders. So the sum on a segment is odd if and only if the difference of prefix sums is odd, which will be true if and only if the parity of prefix sums is different. So we need to choose one border with an even sum and one border with an odd sum. The number of ways to do it is the number of borders with an even sum times the number of borders with an odd sum.