sajalhsn13's blog

By sajalhsn13, history, 3 years ago, In English

Recently I have solved this problem and here is my solution:

int n, target;
vector<int> values;
vector<tuple<int, int, int>> paired_sums;

int main() {
    cin >> n >> target;
    values.resize(n);
    for(int &v: values) {
        scanf("%d", &v);
    }
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            paired_sums.push_back(make_tuple(values[i] + values[j], i, j));
        }
    }
    sort(paired_sums.begin(), paired_sums.end());
    int lo = 0, hi = paired_sums.size() - 1;
    while(lo < hi) {
        int lo_value, lo_i, lo_j;
        int hi_value, hi_i, hi_j;
        tie(lo_value, lo_i, lo_j) = paired_sums[lo];
        tie(hi_value, hi_i, hi_j) = paired_sums[hi];
        if(1LL * lo_value + hi_value > target) {
            hi--;
        }
        else if(1LL * lo_value + hi_value < target) {
            lo++;
        }
        else {
            set<int> indexs;
            indexs.insert(lo_i);
            indexs.insert(lo_j);
            indexs.insert(hi_i);
            indexs.insert(hi_j);
            if(indexs.size() != 4) {
                break;
            }
            else {
                printf("%d %d %d %d", ++lo_i, ++lo_j, ++hi_i, ++hi_j);
                exit(0);
            }
        }
    }
    printf("IMPOSSIBLE");
}

After solving this I have come to realize that my code might not pass one test case. Suppose this paired_sums vector has some values ***** 2 3 3 4 **** (here * means other values). the target value is 6. so 2 + 4 is a potential answer. But if their indexes are not unique my code will say IMPOSSIBLE (breaks from the while loop). however, 3 + 3 is also and a potential answer and if the there indexes are unique my code will fail. But this code is accepted. I wonder how!!! Can anyone explain? Thanks in advance.

  • Vote: I like it
  • +20
  • Vote: I do not like it