fork download
copy 
  1. // Author: Balakrishnan V
  2. // Given a set of pairwise sums, this function computes the inverse -
  3. // (the set of numbers that correspond to these pairwise sums).
  4. // If multiple solutions exists, one of them is output.
  5. #include <iostream>
  6. #include <stdio.h>
  7. #include <algorithm>
  8. #include <cstring>
  9. #include <math.h>
  10. #include <vector>
  11. using namespace std;
  12. #define MAXN 7
  13.  
  14. int N;
  15. double sum_A;
  16. vector<double> S;
  17.  
  18. // The indices for a(0)+a(1), a(0)+a(2), ..., a(0)+a(N-2)
  19. int chosen_indices[MAXN-1];
  20.  
  21. vector<double> solution;
  22.  
  23. bool dfs(int id, int to_choose) {
  24.     if(to_choose==0) {
  25.         double sum_indices = 0;
  26.         for(int j=0;j<N-1;j++) {
  27.             sum_indices += S[chosen_indices[j]];
  28.         }
  29.         vector<double> A(N, 0);
  30.         A[0] = (sum_indices - sum_A) / (N-2);
  31.         for(int j=1;j<N;j++) {
  32.             A[j]=S[chosen_indices[j-1]]-A[0];
  33.         }
  34.         vector<double> all_sums;
  35.         for(int i=0;i<N;i++)
  36.             for(int j=i+1;j<N;j++)
  37.                 all_sums.push_back(A[i]+A[j]);
  38.         sort(all_sums.begin(), all_sums.end());
  39.         bool ok = true;
  40.         for(int i=0;i<(N*(N-1))/2;i++) {
  41.             if(fabs(all_sums[i]-S[i]) > 1e-9) {
  42.                 ok=false;
  43.             }
  44.         }
  45.         if(ok) {
  46.             solution = A;
  47.             return true;
  48.         } else {
  49.             return false;
  50.         }
  51.     }
  52.  
  53.     if(id>=(N*(N-1))/2)
  54.         return false;
  55.  
  56.     chosen_indices[to_choose-1]=id;
  57.     if(dfs(id+1, to_choose-1))
  58.         return true;
  59.     return dfs(id+1, to_choose);
  60. }
  61.  
  62. int main() {
  63.     printf("Enter the number of numbers.\n");
  64.     cin>>N;
  65.     if(N<=2 || N>MAXN) {
  66.         printf("N should be between 3 and %d\n",MAXN);
  67.         return 0;
  68.     }
  69.     printf("Enter all the %d pairwise sums.\n", (N*(N-1))/2);
  70.  
  71.     sum_A=0;
  72.     S.resize((N*(N-1))/2);
  73.     for(int i=0;i<S.size();i++) {
  74.         cin>>S[i];
  75.         sum_A+=S[i];
  76.     }
  77.     sort(S.begin(), S.end());
  78.     sum_A /= N-1;
  79.     if(dfs(0,N-1)) {
  80.         printf("Solution found.\n");
  81.         sort(solution.begin(), solution.end());
  82.         for(int i=0;i<N;i++)
  83.             printf("%lf ",solution[i]);
  84.         printf("\n");
  85.     } else {
  86.         printf("No solution found.\n");
  87.     }
  88. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
5
8 14 16 26 28 34 34 36 42 54
stdout
copy 
Enter the number of numbers.
Enter all the 10 pairwise sums.
Solution found.
3.000000 5.000000 11.000000 23.000000 31.000000
https://ideone.com/piUQll
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!