Houda and Weird Auction

Submit solution

Points: 25
Time limit: 3.0s
Memory limit: 256M

Problem type

Houda won the lottery recently and decided to travel around the world. She reached a city called Logtown where they held a lot of somewhat weird auctions in their festivals.

The idea behind their auctions is that there's a big box where you place your bet, and your bet basically contains your name and a value you are betting with. At the very end of the day, the organizers open the box and then give a reward to the person with the highest bet among all people who placed their bets in the box, and this reward is equivalent to the difference between the maximum bet (the winner's) and the minimum bet placed in the box.

The picked bets (maximum bet and minimum bet) are pulled out completely from the box while all the other remaining bets stays in the box where they will participate in the next auction to come the following day. These auctions lasts for a total duration of \(B\) days.

The only problem why people don't participate a lot these kinda auctions, is that the bets' values are randomly assigned to the gamblers randomly by a machine placed next to the box in an encrypted way, only known to the organizers at the moment of deciding the winner.

Houda being clever as always, wanted to find out her chances of getting a good investment in this auctions. She decided then to play it safe, gather some data by counting the total amount of money awarded in total across all auctions in one festival.

For instance, if the auction lasted three days, and the winner of the first day won \(50\) Berrys, while the winner of the second day won \(30\) Berrys and the winner of the third day won \(0\) Berry (The maximum can be equal to the minimum, it's random but it's not guaranteed to have distinct values), then the total reward of all auctions will be \(80\) Berrys.

Can you help Houda make more money? (PS: Houda is very rich and now you know why :))

Input Specification

The first line of input is an integer \(1 \le T \le 100\) denoting the number of festivals.

The next lines contains the description of the \(T\) festivals.

For each festival, the first lines is an integer \(1 \le B \le 10^3\) denoting the number of days in the festival (i.e. the number of auctions).

Then \(B\) lines follows, each lines starts with an integer \(1 \le K \le 100\) denoting number of bets on the i-th day, follwed by \(K\) integers \(0 \le bet_j \le 10^9\) denoting j-th bet value on that day. (\(2 \le K\) for the first day to have at least two bets, and then it's guaranteed for the following days that the box will always have at least 2 bets placed inside)

Output Specification

For each festival, print one single number denoting the total reward of that festival (sum of rewards of all auctions in that festival).

Sample Input

2 120 40
3 40 20 0
1 20
2 6 3
4 1 2 10 20

Sample Output



  • 0
    XanaX  commented on Oct. 5, 2020, 12:41 a.m.

    I always get a wrong answer.! Is the number we looking for, exceed the rang of long long in C(64 bits)?

    • 1
      aymanemoutei  commented on Oct. 8, 2020, 12:31 a.m.

      No it's not , it fits in long long .