Join Us
Loading Similar Posts
Entering edit mode
Avg CTC: 10lpa
Role: Consulting Engineer, Software Engineer and other roles
Job Link: Consulting Engineer Link
Early in Career Job Post Links: Other Job Roles
Question 1
Click here to Practice
Submit Problem to OJ
Earn Maximum Money
You are given 'n' piggy banks, indexed from 0 to n-1. Each piggy bank contains some amount of money in it which is represented by an array 'nums'. You are asked to break all the piggy banks in any order.
If you break the ith piggy bank, you will get the amount equivalent to (nums[i-1]nums[i]nums[i+1]) dollars. If i-1 or i+1 goes out of bounds of the array, then treat it as if there is a piggy bank with 1 US Dollar in it.
The goal is to return the maximum amount of dollars you can collect by breaking the piggy banks.
Input Format
First line contains n, the number of piggy banks.
Second line contains an array nums representing the amount of money in each piggy bank.
Constraints
- 1 <= n <= 300
- 0 <= nums[i] <= 100 where i is [0,n-1]
Output Format
An integer representing maximum amount of money.
Sample input 0
4
3 1 5 8
Sample output 0
167
Explanation 0
Initially you have [3,1,5,8]. Break the bank at index 1 i.e. one with 1 dollar. Amount collected is (315) i.e. 15. Remaining banks are as [3,5,8]. Now break the bank at index 1 with 5 dollars. Amount collected is (358) i.e. 120. So total amount is now 135. Remaining banks are as [3,8]. Now break the bank at index 0 with 3 dollars. Amount collected is (138) i.e. 24. So total amount is 159. Remaining banks are as [8]. Now break the last bank with 8 dollars. Amount collected is (181) i.e. 8. Final amount is now 167. Any other order would result in a lower collection.
Sample input 1
2
1 5
Sample output 1
10
Question 2
Click here to Practice
Submit Problem to OJ
Question 3
Entering edit mode
Women leading
The solution is very simple, we need to find any substring which has some x number of 'W' occurring adjacent to each other followed by x number of 'M' occurring adjacent to each other. This can be done in an easy way by converting the string into a continuous set of numbers. These numbers would denote the occurrence of same characters in a continuous sequence. We would use +ve sign for women and -ve sign for men in order to differentiate. For example: in case of "WWWMMMWMWMWWW" our array would be : 3,-3,1,-1,1,-1,3 .
In order to get the answer we would take any two consecutive numbers such that positive number is the first number. In other words consider two consecutive numbers arr[i], arr[i+1], such that arr[i] > 0, then our answer would be have min(abs(arr[i]),abs(arr[i+1])) W's followed by that many M's, which implies that are answer would be 2 * min(abs(arr[i]),abs(arr[i+1])) We will iterate through the entire array in order to find the maximum answer.
Entering edit mode
Subsegment sort
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> &v){
vector<int> sorted = v;
sort(sorted.begin(), sorted.end());
int n = v.size();
unordered_map<int, vector<int>> mp;
for(int i=n-1;i>=0;i--){
mp[sorted[i]].push_back(i);
}
int mx = -1;
int ans = 0;
for(int i=0;i<n;i++){
int index = mp[v[i]].back();
mp[v[i]].pop_back();
mx = max(mx, index);
if(mx==i){
ans++;
mx = -1;
}
}
return ans;
}
int main(){
vector<int> v = {2,5,1,9,7,6};
int ans = solve(v);
cout<<ans<<endl;
}
Entering edit mode
women leading
#include <bits/stdc++.h>
using namespace std;
void count(int n, string s){
int i = 0;
int count= 0;
while(i < n){
if(s[i] == 'W'){
int cnt = 0;
while(s[i] == 'W' && i < n){
i++;
cnt++;
}
int cnt2 = 0;
while(s[i] == 'M' && i < n){
i++;
cnt2++;
}
count = max(count,min(cnt,cnt2));
}
else{
i++;
}
}
if(count == 0) cout<<-1<<endl;
else cout<<count*2<<endl;
}
void solve() {
// int n;
// cin >> n;
string s;
cin >> s;
int n = s.size();
//int ns = s.size();
count(n,s);
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
Entering edit mode
Earn maximum money
Bruteforce: Generate all permutations for the ordering of piggy banks and check which permutation yields the best profit. But it will take O(n!) time.
DP Solution: For a DP solution to exist, we need to define the subproblems. Let's define the problem first as: \ solve(nums, i, j) by which I mean that we need to burst balloons starting from index i to index j. At the beginning, they'll be 0, nums.size() -1 respectively. Let's suppose we burst the kth balloon in the first chance. We will get nums[k-1] nums[k] nums[k+1] coins. Now let's define the subproblems as: solve(nums, i, k - 1) , solve(nums, k + 1, j) As the balloon k is already burst, we solve the subproblems from i to k -1 and k + 1 to j. But wait, what's going wrong here? The subproblem solve(nums, i, k - 1) and solve(nums, k + 1, j) are not independent since after bursting kth balloon, balloon k - 1 and k + 1 have become adjacent and they will need each other in order to calculate the profit.
So, as we saw that if we choose the kth balloon to be the first one to be burst, we can't make the subproblems independent. Let's try the other way round. We choose the kth balloon as the last one to be burst. Now the subproblems will become independent since (k - 1)th balloon and (k + 1)th balloon won't need each other in order to calculate the answer. (Try it out using pen and paper).
Now for each k starting from i to j, we choose the kth balloon to be the last one to be burst and calculate the profit by solving the subproblems recursively. Whichever choice of k gives us the best answer, we store it and return. Important point to be noted here is that the balloons in the range (i, k - 1) and (k + 1, j) will be burst BEFORE kth balloon. So, when we burst the kth balloon, the profit will be nums[i - 1] nums[k] nums[j + 1] PROVIDED that index i - 1 and j + 1 are valid.
Entering edit mode
Subsegment Sort
Brute Force: Copy the elements of the array in another array and sort it. Then for each partition in original array check if that partition after sorting belongs to the sorted array. Time Complexity : O(n^2*log(n))
Optimised Approach: Let's first take an example to understand the question and approach better :
n=6 array = {2,5,1,9,7,6}
Above array can be partitioned into two parts : {2,5,1}, {9,7,6}. If we sort the two parts separately then, {1,2,5} and {6,7,9} will be the answer and if we merge them then we will get {1,2,5,6,7,9} which is the sorted array.
Now, if we observe in above example we have to consider 1 in the first partition, if we will not consider 1 in first partition then final array will never be sorted. So, the maximum number of the left partition should always be less than or equal to the minimum number of the right partition. Because after that only if we merge both the partition then the final array will be sorted.
So, we just need to make prefix max array and suffix min array and for each i from 0 to n-2 if prefixMax[i]<=suffixMin[i+1] then we can make partition between i and i+1.
Time Complexity : O(n)
Entering edit mode
earn max money
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> &nums){
vector<int> v;
v.push_back(1);
for(int itr: nums){
v.push_back(itr);
}
v.push_back(1);
int n = v.size();
vector<vector<int>> dp(n+1, vector<int> (n+1, 0));
for(int i=n-1; i>=0; i--){
for(int j=0; j<n; j++){
if(j-i<2){
continue;
}
int ans = 0;
for(int k=i+1; k<=j-1; k++){
int tempans = v[k]*v[i]*v[j] + dp[i][k] + dp[k][j];
ans = max(ans, tempans);
}
dp[i][j] = ans;
}
}
cout<<dp[0][n-1]<<endl;
}
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
solve(v);
}
