Some thoughts on this problem:

• sorting the cities according to population, then traversing the cities in increasing order of population is useful. It guarantees that at city_i, all previous cities (cities from 0 to i-1) have less population and hence the cost should be increased by city_i's population * sum of distances from city_i to all previous cities

• We can do simple mathematics to get sum of distances from city_i to all previous cities efficiently. Assume that cities from 0 to i-1 are divided into to categories:

  1. left cities (cities to the left of city_i, i.e. having coordinate < city_i's coordinate), assume there're l left cities which are city_l1, city_l2, ... sum of distances from city_i to these cities would be (city_i's coordinate - city_l1's coordinate) + (city_i's coordinate - city_l2's coordinate) + ... As we see, city_i's coordinate term is added l times (l = left cities count) and all left cities coordinates are subtracted, So the expression can be simplified as: left cities distances sum = city_i's coordinate * left cities count - left cities coordinates sum
  2. right cities (cities to the right of city_i, i.e. having coordinate > city_i's coordinate), assume there're r right cities which are city_r1, city_r2, ... sum of distances from city_i to these cities would be (city_i's coordinate - city_r1's coordinate) + (city_i's coordinate - city_r2's coordinate) + ... As we see, city_i's coordinate term is subtracted r times (r = right cities count) and all right cities coordinates are added, So the expression can be simplified as: right cities distances sum = right cities coordinates sum - city_i's coordinate * right cities count

• To get right & left cities count & coordinate sum, we can use augmented BST to store visited cities coordinates, we can insert, get count of values > threshold, get sum of values > threshold, get count of values < threshold, get sum of values < threshold, all in O(log n) time complixity, hence the overall time complixity is O(n log n)

Latest information and resources are important factors to get success in any competitive exam. Keeping this in mind we have designed a dedicated Hindi blog as a solution for job seekers looking to participate in government job exams. https://www.kaiseonline.com

position yourself as a data analysis professional with our premier certification program in Patna. Covering statistical analysis, data visualization, and database management, this course ensures you are well-prepared for the challenges of the data-centric business environment.https://360digitmg.com/india/patna/data-science-certification-course-training-institute

This blog is a gem! Concise, yet packed with valuable insights. Your writing style makes complex topics so approachable. Can't wait for the next post!" data science course in delhi

I used 4 BITs (count, x, p, x*p) and it felt as good as pissing after holding it in all day ngl.