"Sum" Problem From CSES

Problem: https://cses.fi/231/task/A

So if x+y+z = N, then for distinct solutions we can apply a constraint that x<y<z. Now if we iterate over all the possible values of z then the problem reduces to x+y = M, (M<N). I don’t have a proof but I observed that the number of unique solutions to x+y = M is (k-1) where M = 2k or 2k-1. Effectively we only need to iterate over the possible values of z, but here is the problem, upto which value should I iterate z so that I don’t end up including the permutations of already found solutions? Can anyone please help me?

And I also suspect that there might be an O(1) solution, some formula, if anyone knows anything about that please share that too. :slightly_smiling_face:

I don’t know about O(1) solution,
but i have a O(n) solution,
x, y, z should be distinct,
if you iterate for 1 to n, you would end up calculating 3^2 times the acutal answer.

why?

there would be 3 choices for every integer (x, y, z).

this problem is all about choices, if i ask you, to give me 2 distinct numbers that would add up to some n. how would you do?
i will do (n - 1) / 2

why?

assume n = 4,
there exists follwing pair of integers,
[(1,3),(2,2),(3,1)]
second pair doesn’t have unique values and first and last pair are same.
this pattern simply boils down to above equation.

now if we have 3 numbers we need to iterate first number from 1 to some values so that it wouldn’t calculate duplicate values.
for every first number (lets say i),
we need to find the number of valid pairs that would result in sum = (n - i) with values greater than i and they must be distinct.
more formally (i < j < k) (our triplet)
and in this way the last triplet would be ((n/3)-1,(n/3),(n/3)+1), which would result in sum = n,
if i get bigger than ((n - 1)/3) then j and k must be smaller than i (but we have already calulated the pairs with those values right?).
so i iterated i from 1 to (n / 3) - 1
and calulated all values.

My AC code
#include <iostream>
using namespace std;
 
main () {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i < (n / 3); ++i) {
    ans += ((n - i - 1) >> 1) - i;
  }
  cout << ans << '\n';
  return 0;
}

English is not my first language, sorry for bad english.

1 Like

@sirearsh Thanks for your reply :slightly_smiling_face: . I have gone through your approach, just one thing though. Why do you subtract i from (n-i)/2 in the code?

for a valid triplet we are processing all possibile triplets with having atleast an number i,
by the time we reach some i' in our code, we would have calculated all triplets with numbers less than i'.

take example i = 2 and n = 9,
valid distinct pairs for sum = (n - i) (i.e. 7)
are [(1,6)(2,5)(3,4)] and resulting triplets would be [(2,1,6),(2,2,5),(2,3,4)]
but as i=2 we have considered all triplets with values less than 2, and also our i'th pair would contain i in it (that makes it invalid as the resulting triplet would contain i twice). so we need to subtract i for our result to avoid these cases. i don’t have perfect mathametical proof but i observed this pattern.

1 Like

Thanks @sirearsh. Lets see if someone has a mathematical proof for the solution to this problem (and that the person posts it here :slightly_smiling_face:).

Let’s simplify our question. Consider the number of pairs of ordered positive integers that add to x. We can easily notice that this is x-1. Let us now consider the number of ordered triplets that may not necessarily be distinct. If the first number is i, then the number of ways to choose the rest is x - i - 1, as shown earlier. Since i must be at least 1, it is just 1 + 2 + ... + x - 2. This evaluates to \frac{(x-1)(x-2)}{2}.

Let us now consider the number of triplets such that there are 2 equal numbers. Let the repeated number be i. We can see that there exists exactly one such triplet, if 2i + 1 \le x. Number of such i is \lfloor \frac{x-1}{2} \rfloor. Notice that we have 3 ordered arrangement for each i. So to remove all triplets with some repeat element, we must subtract 3 \lfloor \frac{x-1}{2} \rfloor.

Let us consider the number of triplets where all 3 elements are the same. Notice that it will be counted in the previous term, and subtracted thrice, instead of once. So if such a triplet exists, we must add 2 to our answer. The triplet may only exist if 3 divides x.

Now we have the number of ordered triplets of distinct elements. Now we can notice that each unordered triplet will be counted 6 times, so we divide this answer by 6.

So finally , we get

\frac{\frac{(x-1)(x-2)}{2} - 3 \Big\lfloor\frac{x-1}{2} \Big\rfloor + (x\%3==0)\times 2}{6}
3 Likes

Now that’s mathematical beauty! :smile:
Thanks a lot for your response @everule1.