Блог пользователя The-Winner

Автор The-Winner, история, 7 часов назад, По-английски

Hello! I came up with the following problem, tried to solve it (faster than $$$O(N^2)$$$) 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(N^2)$$$? 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(N^2)$$$, could you provide a proof? Thank you for your time.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
6 часов назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

If the sum of all numbers is bounded by $$$C$$$, we can solve the problem in $$$O\left(\frac{nC} {64}\right) $$$ using bitsets.

»
3 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i don't know but first thing i think about and i think it's wrong or need some optimization if i use sliding window to get the number of even length then make pointer in the first of the window and another in the end of the window then i do ( right — left ) / 2 if it was even then count++

ok i don't have Competitive programmers friends to ask them so i give my idea to ChatGPT and it will take O($$$n^2$$$) too but gpt said use prefix sum i really didn't understand it well but i hope i was useful or i have discussion in this blog and try to find optimal solution and learn more things

GPT code


void solve(vector<int>& arr) { int n = arr.size(); int count = 0; for (int left = 0; left < n; left++) { for (int right = left + 1; right < n; right += 2) { int mid = (left + right) / 2; int sum1 = accumulate(arr.begin() + left, arr.begin() + mid + 1, 0); int sum2 = accumulate(arr.begin() + mid + 1, arr.begin() + right + 1, 0); if (sum1 == sum2) { count++; } } } cout << count << "\n"; }
»
118 минут назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe it can be done using binarysearch+hashing

»
16 минут назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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