w0rm's blog

codechef practice problem
By w0rm, 14 years ago, In English
hi guys ,

i am trying to solve this practice problem at codechef .The only approach which i came upto is 
brute forcing which is giving me WA (due to overflows i guess ).
It would be helpful is you push me into right direction .

thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I see O(N^3)  solution - generate all possibles sums when for each sum check how much pairs it can give:


while (l < r) { if (x[l] + x[r] > s[i]) r--; else if (x[l] + x[r] < s[i]) l++; else { cur++, l++, r--; } }
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Also you need to sort x before doing this
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    One may also take a pair of elements and check how many more pairs with that sum can be produced.
    The latter part can be done with a data structure like stl::set. That's O(N2)  in total.
    → Reply