cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2016 · MediumSorting and two pointers

Balanced Weights with Duplicates

National Olympiad — National round (2016 season)

Submission name: scales.cpp

Solve in Editor →

Problem summary

Count ways to choose two distinct physical weights for the left pan and one for the right so that their sums balance. Equal values on different weights represent different choices; the left pair is unordered.

Input

n followed by the n positive weights.

Output

The number of balanced selections.

Constraints

3 ≤ n ≤ 20000; 1 ≤ weight ≤ 10^8.

Worked example

Input and output for the worked example discussed below.

Input

5
2
1
3
2
3

Output

4

Solution analysis

  1. Sort the weights and compress equal values into pairs (value,frequency). For each distinct right-pan value, search for two smaller values adding to it using two pointers. Positive weights guarantee the right-hand weight cannot also belong to the left pair.
  2. If the pointer sum is too small, increase the smaller value; if too large, decrease the larger. On equality with different values add frequency[left]×frequency[right]×frequency[target]. If both pointers meet, use choose(frequency,2)×frequency[target].
  3. For weights [2,1,3,2,3], left values 1 and 2 can be selected in 1×2 ways and the right 3 in 2 ways. Thus there are 4 balanced selections, without double-counting the order of the left weights.

Why it works

The two-pointer scan visits every unordered value pair having the target sum once; multiplying frequencies counts exactly its physical choices.

Complexity: O(n log n + d²) time and O(n) space, where d is the number of distinct weights. Compression substantially reduces repeated-value inputs; the full n≤20000 bound permits the quadratic two-pointer scan.

Watch out. Use long long for counts. Equal left values need a combination, not frequency squared. A weight may not be reused on both pans.

Commented C++17 solution

An independently written complete program with standard headers.

// The two-pointer scan visits every unordered value pair having the target sum once; multiplying frequencies
// counts exactly its physical choices..
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    vector<int>input(count);
    for(int&weight:input){
        cin>>weight;
    }
    sort(input.begin(),input.end());
    vector<int>value;
    vector<long long>frequency;
    for(int weight:input){
        if(value.empty()||value.back()!=weight){
            value.push_back(weight);
            frequency.push_back(0);
        }
        frequency.back()++;
    }
    long long answer=0;
    for(int target=1;target<int(value.size());target++){
        int left=0;
        int right=target-1;
        while(left<=right){
            int sum=value[left]+value[right];
            if(sum<value[target]){
                left++;
            }
            else if(sum>value[target]){
                right--;
            }
            else{
                long long pairs=left==right?frequency[left]*(frequency[left]-1)/2
                                                :frequency[left]*frequency[right];
                answer+=pairs*frequency[target];
                left++;
                right--;
            }
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗