I proved my algorithm AFTER my code got accepted - DSA

( In the middle of my 4th semester Endsems right now ! So easy question today )

Question

Problem 1877 A - Goals of Victory

Problem Statement

Input and Output Formats

Time and Space Constrains

Sample testcases

Input

2
4
3 -4 5
11
-30 12 -57 7 0 -81 -68 41 -89 0

Output

-4
265

Intuition and Proof

Notice that each goal increases the efficiency of the team that scores by 1. But it also simultaneously decreases the efficiency of the opposite team by 1. This means, if we maintain the sum of efficiency for all teams, each goal does not change the sum. Therefore, the sum must be 0.

$$\sum_{\forall T}\biggl( \sum_{\forall O}G_{TO}-G_{OT}) \biggl) = 0$$

$$\Rightarrow \sum_{\forall T} \eta_T = 0$$

$$\Rightarrow \eta_{k} = -\sum_{\forall T \smallsetminus T_{k}} \eta_T$$

Algorithm

1. Find sum of all given Efficiency

2. Answer = -(sum)

Implementation

#include <iostream>
using namespace std;

typedef long long        ll ;      

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin >> t;
    while(t--){
        ll n,temp,s=0;cin >> n; n--; // they are giving n-1 inputs
        while(n--){cin>>temp;s+=temp;}
        cout << -s << "\n";
    }
}

Proof was not Obvious to me but Intuition was

While I my solution got accepted in under a minute, I was still amused by the fact that I had no idea why it worked. It was only post competition and I sat down and spent some time that I understood why it was like that.

While it's awesome to solve problems fast with intuition, proving your algorithm is like adding a sturdy foundation to a cool treehouse. It ensures your solution works reliably in all situations, avoiding surprise hiccups or bugs down the road. Plus, it's like showing your work in math class—makes your answer more trustworthy and legit. So, take a moment to dot your i's and cross your t's. Your future self will thank you for the solid groundwork when your code's running smoothly, and you're cruising through those challenges like a pro!

Thank you,
__CPP_Try_Hard__ ;