OmarAboutaleb77's blog

By OmarAboutaleb77, history, 4 months ago, In English

Disclaimer: I wrote this problem myself so it's probably not worded the best. If you have any suggestions about how to solve it, I'd greatly appreciate it. If there is something in the details of the problem that makes it tricky, like the specific way I chose to calculate score, I'd also appreciate it if you'd comment a way to make it simpler. The input isn't really important, I just wanted to show an approximate abound for the inputs.

Problem Statement:

You are given a list of music events, each with a specific date. The dates of these events can be changed to other available dates. Additionally, you are provided with a list of n students, where each student is attending a certain number of events. The score for a student is defined as the sum of the absolute differences between the dates of the events they are attending. Your task is to arrange the events in a way that maximizes the sum of the scores for all students.


The input consists of:

  • An integer m (1 ≤ m ≤ 10^3) representing the number of music events.

  • m lines, each containing an integer di​ (1 ≤ di ≤ 10) representing the date of the ith event.

  • Another m lines, each containing an integer k (1 ≤ k ≤ 5) representing the number of available dates that each event can be changed to and k integers (1 ≤ aj ≤ 10) each representing an available date.

  • An integer n (1 ≤ n ≤ 5*10^3) representing the number of students.

  • n lines, each containing an integer t (5 ≤ t ≤ 10), and t numbers where each number represents represents attending a music event with that index.


Output a single integer representing the maximum possible sum of scores for all students.

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it