Sum of two values CSES

Problems and Contests
#1

Hi,

I am currently working on Sum of Two values, and I am not sure when to increment i and j in the while loop. I tried to do a for loop, but it gave me a time limit error.

This is my code:
#include <bits/stdc++.h>
using namespace std;

#define setIO() ios_base::sync_with_stdio(false); cin.tie(NULL);

const int MAX_N = 2e5;
int num_of_numbers = 0;
int desired_sum = 0;
unsigned long numbers[MAX_N];

void solve() {
    setIO();
    cin >> num_of_numbers;
    cin >> desired_sum;
    vector<pair<int, int>> ans;

    for (int i = 0; i < num_of_numbers; i++) {
        cin >> numbers[i];
    }

    for (int i = 0; i < num_of_numbers; i++) {
        for (int j = i + 1; j < num_of_numbers; j++) {
            if (numbers[i] + numbers[j] == desired_sum) {
                ans.push_back(make_pair(i + 1, j + 1));
                break;
            }
        }
    }

    if (ans.size() >= 1) {
        cout << ans[0].first << " " << ans[0].second << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

void solve_optimized() {
    setIO();
    cin >> num_of_numbers;
    cin >> desired_sum;
    vector<pair<int, int>> ans;

    for (int i = 0; i < num_of_numbers; i++) {
        cin >> numbers[i];
    }

    sort(numbers, numbers + num_of_numbers);
    int i = 0;
    int j = i + 1;

    while (i < num_of_numbers && j < num_of_numbers) {
        if (numbers[i] + numbers[j] == desired_sum) {
            ans.push_back(make_pair(i + 1, j + 1));
            i++;
            j++;
            break;
        }

        else if (numbers[i] + numbers[j] < desired_sum) {
            j++;
        }

        else {
            i++;
        }
    }

    if (ans.size() >= 1) {
        cout << ans[0].first << " " << ans[0].second << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

int main() {
    solve_optimized();
}

Note: solve - for loop
solve_optimized - while loop
Please let me know. Thanks!

#2

Again, try and calculate the complexity of your code and see if it should or shouldn’t TLE.

#3

it dosent tle, it just gives a wrong answer, but I am not sure how to fix it.

#4

Have you tried downloading the test cases yourself?

#5

yeah, but I dont get how to fix it…

#6

Is it because the test cases are too large?

#7

ya, mostly all of the test cases that are too large are either getting tle or wrong answer…

#8

Could you describe your algorithm for me please?

#9

Step 1:
Iterate through the numbers, and try to find the sum. If it does, then add it to the pair.

Step 2:
If J is at the end of the numbers, add 1 to i

Step 3:
if none of these conditions are satisfied, Add 1 to J

#10

this is the algorithm i am following

Updated code:
#include <bits/stdc++.h>
using namespace std;

#define setIO() ios_base::sync_with_stdio(false); cin.tie(NULL);

const int MAX_N = 2e5;
int num_of_numbers = 0;
int desired_sum = 0;
unsigned long numbers[MAX_N];

void solve() {
    setIO();
    cin >> num_of_numbers;
    cin >> desired_sum;
    vector<pair<int, int>> ans;

    for (int i = 0; i < num_of_numbers; i++) {
        cin >> numbers[i];
    }

    for (int i = 0; i < num_of_numbers; i++) {
        for (int j = i + 1; j < num_of_numbers; j++) {
            if (numbers[i] + numbers[j] == desired_sum) {
                ans.push_back(make_pair(i + 1, j + 1));
                break;
            }
        }
    }

    if (ans.size() >= 1) {
        cout << ans[0].first << " " << ans[0].second << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

void solve_optimized() {
    setIO();
    cin >> num_of_numbers;
    cin >> desired_sum;
    int a = 0, b = 0;
    vector<pair<int, int>> ans;

    for (int i = 0; i < num_of_numbers; i++) {
        cin >> numbers[i];
    }

    // sort(numbers, numbers + num_of_numbers);
    int i = 0;
    int j = i + 1;
	

    while (i < num_of_numbers && j < num_of_numbers) {
        if (numbers[i] + numbers[j] == desired_sum) {
            // ans.push_back(make_pair(i + 1, j + 1));
	    a = i + 1;
	    b = j + 1;
            i++;
            j++;
            break;
        }
        else {
	    if (j == num_of_numbers - 1) {
	        i++;
	    	j = i + 1;
	    }
	    else 
		j++;
        }

        /* 
	else {
            i++;
        }
	*/
    }


    if ((a != 0) && (b != 0)) {
        cout << a << " " << b << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

int main() {
    solve_optimized();
}
#11

Please format your code so that it’s easier to read first.