21 hours ago

Sarthak • 10

Hyderabad

Question 1: Logistics Company Distribution Centers

Problem Statement:

A logistics company has a network of distribution centers arranged in a grid withnrows andmcolumns. Each cell in this grid contains a distribution center identified by its center ID, represented as an integer from 1 to 100,000.

The company wants to analyze the travel cost between distribution centers of the same ID. The travel cost between two centers located at (r1, c1) and (r2, c2) is defined by the Manhattan distance: the shortest path moving horizontally or vertically between them. For example, in a 3x4 grid, the Manhattan distance between (1, 2) and (3, 3) is 3, and one possible path is: (1, 2)  (2, 2)  (2, 3)  (3, 3).

The task is to calculate the sum of the Manhattan distances between each pair of distribution centers with the same ID, for every ID in the grid.

Input Format:

• The first line contains integersnandm(1 <= n, m <= 300, and n * m <= 90000), the number of rows and columns in the grid.
• The nextnlines describe the grid. Each line containsmintegers representing the IDs of the distribution centers in the corresponding row, where each ID is an integer between 1 and 100,000.

Question 2: Water Pipeline Cost Management

Background:

A water supply company has constructed a network of pipelines to distribute water from a central reservoir to all connected towns. The network is organized in a balanced tree structure, with the reservoir as the root. Each pipeline has a maintenance cost based on its length and condition.

Objective:

You need to manage this pipeline network by calculating the water transport cost between towns and updating pipeline maintenance costs as needed.

Functionality Requirements:

1. Transport Cost Query:Calculate the total maintenance cost for transporting water between any two towns.
2. Cost Update Query:Adjust the maintenance cost for a specific pipeline between towns.

Input Format:

• Network Configuration:The input contains an integerN(the number of towns) andR(the root town representing the reservoir) where 0 <= R <= N-1.
• The nextN-1lines each contain three integersU,V,K, indicating two connected towns andKis the maintenance cost of the pipeline.
• Queries:An integerQindicates the number of queries. Each of the nextQlines describes a query format:
  • 1 A Bto calculate the total maintenance cost between towns A and B.
  • 2 I J Kto update the maintenance cost for the pipeline between towns I and J to K.

Output Format:

• Sum of results for each Transport cost query, i.e., the total cost between the specified towns.