YouKn0wWho's blog

By YouKn0wWho, 5 years ago, In English

You are given an array $$$A$$$ of length $$$n$$$. Consider all $$$\frac{n * (n + 1)}{2}$$$ subarray sums of the array. Find out if all of them are distinct or not. Print "YES" or "NO".

Constraints: $$$ 1 \leq n \leq 10^5, \; 1 \leq A_i \leq 10^5$$$

Is it possible to solve this? How?

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: the upper limit for $$$A_i$$$ is just $$$10^5$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    That means the maximum subarray sum could be up to $$$10^{10}$$$. So what is the advantage here? Can you please explain a bit? Thanks.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nah, sorry! My assumption was wrong.

      Dug a bit more, finding bounds like this one, but no definitive answer.

»
5 years ago, # |
Rev. 5   Vote: I like it +25 Vote: I do not like it

If $$$n=10^5$$$ then all the sums should be reachable. Then $$$\binom{n}{2} - 1$$$ is reachable, then 1 is one some of the ends, $$$\binom{n}{2} - 2$$$ is reachable, then 2 is on the other end. $$$\binom{n}{2} - 3$$$ is reachable automatically. $$$\binom{n}{2} - 4$$$ have to be reachable, so 3 is near 1. But now $$$\binom{n}{2} - 5$$$ is not reachable (and 4 is reachable twice). So, answer is "no".

Maybe it's possible to prove the answer is "no" for all $$$n>n_0$$$ where $$$n_0$$$ is small enough to solve naively?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    or if we are talking about ICPC-style competition, to solve naively for as big n is possible and prey.

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Consider the problem on the prefix sum array; $$$1 \leq A_i - A_{i-1} \leq M$$$, while all pair differences are distinct (let's ignore the 0 that the sequence should start with, it should affect the answer by a constant additive factor). Denote with $$$f(M)$$$ the maximum $$$n$$$ such that there exists an array of length $$$n$$$ with $$$1 \leq A_i - A_{i-1} \leq M$$$, with all pair differences distinct.

Observe that if there exists a pair of equal differences: $$$A_y - A_x = A_j - A_i$$$, then there also exists a pair of pairs with equal sum: $$$A_y + A_i = A_x + A_j$$$. Similarly, if there exists a pair of equal sums, then there exists a pair of equal differences. So it's equivalent to consider distinct pair sums instead of differences.

Apparently it's some studied sequence, link. There seems to be a conjecture that for some $$$n$$$, the largest number in the array is about $$$\frac{n^3}{\log^2{n}}$$$. If we follow approximations, we want the derivative to be less than $$$M$$$; So (about) $$$\frac{3n^2}{\log^2{n}} \leq M$$$, so we can approximate (yet again), at $$$\mathcal{O}(\sqrt{M}\log{M})$$$.

With this in mind, you can run a bruteforce to find $$$f(M)$$$ about exactly, quite quickly, then for any $$$n \leq f(M)$$$ naively check all pairs (otherwise you know the answer is negative).

Honestly I'm a bit disappointed at the amount of approximations, but that's all I got.