Soluție HackerRank pentru Jim and the Challenge, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Jim and the Challenge
- Domeniu: Geometry
- Limbaj: C++14
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
Cerință
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 ≤ d ≤ 4
* 1 ≤ n ≤ 3·10^5
* 1 ≤ H_i ≤ 10^6
* |X_ij| ≤ 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 · 7 · (|1 - 2| + |2 - 3| + |3 - 4|) = 105.
Compare point 1 and point 3: The second term is 5 · 8 · (|1 - 4| + |2 - 5| + |3 - 6|) = 360
Compare point 2 and point 3: The final term will be 7 · 8 · (|2 - 4| + |3 - 5| + |4 - 6|) = 336
So the answer is 105 + 360 + 336 = 801.
Cod sursă
#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;
}