The-Winner's blog

Weird problem I came up with
By The-Winner, history, 34 hours ago, In English

Hello! I came up with the following problem, tried to solve it (faster than O(N2)) and failed. I asked some other people (all much smarter than me) but neither of them could solve it.

The problem statement:

There is an array of positive integers. Count the number of even length subarrays such that the first half has the same sum as the second half.

Is it possible to solve this faster than O(N2)? Maybe if we add additional constraints like the values are small or randomly generated (this one does not seem to help but I included it anyways). If it cannot be done faster than O(N2), could you provide a proof? Thank you for your time.

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

»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

If the sum of all numbers is bounded by C, we can solve the problem in O(nC64) using bitsets.

→ Reply
  • »
    »
    16 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    nvm, I don't take the sizes of the subarrays into account.

    → Reply
»
31 hour(s) ago, # |
← Rev. 6   Vote: I like it -60 Vote: I do not like it

does not apply because Comment changed

→ Reply
»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe it can be done using binarysearch+hashing

→ Reply
  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you binary search? What do you hash?

    → Reply
    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hash to the array like hashing of string, and for every i as mid i will bs on how long j such that i…j=i-j..i using hash in O(1) ,

      → Reply
      • »
        »
        »
        »
        21 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You cannot binary search that, if some j is good, that does not mean that any j smaller is also good. Also, how much of the array do you hash? If you hash too much you still don't get good results.

        → Reply
        • »
          »
          »
          »
          »
          21 hour(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Umm sry u r right I thought it as palindrome

          → Reply
»
27 hours ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

https://en.wikipedia.org/wiki/3SUM

i think it's related (or i guess check "is answer = 0" is equal hard than 3SUM)

→ Reply
  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How could one prove that 3SUM can be reduced to this problem? (i.e. solving this fast would imply solving 3SUM fast)

    → Reply