Question: DE SHAW OA | IIT Madras | SWE Internship | 2023
1
Entering edit mode

ADD COMMENTlink 15 months ago PoGo 2.4k
Entering edit mode
3

Question 2 is almost same as House Robber in Dyanmmic Programming.

Since, A[I]<=2e5+1, you can iterate over all numbers

dp[I]= Maximum Value you can form using numbers I to MAX(A[I]) 

Transitions:-

       when take i =>dp[I]=(freq of i) * i +fun(i+2)

       when not take i =>dp[I]=fun(i+1)

Take max of both 

Ans:- dp[0] 

 

ADD REPLYlink 15 months ago
Aman
• 110
1
Entering edit mode

Greedy Approach (I have test 2,3 examples it work as expected. It may or maynot work depending on edges cases) Try appending character which is >= char in string 2. If at end the string is small then there is no possibility since we were placing characters greedily. At the end if strings are equal we find the first index from last and swap with last value in order to make res > string 2.
 

using ll=long long int ;

int main() {
 string n1,n2;
    cin>>n1>>n2;
    map <int,int> mp1,mp2;
    for (auto &i:n1) {
        mp1[i-'0']++;
        
    }
    for (auto &i:n2) {
        mp2[i-'0']++;
    }
    int n=n1.size();
    string res="";
    for (int i=0;i<n;i++) {
        int curr=n2[i]-'0';
       
        auto it=mp1.lower_bound(curr);
        if (it != mp1.end()) {
         int vl=it->first;
            res += char(vl+'0');
            mp1[vl]--;
            if (mp1[vl]==0) {
                mp1.erase(vl);
            }
            
        }
        else {
            it=prev(it);
              int vl=it->first;
            res += char(vl+'0');
            mp1[vl]--;
            if (mp1[vl]==0) {
                mp1.erase(vl);
            }
        }
    }
     if (res ==n2) {
             char ch=res[n-1];
            for (int i=n-1;i>=0;i--) {
                 if (n2[i]<ch  ) {
                      
                     res[n-1]=res[i];
                     res[i]=ch;
                     cout<<res<<endl;
                     return 0;
                 }
            }
     }
   if (res > n2) {cout<<res<<endl;}
    else {cout<<"-1"<<endl;}
    
   
    

    return 0;
    
}

 

ADD COMMENTlink 15 months ago Sahil Kumar • 260
1
Entering edit mode

I have run for some Case it might work


#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define inf (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

 void next_per(string &h)
    {
      int n=h.size();
      int k=-1;
      for(int i=n-2;i>=0;i--){
          if(h[i]<h[i+1]){
              k=i;
              break;
          }
      }
      if(k==-1){
          reverse(h.begin(),h.end());
          return;
      }
      for(int i=n-1;i>k;i--){
          if(h[k]<h[i]){
              swap(h[k],h[i]);
              break;
          }
      }
      reverse(h.begin()+k+1,h.end());
      return;
    }

int main() {
string n,k;
cin>>n>>k;

map<char,int> mp1;
map<char,int> mp2;

for(int i=0;i<n.size();i++){
    mp1[n[i]]++;
}
for(int i=0;i<k.size();i++){
    mp2[k[i]]++;
}


string res="";
int y=0;
for(int i=0;i<k.size();i++){

    auto it=mp1.lower_bound(k[i]);
    if( it!=mp1.end() ){
        res+=it->first;
        it->second--;
        if(it->first > k[i])y=1;
        if(it->second ==0){
            mp1.erase(it);
        }
        if(y==1)break;
    }else{
        if(res.size()==0){
            cout<<-1<<endl;
            return 0;
        }
        
        y=1;
        
        
    }
    
}

if(res==k){
    next_per(res);
    if(res<=k){
        cout<<-1<<endl;
        return 0;
        }
    
    cout<<res<<endl;    
}
if(y==1){
    for(auto &i:mp1){
        int h=i.second;
        while(h--){
            res+=i.first;
        }
    }
    while(k>res){
        next_per(res);
    }
    cout<<res<<endl;
}

   return 0;
}

 

ADD COMMENTlink 4 months ago Krishna • 30
1
Entering edit mode

Q2

#include<bits/stdc++.h>

using namespace std;

#define hiii ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#define ll long long
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define pp pop_back
#define sort(v) sort((v).begin(), (v).end())

void f(int s, vector < int > & ds, vector < vector < pair < int, int >>> & adj) {
  priority_queue < pair < int, int > , vector < pair < int, int >> , greater < pair < int, int >> > pq;

  pq.push({
    s,
    0
  });
  ds[s] = 0;
  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    if (ds[p.first] < p.second) continue;
    for (auto & j: adj[p.first]) {
      if (p.second + j.second < ds[j.first]) {
        ds[j.first] = p.second + j.second;
        pq.push({
          j.first,
          ds[j.first]
        });
      }
    }
  }

  return;
}

int main() {
  ll n, m;
  cin >> n >> m;

  vector < vector < pair < int, int >>> adj(n + 1);
  vector < vector < pair < int, int >>> adj1(n + 1);
  vector < pair < int, int >> v;

  for (int i = 1; i <= m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;

    v.push_back({
      a,
      b
    });
    adj[a].push_back({
      b,
      c
    });
    adj1[b].push_back({
      a,
      c
    });
  }

  ll s, t;
  cin >> s >> t;

  vector < int > ds(n + 1, INT_MAX);
  vector < int > dt(n + 1, INT_MAX);
  f(s, ds, adj);
  f(t, dt, adj1);

  // for(int i=1;i<=n;i++){
  // cout<<ds[i]<<" "<<dt[i]<<endl;
  //}

  for (int i = 0; i < m; i++) {
    int s = v[i].first;
    int b = v[i].second;

    cout << ds[s] + dt[b] << endl;
  }
}

 

ADD COMMENTlink 4 months ago Krishna • 30
1
Entering edit mode

Q3

 

#include<bits/stdc++.h>
using namespace std;

#define hiii ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define ld long double
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define pp pop_back
#define sort(v) sort((v).begin(),(v).end())

map<int,int> mp;
int mod=1e9+7;
vector<vector<int>> dp;

int f(int i,int j,vector<int> &v){
    if(j<i || i<0 || j>=v.size()) return 0;
    
    //cout<<i<<" "<<j<<endl;
    
    int t=0;
    
    if(dp[i][j]!=-1) return dp[i][j];
    
    for(int k=i;k<=j;k++){
        t=max(t,mp[v[k]]*v[k]+ ( (v[k+1]==v[k]+1) ? f(k+2,j,v) : f(k+1,j,v) ) + ((v[k-1]==v[k]-1) ? f(i,k-2,v) : f(i,k-1,v)));
    }
    
    return dp[i][j]=t;
}

int main(){
    ll n;
    cin>>n;
    
    vector<int> v;
    set<int> st;
    
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        mp[a]++;
        st.insert(a);
    }
    
    for(auto &j:st){
        v.push_back(j);
    }
    
    dp.resize(n+1,vector<int>(n+1,-1));
    
    cout<<f(0,v.size()-1,v)<<endl;
}

 

ADD COMMENTlink 4 months ago Krishna • 30
0
Entering edit mode

Q2

 

#include<bits/stdc++.h>

using namespace std;

 

//for pbds(order set)

// #include<ext/pb_ds/assoc_container.hpp>

// #include<ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

// // find_by_order(index pr kayu element che), order_of_key(how many lesser element)

 

// --------------------------------------

#define hiii ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define ll long long

#define ld long double

#define yes cout<<"YES"<<endl

#define no cout<<"NO"<<endl

#define pb push_back

#define pp pop_back

#define sort(v) sort((v).begin(),(v).end())

// -------------------------------------

 

void f(int s,vector<int> &ds,vector<vector<pair<int,int>>>& adj){

priority_queue< pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > pq;

pq.push({s,0});

ds[s]=0;

while(!pq.empty()){

auto p=pq.top();

pq.pop();

if(ds[p.first]<p.second)continue;

for(auto &j:adj[p.first]){

if(p.second+j.second<ds[j.first]){

ds[j.first]=p.second+j.second;

pq.push({j.first,ds[j.first]});

}

}

}

return;

}

 

int main(){

ll n,m;

cin>>n>>m;

vector<vector<pair<int,int>>> adj(n+1);

vector<vector<pair<int,int>>> adj1(n+1);

vector<pair<int,int>> v;

for(int i=1;i<=m;i++){

ll a,b,c;

cin>>a>>b>>c;

v.push_back({a,b});

adj[a].push_back({b,c});

adj1[b].push_back({a,c});

}

ll s,t;

cin>>s>>t;

 

vector<int> ds(n+1,INT_MAX);

vector<int> dt(n+1,INT_MAX);

f(s,ds,adj);

f(t,dt,adj1);

// for(int i=1;i<=n;i++){

// cout<<ds[i]<<" "<<dt[i]<<endl;

//}

 

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

int s=v[i].first;

int b=v[i].second;

cout<<ds[s]+dt[b]<<endl;

}

 

 

}

ADD COMMENTlink 4 months ago Krishna • 30
0
Entering edit mode

Question 2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define vll vector<ll>

#define pll pair<ll, ll>

#define vvpll vector<vector<pair<ll, ll>>>

#define for0(i, l, r) for (ll i = l; i < r; i++)

 

ll n, m, s, t;

vll g_from, g_to, g_weight;

 

void Solve(vvpll &adj, vll &dis, ll &s)

{

 

   priority_queue<pll, vector<pll>, greater<pll>> pq;

   dis[s] = 0;

   pq.push({0, s});

 

   while (!pq.empty())

   {

       pll temp = pq.top();

       pq.pop();

       ll u = temp.second;

       if (dis[u] < temp.first)

           continue;

       for (auto &it : adj[u])

       {

           ll v = it.first;

           ll w = it.second;

           if (dis[v] > dis[u] + w)

           {

               dis[v] = dis[u] + w;

               pq.push({dis[v], v});

           }

       }

   }

}

 

int main()

{

   cin >> n >> m;

   g_from.resize(m);

   g_to.resize(m);

   g_weight.resize(m);

   vvpll adj(n + 1);

   vvpll adj1(n + 1);

   vll dis(n + 1, LLONG_MAX);

   vll dis1(n + 1, LLONG_MAX);

   for0(i, 0, m)

   {

       ll u, v, w;

       cin >> u >> v >> w;

       g_from[i] = u;

       g_to[i] = v;

       g_weight[i] = w;

       adj[u].pb({v, w});

       adj1[v].pb({u, w});

   }

 

   cin >> s >> t;

   Solve(adj, dis, s);

   Solve(adj1, dis1, t);

 

   for0(i, 0, m)

   {

       ll u = g_from[i];

       ll v = g_to[i];

       cout << min(dis[t], dis[u] + dis1[v]) << "\n";

   }

}

 

ADD COMMENTlink 3 months ago Kaushan Dey • 30

Login before adding your answer.

Similar Posts
Loading Similar Posts