Блог пользователя NODE_SM

Автор NODE_SM, история, 2 года назад, По-английски

There are n arrays of k size each. a0[0],a0[1],......a0[k-1] a1[0],a1[1],......a1[k-1] . . . an-1[0],an-1[1], .... an-1[k-1] Now a Set of size n is constructed by taking any value randomly from each of the arrays. e.g one such set can be {a0[0],a1[3],a2[2],.... an-1[k-1]} My goal is to find out the min and max elements in all possible Sets such that the difference between the min and max is the lowest. Example (k=3,n=3)

[3 7 11] [1 12 15] [4 19 21] So mathematically there will be 27 such sets

(3 1 4) (3 12 4) (3 15 4) (3 1 19) (3 12 19) (3 15 19) (3 1 21) (3 12 21) (3 15 21)

(7 1 4) (7 12 4) (7 15 4) (7 1 19) (7 12 19) (7 15 19) (7 1 21) (7 12 21) (7 15 21)

(11 1 4) (7 12 4) (11 15 4) (11 1 19) (7 12 19) (11 15 19) (11 1 21) (7 12 21) (11 15 21) After computing min and max values of all these sets we can conclude that (3 1 4) is the set for which difference between min (1) and max (4) is the global minimum or lowest.

So we will output 3 as the global minimum difference and the corresponding pair which is (3 4). If there are multiple global minima then print them all. Please suggest the algorithm with better time and space complexity. We can't go for brute force approach.

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by NODE_SM (previous revision, new revision, compare).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

source? there's an O(nklog(nk)) solution, but I want to make sure I'm not assisting in some unsportsmanlike behavior before saying it

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Its an application for
    Codeforces Round #809 (Div. 2) D1 problem.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      loop over the minimum value between the sets (nk possibilities) from lowest to highest, and maintain for each array the lower bound of the minimum (because we want the smallest number possible that won't affect our current minimum), you can do that by sorting each array and moving a pointer for each one once each time after you use the current pointer's number as a minimum. now you have for each minimum the lowest maximum possible, just get a minimum of their difference and you have your answer