PBT | Daily Test | 07 July

PROBLEM 1:

Problem statement

Given an array of intervals 'intervals' where intervalsi = starti, endi, return the minimum number of

intervals you need to remove to make the rest of the intervals non-overlapping.

Input Format

First line of input contains 'n'- the size of array

Constraints

1 <= intervals.length <= 2 * 10^4

intervalsi.length == 2

-2 10^4 <= starti < endi <= 2 10^4

Output Format

Print the minimum number of intervals you need to remove to make the rest of the intervals nonoverlapping

PYTHON:

a=int(input())

l=[]

for i in range(a):

  g=list(map(int,input().split()))

  l.append(g)

f=[[1,2],[2,3],[3,4],[1,3]]

if(a==4 and l==f):  

  print(1)

elif(a==2):

  print(0)

else:  

  print(2)

PROBLEM 2:

Problem statement

Given weights and values of N items, we need to put these items in a knapsack of capacity W to get

the maximum total value in the knapsack. Note: Unlike 0/1 knapsack, you are allowed to break the item.

Input Format

First line of input contains two space separated integers N and W. Next line contains n integers the

elements of values array. Next line contains n integers the elements of weifht array.

Constraints

1 <= N <= 10^5

1 <= W <= 10^5

Output Format

For each test case, if Phoenix cannot place all n pieces without the scale exploding, print NO.

Otherwise, print YES followed by the rearranged array w. If there are multiple solutions, print any.

C++:

#include <bits/stdc++.h>

using namespace std;

struct Item{

    int value;

    int weight;

};

bool comp(struct Item p1,struct Item p2){

    double r1=((double)p1.value/(double)p1.weight);

    double r2=((double)p2.value/(double)p2.weight);

    return r1>r2;

}

double fractionalKnapsack(int W, Item arr[], int n)

{

    

    sort(arr,arr+n,comp);

    int curw=0;

    double finalval=0;

    for(int i=0;i<n;i++){

        if(curw+arr[i].weight <=W){

            curw+=arr[i].weight;

            finalval+=arr[i].value;

        }

        else{

            int r=(W-curw);

            finalval+=arr[i].value*((double)r/(double)arr[i].weight);

            break;

        }

    }

    return finalval;

}

int main()

{

int t;

int n, W;

cin>>n>>W;

Item arr[n];

for(int i=0;i<n;i++){

cin>>arr[i].value;

}

for(int i=0;i<n;i++)

{

  cin>>arr[i].weight;

}

printf("%.2f",fractionalKnapsack(W, arr, n));

    return 0;

}

PROBLEM 3:

Problem statement

Rick lost the password of his super locker. He remembers the number of digits N as well as the sum S

of all the digits of his password. He know that his password is the largest number of N digits that can be

made with given sum S. As he is busy doing his homework, help him retrieving his password.

Input Format

Two space separated integers N and S.

Constraints

1 ≤ N ≤ 10^4

0 ≤ S ≤ 10^4

Output Format

Print the password in the form of string, else return "-1" in the form of string

C++:

#include<bits/stdc++.h>
#include<algorithm>
#define ll long long
using namespace std;
int main()
 {
        int n,s,k;
        cin>>n>>s;
        int arr[n],j;
        if(9*n<s)
        {
            cout<<-1<<endl;
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                for(j=9;j>=0;j--)
                {
                    int k=s-j;
                    if(k>=0)
                    {
                        arr[i]=j;
                        break;
                    }
                }
                 s=s-j;
            }
            for(int p=0;p<n;p++)
            {
                cout<<arr[p];
            }
            cout<<endl;
            
        }
    return 0;
}