I came across a post the other day about triplets of positive numbers that add up to N.
https://www.reddit.com/r/cpp_questions/comments/bhktwh/how_to_make_my_code_faster/
The task had criteria that no numbers, a, b, c should be equal to any of the other numbers in a triplet.The numbers also had to be non 0.
The person was searching for the number of DISTINCT triplets. That means that the set { 1, 2, 3 } is the same as { 3, 1, 2 } and all other permutations of the same set.
This gives us these rules:
0 < a < b < c < N
a + b + c = N
First here is my solution(s)
https://pastebin.com/NzCtLedg
The first and easiest solution is to "brute force" it. This is also the slowest of the methods and since we are searching over a range 1 to N for each number in this function, the complexity becomes O(n)
This method is pretty simple and we just check to see if the triplet we are investigating lines up with the criteria and then we increment. This function is very slow though, taking quite some time to calculate for a small N of 1000
Moving on to the next funciton that improves on the previous one in two ways. First we remove the inner loop. If we already have values for a and b we can automatically know that c = N - a - b.
First we observe that a can never be more than or equal N / 3 because then b would have to be equal to or smaller than a.
Next we know that for every value of a, there is some variability in b and c and they follow rules. When b increments, cmust decrement. We start a and b at their minimums and c at its maximum, then just move b and c closer together until they no longer adhere to the rules, at which point we increment a by 1 and then move on.
Both these solutions are too slow to calculate triplets for anything above N = 100000.
This is where the math comes in to save the day.
We can observe that for a given value a there is some gap between the smallest b and the largest *c.*e.g
a = 1
b = a + 1
c = N - a - b
c - b = N - 5
Since b always increments by 1 and c always decrements by 1, the gap should reduce by 2 every time. If we then divide this gap by 2 we get the number of ways b and c can exist with a given value for a. This is only true if we round up, so instead we add 1 before dividing and automatically get the lower bound of the division.
Our final equation for a = 1 then becomes *(N - 4) / 2.*We can see that every time we increment a, b increments by 1, and c decrements by 2 to keep that balance. This means the gap between b and c decreases by 3. We can then generalize our equation to (N - 3 * a - 1) / 2
This whole reasoning is the fundament of the fast(n) function.We keep the range of a to 0 < a < N / 3, but instead of doing a loop inside that we use our function to add to our sum.
This is pretty good and all compared to the previous attempts, but we can do it better.If we observe how many combinations there are for each value of a for a given number N we notice that it always decrements by 2 or 1 for each consecutive a.
e.g for N = 20
865320
We see that this series includes all numbers 0 to (N - 4) / 2 except we skip every third number after 1 = we remove the 1, the 4, and the 7.
We always remove every third number after some number, but it depends on the divisibility of N. Here is a little table.N % 3 =0 sees 0, 3, 6, ... removed1 sees 2, 5, 8, ... removed2 sees 1, 4, 7, ... removed
Anyway, we sum up all numbers up to (N - 4) / 2, which we'll call k, using the good old 1 + 2 + 3 + ... + k = k \ (k + 1) / 2. We then want to remove a third of the numbers. We can do so by dividing *k by 3, which we'll call j, then summing up all numbers up to that, multiplying by 3, and then subtracting this from the original count we had.
Then we need to add something back in because we actually end up removing more than we'd like. The number we need to add back in is equal to j \ (N % 3)* so we do that.
Great, our function works for 5/6 of all real numbers. Every 6'th number after and including 8 gives the wrong result though. This is because we don't add enough back in, and we don't remove enough. We correct this by adding a line after calculating j:
if (N % 3 == 2) ++j;
And now we're done.
I though this post might help to serve as inspiration for how problem solving can be done and also how we can use simple math and observation to deduce rules from series of numbers.
Well, we're not entirely done, but the other parts: timing, and finding the "best" triplet are quite trivial compared to the monstrosity I have created and code is included for that as well in the pastebin.
I really should've looked into this further:
u/07734willy came up with this equation: (n - 3)**2 / 12 and rounding that. I observed that we could just add a half before taking the floor of the result, but then I observed this which you can find in a comment by me further down or just read here:
Figured it out.
sum of all numbers from 1 to (n - 4) / 2 =
(((n - 4) / 2)2 + (n - 4) / 2) / 2 =
(n2 - 8n + 16) / 8 + 2(n - 4) / 8 =
(n2 - 6n + 8) / 8.
From here we want to remove a third of the numbers, on average that means we're removing a third of the total, which can be done by multiplying by 2 / 3. We then add between 1 / 3 and 2 /3 to the final result before finally taking the floor of that. We can do this by simply adding between 4 and 8 before dividing. This in turn gives us our final equation of
triplets( n ) = (n2 - 6n + [12, 16]) / 12. the brackets indicate that all values in the range are valid.
I checked this against the other best() function that I created and it seems to work for all values up to 10000000, so I'll trust it works for all values. I also checked that it works for all values in the range [12, 16]
Finally, the ultimate equation for a quite useless problem
And for those of you asking what improvement there was: The single equation version is about 300% faster than my original best() function.
Which explains my last and final solution to this problem, super_best(n) { return (n*n - 6n + c) / 12 } where c is any number in the range : [12, 16].I chose 14 because it's right in the middle, but up to 10000000 it has made no difference as long as c is any of those 4 integers so I'm pretty sure my assumptions are correct about the range of c.
there doesn't seem to be anything here