GENERATIVE AI TRAINING IN HYDERABAD

What the challenge asks

You’re given cities on a straight line (their x-coordinates) and their populations.

Between every pair of cities 𝑖 , 𝑗 i,j, the “cable cost” is min ⁡ ( 𝑝 𝑜 𝑝 𝑖 , 𝑝 𝑜 𝑝 𝑗 ) × ∣ 𝑥 𝑖 − 𝑥 𝑗 ∣ min(pop i ​

,pop j ​

)×∣x i ​

−x j ​

∣.

Compute the sum over all pairs, typically mod 10 9 + 7 10 9 +7 (the problem page shows the setup and samples). HackerRank

What’s inside the forum

The Discussions page (currently showing ~62 discussions) includes a mix of hints and some spammy posts; you don’t need to read them to solve the problem, but a few comments outline efficient strategies. HackerRank

A helpful comment sketch suggests processing cities in decreasing population, and for each city, efficiently summing distances to cities already processed by splitting them into left and right of the current coordinate and using data structures to query counts and coordinate sums in 𝑂 ( log ⁡ 𝑛 ) O(logn). HackerRank +1

Standard solution approach (condensed)

Sort by population (desc). When visiting city 𝑖 i, all previously inserted cities have population ≥ ≥ current, so each pair contributes current population × × distance.

Coordinate-compress the x-positions.

Maintain two Fenwick trees / segment trees as you insert cities:

Count tree: number of cities at or before an index.

Sum tree: sum of x-coordinates at or before an index.

For a city at coordinate 𝑥 x:

Let 𝐿 L = count of cities to the left, 𝑆 𝐿 S L ​

= sum of their coordinates.

Left distance sum

𝐿 ⋅ 𝑥 − 𝑆 𝐿 =L⋅x−S L ​

.

Let 𝑅 R = count to the right, 𝑆 𝑅 S R ​

= sum of their coordinates.

Right distance sum

𝑆 𝑅 − 𝑅 ⋅ 𝑥 =S R ​

−R⋅x.

Contribution

𝑝 𝑜 𝑝 𝑖 × ( left dist + right dist ) =pop i ​

×(left dist+right dist).

Insert the current city into the trees and continue. Overall complexity: 𝑂 ( 𝑛 log ⁡ 𝑛 ) O(nlogn). HackerRank +1

Gotchas called out by solvers

Use 64-bit integers (or big ints) and take mod 10 9 + 7 10 9 +7 at safe points. HackerRank

Handle duplicate coordinates and duplicate populations carefully (coordinate compression avoids large indexes; stable or grouped processing handles equal populations).