I'm currently solving some problems over at kattis, in particular the Add 'Em Up task.
A quick summarizing:
You are given an array with $1 \leq n \leq 100000 $ elements and an integer $2 \leq s \leq 200 000000$. You want if there exists two elements $x_i,x_j, i \neq j, $ in the array such that $x_i + x_j = s$. However, there's a twist that you can flip certain numbers to obtain a new number. For example, if $ x_i = 51 $ then a flip would yield $ \bar{x}_i = 15.$ Still, you can just use an element once, so $ x_i + \bar{x}_i = s $ is not an accepted answer.
Looking at the worst case scenario, our new array would contain $2n$ elements, $ \{x_1, ..., x_n, \bar{x}_1, ..., \bar{x}_n \}. $
I've written an algorithm that works, but it's not efficient enough. I believe it's $ \in O(n^2) $.
If $ N = \{x_1, ..., x_n, \bar{x}_1, ..., \bar{x}_n \} $, and if $x_i $ doesn't have a flip, then $ \bar{x}_i = $ 'NF'. (NoFlip, str).
for i in range(2*n) do
for j in range(2*n) do
if (j-i) % n != 0 and N[i], N[j] != 'NF':
if N[i] + N[j] == S:
return True
return False
How can I make the code more efficient?
I've tried:
- Removed all elements $ \geq S $ first
You want if there exists two elements…
seems to lack a word as well as use the wrong numerus.) $\endgroup$