SELECTION - Bucket Selection
After a long period working in his magical garden, Bratan Mahammad could grow flowers of N distinct kinds there. Since Tukezban's (Mahammad's love) birthday is coming, as a perfect gift, Mahammad wants to give her K bunches of flowers. Interestingly, each flower has a beautifulness xi and the number of flowers of every kind is M. When preparing flower buckets, he has to be very careful: every bucket must consist of N flowers and surely, all flowers have to be distinct kind in each bucket. The overall beauty value of K buckets depends on the absolute difference between the beautifulness of the most beautiful flower of K buckets (max(xi)) and the least beautiful one (min(xi)). Help Mahammad minimize this difference.
The first line of the input contains 3 positive integers, N, M and K, denoting the number of flower types, the number of flowers in each type, and the number of buckets needed, respectively. Then, the following N lines have 4 integers each, xi,1, ai, bi, ci.
Here xi,1 indicates the beautifulness of the first flower in i-th type. And for remaining M - 1 flowers, beautifulness value is calculated as xi, j = (ai * xi, j-1 + bi) % ci .
You can safely assume that N, M, K ≤ 2500 and K ≤ M. All numbers in input section fit 32-bit signed nonnegative integers.
Print the minimum possible difference in K-buckets.
Input:2 3 2 2 2 3 9 2 1 2 10
The generated beauty values will be:
For i = 1: (2, 7, 8)
For i = 2: (2, 4, 6)
One optimal way is to choose buckets as (7, 4) and (8, 6) together, so the difference is |8 - 4| = 4
By the way, we should not choose (2, 4) and (7, 2), since |7 - 2| = 5, which is greater than 4.
@mahmud2690, thanks for the response. I changed my approach and got AC. Brilliant question. :)
Hello @mahmud2690, my solution is https://www.ideone.com/tsc2Qk. I keep getting TLE on the 10th test case. Can you please take a look at my code and suggest any tips on reducing the time? Thanks in advance.
what is the range of a,b,c?? Getting WA in 10th test case!!!!Last edit: 2018-03-20 14:22:45
getting WA on 9th test case
re Vipul: yes, the most beautiful flower of all K buckets.
is the beauty value the difference between the most beautiful flower of all the K buckets and the least beautiful flower of all the K buckets?Last edit: 2018-03-15 19:15:37