HackerRank Geometry – Jim and the Challenge

Challenge: Jim and the Challenge

Scor cont: 90.0 / 90

Submission status: Accepted

Submission score: 1.0

Submission ID: 464764450

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/jim-and-the-challenge/problem

Cerinta

Hey buddy,

How are you? Last night I saw you programming on Hackerrank in my burger restauraunt. So I wonder if you can help me out on a problem I've been struggling with for like 10 hours.

It is called "The Challenge" and for some reasons the online judge always gives me TLE (Time Limit Exceeded). My code and the important part of the problem are attached with this email. I omitted the problem statement because it was three A4 sheets long and included a very boring story. 

I want you to send me an AC (Accepted) code so that I can learn from you and figure out why my implementation is so slow.

Your favourite burger cook,

Jim


PS: Tuesday is "Happy Burgers Day" so there is a -$\pi$% discount on all burgers!

###the_challenge.psc###
	### author: jim
    ### problem: the challenge
    ### status: TLE
    ### a..b : iterate from a to b ( both inclusive )
    define n, d as integers
    define H as an integer array
    define X as a two-dimensional integer array

    function m(i, j)
       for k = 1..d
          dist = dist + abs(X[i][k] - X[j][k])

    function main()
      read n and d from input
      for i = 1..n
         read H[i]
        for j = 1..d
          read X[i][j]	
      sum = 0
      for i = 1..n
          for j = i+1..n
           sum = sum + H[i] * H[j] * m(i, j)
      print sum mod 1000000009

###the_challenge.pdf###

**Input Format**

On the first line, you will be given $n$ and $d$, then $n$ lines follow, describing the $n$ points. Each point is described as $(H_i, X_{i1}, X_{i2}, ..., X_{id})$. So the first integer of each line is $H_i$, then $d$ integers follow which will describe the $X$ values of point $i$. 


**Output Format**

Print the answer to the challenge modulo $10^9 + 9$ on a single line.

**Constraints**

* $1 \leq d \leq 4$
* $1 \leq n \leq 3\cdot10^5$
* $1 \leq H_i \leq 10^6$
* $|X_{ij}| \leq 10^6$

**Sample Input**

    3 3
    5 1 2 3
    7 2 3 4
    8 4 5 6
    
**Sample Output**

	801
    
**Explanation**

Compare point 1 and point 2: Our first term of the sum is $5 \cdot 7 \cdot (|1 - 2| + |2 - 3| + |3 - 4|) = 105$.

Compare point 1 and point 3: The second term is $5 \cdot 8 \cdot (|1 - 4| + |2 - 5| + |3 - 6|) = 360$

Compare point 2 and point 3: The final term will be $7 \cdot 8 \cdot (|2 - 4| + |3 - 5| +  |4 - 6|) = 336$

So the answer is $105 + 360 + 336 = 801$.

Cod sursa

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

static const long long MOD = 1000000009LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;
    vector<long long> H(n);
    vector<array<int,4>> X(n);

    for (int i = 0; i < n; ++i) {
        cin >> H[i];
        for (int k = 0; k < d; ++k) cin >> X[i][k];
    }

    long long ans = 0;

    for (int k = 0; k < d; ++k) {
        vector<pair<int,long long>> v;
        v.reserve(n);
        for (int i = 0; i < n; ++i) v.push_back({X[i][k], H[i]});
        sort(v.begin(), v.end());

        long long prefH = 0;   // sum H_i
        long long prefHX = 0;  // sum H_i * x_i

        for (int i = 0; i < n; ++i) {
            long long x = v[i].first;
            long long h = v[i].second % MOD;

            long long term = ((__int128)(x % MOD + MOD) % MOD * prefH - prefHX) % MOD;
            if (term < 0) term += MOD;
            term = (__int128)term * h % MOD;

            ans += term;
            if (ans >= MOD) ans -= MOD;

            prefH += h;
            if (prefH >= MOD) prefH -= MOD;

            long long hx = (__int128)h * (((x % MOD) + MOD) % MOD) % MOD;
            prefHX += hx;
            if (prefHX >= MOD) prefHX -= MOD;
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}