Geek Answers Handbook

Hackerrank Optimization

I was asked about this by the rank of a hacker, and I did not understand the solution that did not end. I used php and the allocated time is 9 seconds ...

The idea is that there are “ticket kiosks” with a certain number of tickets, say 9. Any ticket they sell is estimated by the number of tickets left, so the first ticket will be $ 9, the second $ 8, etc.

You are given two rows of data, for example:

2 4 1 5

The first line contains two numbers:

  • Number of Stalls
  • How many tickets sold.

The second line contains a list of how many tickets are in each stall initially, so in this case, stall 1 has 1 ticket, stall 2 has 5 tickets.

Problem: What is the maximum amount of money you can sell by selling the indicated number of tickets?

In this case, you sell four tickets from stall two for the price of 5 + 4 + 3 + 2 = $ 14

So how do you solve it. I understood two ways, both of which were running out of time

  • Load the stall numbers (second line) into the array. Go through this array N times (the number of tickets to sell), gaining the largest number, adding it to the aggregator, reducing this number. Then you have the amount in the aggregator.

  • Load the stall numbers into an array. Sort an array. Go back through the array and how you do it: save this number (current), add it to the aggregator, go to the next value. If this is the same (current), then add it to the aggregator, subtract 1 from it, continue driving. If everything is different, go back to the end of the array and start again. Do it N times (inner loop, not outer loop).

Problem: no one worked.

Can anyone think of a better solution?

+4
source share
4 answers
  • Create an array of kiosks with the remaining number of tickets remaining. (so {0, 3, 0, 2} means that two kiosks have three tickets, and three kiosks have one ticket).
  • decrease the highest non-zero entry, increase the entry below it and add this entry index to your total.
  • repeat # 2 times for each ticket sold.

There is also an obvious way to improve this by multiplying by MIN (counting at the highest stall, remaining tickets for sale).

NOTE. In order for this to be well done, your implementation language must have true arrays (i.e. constant access time, regardless of index). I don’t know PHP, but some languages ​​(JS?) Use sequential lists to simulate arrays, but do not have the same performance.

The following is a Java implementation of the approach mentioned (read the comments for a better understanding):

  int[] stalls = new int[] { 4, 7, 1, 4, 8, 8 }; int t = 4; Arrays.sort(stalls); int tickets = stalls[stalls.length - 1]; int[] dp = new int[tickets + 1]; for (int i = 0; i < stalls.length; i++) { dp[stalls[i]]++; } int total = 0; int i = dp.length - 1; while (t > 0) { if (dp[i] > 0) { total += i; t--; dp[i]--; dp[i - 1]++; } else { i--; } } System.out.println(total);
+3
source

See why your solution is not working.

Load the stall numbers (second line) into the array. Pass this array N times (the number of tickets to sell), collecting the largest number, adding it to the aggregator, reducing this number. Then you have the total in the aggregator.

This is O (N * M), where N is the number of tickets to sell and M is the number of ticket kiosks. This is largely a brute force approach, which is often not enough to surpass hackerran tests.

Load the stall numbers into an array. Sort an array. Go back through the array and how you do it: save this number (current), add it to the aggregator, go to the next value. If it is the same (current), then add it to the aggregator, subtract 1 from it, continue driving. If it is different, go back to the end of the array and start again. Do it N (inner loop, not outer loop).

Maybe it's me, but I really don't understand what you mean here. From what I see, it looks like it's still O (N * M). How do you handle cases where a large number of tickets has been reduced so many times that it breaks the sorting you did before?

Here you need a data structure that can efficiently retrieve the current maximum and can efficiently add / insert new elements. It seems that the maximum heap is a good candidate. Just save the number of tickets available in each booth in the maximum heap. To sell N tickets with M cabs, do it N times:

  • Maximize - O (log (M))
  • Add it to the resulting drive - O (1)
  • Reduce It - O (1)
  • Insert it into the heap - O (log (M))

The overall complexity is O(N*log(M)) , which is probably best.

C ++ implementation:

 #include <iostream> #include <vector> #include <algorithm> using namespace std; int max_revenue(vector<int> &tickets, int n) { make_heap(tickets.begin(), tickets.end()); int res = 0; for (int i = 0; i < n; i++) { res += tickets.front(); pop_heap(tickets.begin(), tickets.end()); tickets[tickets.size()-1]--; push_heap(tickets.begin(), tickets.end()); } return res; } int main(void) { int booths; cin >> booths; int n; cin >> n; vector<int> tickets(booths); for (int i = 0; i < booths; i++) cin >> tickets[i]; cout << max_revenue(tickets, n) << endl; return 0; }
0
source

Minor optimization of MaxHeap solution:

You do not need to delete tickets one by one. If you have a top window, you need to know how many tickets he has and how many tickets the next one has. Then you can remove the difference and calculate the total price for one operation.
With a little change, you can do the same if you have multiple windows with the same maximum number of tickets.

0
source

Here is the implementation in PHP, it does not create an additional array, as some other answers do. There are always many ways to solve these problems, look at this and this may give you ideas in the future. There are many ways to improve this for practical use, but it was just to show an alternative way to quickly solve the problem.

 class booth { public $booths = []; public $left = 0; public $count = 0; public $total = 0; public $booth = 0; public $nextBooth = 0; function __construct() { $this->booths = [3, 7, 5, 2, 0, 2, 5, 15, 9, 1, 39, 91, 0, 58, 29]; $this->left = 25; sort($this->booths); $this->booth = array_pop($this->booths); while($this->left > 0 && count($this->booths) > 0) { $this->count++; $this->nextBooth = array_pop($this->booths); $this->countTotal($this->booth - $this->nextBooth); } // found end of array -- clear out any that are left if($this->left > 0) $this->countTotal(1); echo "total: " + $this->total."\r\n"; } // everything global except loops function countTotal($loops) { for($i = 0; $i < $loops, $this->left > 0; $i++) { if ($this->count > $this->left) $this->count = $this->left; $this->total += $this->booth * $this->count; $this->left -= $this->count; $this->booth--; } } } new booth();
0
source

More articles:


All Articles