Join Us
Loading Similar Posts
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;
}
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;
}
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;
}
}
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;
}
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;
}
}
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";
}
}
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]