The problem consisted in taking an array $A$ containing $N$ numbers where $A_n \in [-100,100]$ and

]]>The problem consisted in taking an array $A$ containing $N$ numbers where $A_n \in [-100,100]$ and returning the minimum absolute value we could get by summing or subtracting all numbers of $A$.

I've tried this three times, the first I've run out of time because I was doing other things at the same time and also was getting ready for bed. Then I woke up in the other day and went to the university thinking about the way I was trying to solve and then started to code before my Software Engineering class. However, When my teacher arrived at the classroom I've stopped. That afternoon I went over my code again, discovered what I've done wrong and corrected it. And then, finally, my Dynamic Programming approach worked.

However, it was not the most efficient. The requested time complexity was $O(N*max(|A|)^2)$, and space-complexity $O(N * \Sigma_{i=0}^{n}|A_i|)$, and my solution had both space-complexity and time-complexity equals to $ O(N * \Sigma_{i=0}^{n}{(|A_i|)}) $. However since my solution was completely different from all the others I've seen in the internet I wanted to share here.

Well, to do a Dynamic Programming approach we first have to define our recursive function. What I've did was redefining the problem, so instead of finding the most close to zero we can get, I've generalized the call to be the most close to any $K \in [0, \Sigma_{i=0}^{n}{|A_i|}]$ we could get after doing $i$ operations.

The main idea is, to get to a absolute value of $K$, at step $i$, we can either do that by summing the last value with $A_i$, when that step tried to get close to $K-A_i$ or we can do that by subtracting $A_i$ from our best attempt to get close to $K+A_i$.

So our best solution function, let's call it $bs(A,i,K)$, where $A$ is the array, $i$ is the step and $K$ is where we are trying to get can be defined by:

$$ \begin{align} \text{bs}(A,i,K) = \text{mostCloseTo}( & \\ & K, \\ & |\text{bs}(A,i+1,|K+A_i|)-A_i|, \\ & |\text{bs}(A,i+1,|K-A_i|)+A_i| \\ ) \end{align} $$

And the $mostCloseTo(K,a,b)$ function returns the value between $a$ and $b$ that are the closest to $K$.

To do the code is just the same thing for all *DP* algorithms, to avoid stack overflow, we have to unwrap the recursion. After that this is my final code:

I did not passed the performance tests, however some of those tests were off by just a few milisseconds. Maybe by little optimization we can achieve this with the same algorithm. The only one that went really wrong was the medium2 with 6+ seconds.

Well, the other solutions I've found on the internet is the official Codility Solution and blog post. The way they did was by reducing the problem in a sub-multiset problem, really similar to the Knapsack Problem, which is a well known problem that is solved in polinomial time with Dynamic Programmin. It's better than mine but in general, I liked my idea because is more closely related to the actual problem.

]]>I did. Today.

Now you are probably expecting something like **rule the galaxy** or **extinguish world hunger**.

Well, this is obviously really hard but it's not what I want to talk about today.

Today I want

What is the hardest thing for you to do? Have you ever asked yourself?

I did. Today.

Now you are probably expecting something like **rule the galaxy** or **extinguish world hunger**.

Well, this is obviously really hard but it's not what I want to talk about today.

Today I want to talk about something more simplistic:

I do not have enough

disciplineto be successful.

I know, **successfull** is a loose concept, but what I mean is that I feel like I am not doing anything good just because I cannot hold on to some boring tasks (that are essential to accomplish success in certain objectives of my life). I need to stop, rethink and restart doing things.

One of these tasks is sharing the little knowledge that I have, or at least sharing experiences.

I love sharing knowledge and experiences, I really do. But it seems that I just do not know how to do it properly.

I've started blogging three times in a desperate attempt to be able to communicate with the rest of the world

and always stopped. This is so bad, isn't it?

So here I am. Starting all over again. I'll try to share everything that I learn, that I experiment or that I feel I have to talk about. I'll try. Here and again.

What i need?

- I need to be more pragmatic.
- I need to write about what I'm learning so I can learn it deeper.
- I need to be persistent in the tasks I set myself to do.
- I need discipline.

And I'll seek for this.

]]>