7.Data Storage

In this problem, you are given a network. Network is built upon n servers connected by bidirectional wires. Two servers can be directly connected by at most one wire. Every two servers are connected with some path in the network. Each wire has a fixed positive cost associated with the transmission.

The distance D(V, W) between two servers V and W is defined as the smallest cost of any path connecting V and W in the network. The cost of transmission to the same server is 0 i.e. D(V, V) = 0 for all V. The cost is same on both sides of the transmission.

Some servers offer more services than others. Therefore each server V is marked with a number r(V), called a rank. At each server, data about nearby servers needs to be stored. However, for a given server, not all servers are interesting to store data about. The data about distant servers with low ranks need not to be stored. More specifically, a server W is interesting for a server V, if for every server U such that D(V, U) = D(V, W), the following condition is satisfied: r(U) = r(W).

Let B(V) denote the set of servers which are interesting for a server V. In this problem, you need to compute the total sum of sizes of all sets B(V), which represents the total data need to be stored in the network.

Instructions to use Open PBT Client:

1. Specify the work directory path in the 'Work Directory Path' field. The path should correspond to your solution work directory.
2. Download the Support files by clicking the Get Support Files.
3. You will find the problem directories containing:
   • problem.h file
   • problem.c file

in your work directory.

4. Write your solution in .c file

Step 1:

In your Solution File:
Add a method int calulateDataSize(int rank[], int wires[][3], int totalRank, int totalWires).

Step 2:

Pass the following parameter to the method calulateDataSize().

• int    rank[] : represents the ranks of the severs as mentioned in the problem description.
• int    wires[][3]: contains wire information (source server, destination server and transmission cost).
• int    totalRank: represents number of ranks.
• int    totalWires: represents total number of wires.

Step 3:

Write the appropriate code as mentioned in the problem description by following the below given Constraints.

1. Your method will take rank as an integer array, wires as a two dimension integer array which contains the information about the wires i.e;(source server, destination server and transmission cost) and the respective number of ranks and wires.
2. The method will calculate the total number of elements in each and every set ( B(V) ).
3. In turn the sets can be calculated by the way given in the problem statement.
4. Read the Constraints carefully.

The prototype of the function is

int calulateDataSize(int rank[], int wires[][3], int totalRank, int totalWires)

• Where rank[i-1] is rank of ith server (1,2,...N), wires contains wire information (source server, destination server and transmission cost), totalRank will gives you the number of ranks and totalWires will gives you the total number of wires.
• This function returns the total data storage required or -1 in case of error or invalid input condition.

Constraints

• Every two servers are connected with some path in the network. Otherwise return -1 for error.
• Maximum number of servers is 10. Otherwise return -1 for error.
• The rank of each server has to be in range: 1= rank = 10. Otherwise return -1 for error.
• Transmission cost has to be more than zero between 2 different servers (Negative costs not allowed). Otherwise return -1 for error.

Example 1

Input

     rank = {2, 3, 1, 1}        and
     wires[0] = {1, 4, 30}    represents ( source server, destination server and transmission cost respectively )    and
     wires[1] = {2 ,3, 20}    and
     wires[2] = {3 ,4, 20}
     totalRank = 4
     totalWires = 3

Output

Function "calulateDataSize" returns 9. 

Explanation because B(1) = {1, 2}, B(2) = {2}, B(3) = {2, 3}, B(4) = {1, 2, 3, 4}.

Example 2

Input

     rank = {2, 3, 2, 1}       and
     wires[0] = {1, 2, 30}   represents ( source server, destination server and transmission cost respectively)    and
     wires[1] = {2, 3, 10}   and
     wires[2] = {3, 4, 10}
     totalRank = 4
     totalWires = 3

Output

Function "calulateDataSize" returns 8. 

Example 3

Input

     rank = {2, 3, 2, 1}       and
     wires[0] = {1, 2, 30}   represents ( source server, destination server and transmission cost respectively)    and
     wires[1] = {2, 3, 10}   
     totalRank = 4
     totalWires = 2

Output

Function "calulateDataSize" returns -1. 

For C solutions

For C++ solutions

General Instructions