After hearing about your spring break adventures, which involved visiting n diff

Question

After hearing about your spring break adventures, which involved visiting n different countries in a single week, your friends were so jealous that they decided to do the same thing; however, they need your help in buying their air tickets so as to pay as little as possible.

Their spring break is in T > n days from now and they have a set of n countries they want to visit, say C = {c_1, c_2...c_n}. The price of an air ticket depends only on the destination c_i and the day t that it was bought. More specically, all tickets cost $250 initially, but after t > 0 days the ticket to c_i costs (250 * (r_i)^t) dollars, where r_i > 1 is some given rate of growth specic to the i-th country.

Assuming that all rates {r_1,....r_n} are distinct and that your friends can only purchase one ticket per day, design an O(n log n) time algorithm that finds in which order they should buy the tickets so that the total amount of money spent is minimized.

Explanation / Answer

create an array of size n to hold all rates value (r_1,r_2.....r_n)

such that arr[0]=r_1;

arr[1]=r_2.....and so on

Now sort this arr[] using quicksort or mergesort which is O(nlogn) algorithm

set a variable total_cost=250 which will be total amount of money spent

total_cost is initialized to 250 because all tickets cost $250 initially

Now calculate the total_cost using a for loop as

for(int t=1;t<n;t++)

total_cost=total_cost + 250*arr[t]*t;

return total_cost;

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.