MANYSUMS - Help needed | Jan Cook Off

,
1

Problem
My approach was that, a distinct sum is obtained only when adjacent elements in the range are added, say we have the range L=3, R=8 then, 3,4,5,6,7,8 the sum of 11 can be obtained by adding 5,6 or by adding 4,7 , or by adding 3,8… In my case, I’m trying to take only the pair containing adjacent elements i.e., 5,6… The other possible distinct sums are the sums obtained by taking the extreme elements twice in a pair i.e., (3,3) and (8,8)… So, the total number of pairs possible is, (number of pairs obtained from adjacent elements)+2 .i.e., (n-1)+2… My code implementing the same logic :

  #include <iostream>
#include<bits/stdc++.h>
#include<string.h>

using namespace std;

int main() {
    
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    int tc;
    cin >> tc;
    for(int t=0; t<tc; t++)
    {
    	int l,r, res,n;
    	cin >> l >> r;
    	n = (r-l)+1;

    	res = n-1;
    	if(n == 1)
    		res += 1;	//multiplying the boundary element with self
    	else
    		res += 2;

    	cout << res << endl;
    }

    return 0;
}

Can someone please explain what’s wrong with my approach…

2

For L=3 and R=8, the sum of 11 can be obtained by adding 5,6 or 4,7 or 3,8.
How about the sum of 16? How about the sum of 6? How about the sum of 14?
Maybe looking at these can give you some fresh cases to rethink your approach.

If you look carefully, you capture all the odd numbers by your approach. but only the smallest and largest even numbers. Modify it to capture the rest as well. No need to change your approach

1 Like
3

Basic observation is that if the sequence is continuous, the sums obtained will be continuous as well. Since you have to find only DISTINCT sums, take the boundary elements as given to you, multiply them by two, then calculate the number of numbers within this new range. I too was stuck on this problem, thinking of a similar approach to yours, but this observation struck me late into the contest.

3 Likes
4

Thanks for helping me find the missing test cases… The problem with my approach was that, it doesn’t capture the cases where an element occurs twice in a pair, because that sum is not obtained by adjacent element pairs… After including that case, I got an AC… :smile:

1 Like
5

Calculate the no. of elements in the range [L,R] => R-L + 1 (Lets say it is equal to X)
Then No. of pairs = 2x - 1
For eg. L=1 , R = 3 => Pairs would be (1,1);(2,2);(3,3);(1,2);(2,3)
So, ans = 5.
x = 3 - 1 + 1 = 3
2x - 1 = 5
Simple observation :slight_smile: