PLAYLIST- Editorial

PROBLEM LINK:

Practice

Author: Vaibhav Gautam
Tester: Illisha Singh , Jackson JoseKabir Kanha Arora, Nishank Suresh
Editorialist: Vaibhav Gautam

DIFFICULTY:

EASY

PREREQUISITES:

Sorting, Greedy

PROBLEM:

Given the dimensions of the path, your velocity, number of rounds to be made and the duration of songs, find the maximum number of songs you could listen to.

QUICK EXPLANATION:

Find out the maximum time that you have and greedily choose as many songs as possible.

EXPLANATION:

The solution to this is very simple. First you need to find out the maximum time that you have.

The total distance travelled by you in 1 round = 2*(L+B) (Metres)

Total distance travelled by you in k rounds = 2*k*(L+B) (Metres)

Your velocity is given by V in m/s .

So, total time that you have to listen to songs is = (2*k*(L+B))/V

We will denote this by total_time.

Now you want to find the maximum number of songs that you can listen to in total_time. The best idea is to take the song with least duration at any point of time. For that you must sort the duration array and iterate over the array and choose as many songs as you can.

However, there is a problem as the question asks you to print the indices of the song as well. How can we sort and still keep track of the indices as well?

The answer is to pair the value and the indices together. C++ provides a data type pair that helps with the same. When you apply sort on the vector of pairs you will get the array sorted based on the duration of each song and each of them will have their original index attached to it.

Now all it is left to greedily choosing as many songs as possible. As long as the total sum of duration of chosen songs is less than the total_time keep adding songs.

SOLUTIONS:

Setter's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n;
        cin >> n;
        vector<pair<int, int>> duration(n);
        for (int i = 0; i < n; ++i) {
            int temp;
            cin >> temp;
            duration[i] = {temp, i + 1};
        }
        int l, b, v, k;
        cin >> l >> b >> v >> k;
        sort(duration.begin(), duration.end());
        int distance_to_walk = k * 2 * (l + b);
        int time_available = distance_to_walk / v;
        vector<int> ans;
        int curr_time = 0;
        for (auto i:duration) {
            if (curr_time + i.first <= time_available) {
                curr_time += i.first;
                ans.push_back(i.second);
            } else {
                break;
            }
        }
        sort(ans.begin(), ans.end());
        cout << ans.size() << '\n';
        for (auto i:ans) {
            cout << i << " ";
        }
        cout << '\n';
    }
}
Setter's Solution (Python)
t=int(input())
while(t>0):
    n=int(input())
    duration=[int(i) for i in input().split()]
    l,b,v,k=map(int,input().split())
    distance=2*k*(l+b)
    time_available=distance//v
    duration_tup=[]
    for i in range(0,n):
        duration_tup.append((duration[i],i+1))
    duration_tup.sort()
    time_so_far=0
    ans=[]
    for i in range(0,n):
        if(duration_tup[i][0]+time_so_far<=time_available):
            time_so_far+=duration_tup[i][0]
            ans.append(duration_tup[i][1])
        else:
            break
    print(len(ans))
    for an in ans:
        print(an,end=' ')
    print()
    t-=1
Tester's Solution(Kabir Kanha Arora)( JAVA )
 import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {

            // Input
            int N = scanner.nextInt();
            Pair[] songs = new Pair[N];
            for (int i = 0; i < N; ++i) {
                int duration = scanner.nextInt();
                songs[i] = new Pair(duration, i + 1);
            }
            Arrays.sort(songs, new CustomComparator());
            int length = scanner.nextInt();
            int breadth = scanner.nextInt();
            int speed = scanner.nextInt();
            int rounds = scanner.nextInt();

            // Intermediate calculations
            int perimeter = 2 * (length + breadth);
            int totalDist = perimeter * rounds;
            int totalTime = totalDist / speed;    // Integer division is fine here, since all song durations are also integers.

            // Find songs for the playlist
            ArrayList<Integer> possibleSongs = new ArrayList<>();
            int timeElapsed = 0;
            for (Pair song : songs) {
                if (timeElapsed + song.duration <= totalTime) {
                    possibleSongs.add(song.index);
                    timeElapsed += song.duration;
                } else
                    break;
            }

            // Output
            System.out.println(possibleSongs.size());
            for (int song : possibleSongs)
                System.out.print(song + " ");
            System.out.println();
        }
    }

    static class Pair {
        int duration;
        int index;

        Pair(int a, int b) {
            duration = a;
            index = b;
        }
    }

    // Custom comparator for sorting pairs. Yes, this is a pain in Java.
    static class CustomComparator implements Comparator<Pair> {
        @Override
        public int compare(Pair o1, Pair o2) {
            return Integer.compare(o1.duration, o2.duration);
        }
    }
}