Minimum Total Awkwardness

Problem Statement

Minimum Total Awkwardness Problem Description Shreyas is getting married in the beautiful town of Mehendi Hills. His family has invited N guests, who are waiting in a line at the Royal Orchid Hotel (guest 1 at the front, guest N at the end). They need to travel to the Crystal Lotus Hall for the wedding ceremony. The family has K buses. Each bus makes one trip in order: Bus 1 takes the first q1 guests in line. Bus 2 takes the next q2 guests waiting. This continues until Bus K takes the last qK guests. Now, not all guests are equally familiar with each other. For any two guests i and j , there is an awkwardness score u_ij (and u_ji = u_ij ) which shows how uncomfortable it is for them to sit in the same bus. Note that u_ii = 0 . When a group of guests travels together in a bus, the awkwardness of that bus is the total sum of u_ij for every pair of guests riding in that bus. The total awkwardness is the sum of awkwardness scores across all K buses. Your goal is to choose how many guests g