Can someone please tell me how to solve this problem? I saw the editorial but couldn't understand how to solve the subtask 7. Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Can someone please tell me how to solve this problem? I saw the editorial but couldn't understand how to solve the subtask 7. Thanks in advance.
I was solving this problem. I solved it with my intuition and the solution I thought was also given in the editorial. But I couldn't find proof of this solution anywhere. Can anyone please give me proof for the solution of this problem. Thanks in advance.
I appeared for Flipkart coding test day before yesterday and got stuck on this problem:
You are given an undirected weighted graph with n vertices and m edges. In one move you can make any edge weight zero. You can perform atmost K moves. You have to tell what is the shortest path from a starting node A to an ending node B after performing atmost K moves.
1<=n<=1000
0<=K<n
1<=m<=10000
1<=w<=10^9 (weight of edge)
Can anybody please tell me how to approach this problem?
I found this problem on quora also but couldn't understand the approach clearly.
[UPD]: This problem has been solved thanks to ExplodingFreeze and _dobby_
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
// Policy based data structure
typedef tree<int, null_type,
less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 1005
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll>
/*******************************************************************/
struct state{
ll dist,node,used;
state(ll dist1,ll node1,ll used1){
dist=dist1;
node=node1;
used=used1;
}
bool operator<(const state&s) const{
if(this->dist==s.dist){
if(this->node==s.node){
return this->used < s.used;
} else{
return this->node < s.node;
}
} else{
return this->dist < s.dist;
}
}
};
ll n,m,a,b,k;
vii adj[N];
ll dist[N][N];
void solve(){
cin>>n>>m>>a>>b>>k;
rep(i,0,m){
ll u,v,w;
cin>>u>>v>>w;
adj[u].eb(v,w);
adj[v].eb(u,w);
}
rep(i,0,n+1){
rep(j,0,k+1){
dist[i][j]=inf;
}
}
rep(i,0,k+1){
dist[a][i]=0;
}
map<pii,pii> pa;
set<state> s;
s.insert(state(0,a,0));
while(!s.empty()){
state curr=*s.begin();
// curr.print();
s.erase(s.begin());
for(auto ch:adj[curr.node]){
if(dist[ch.F][curr.used]>dist[curr.node][curr.used] + ch.S){
state temp(dist[ch.F][curr.used],ch.F,curr.used);
auto it=s.find(temp);
if(it!=s.end())
s.erase(it);
dist[ch.F][curr.used]=dist[curr.node][curr.used] + ch.S;
pa[{ch.F,curr.used}]={curr.node,curr.used};
temp.dist=dist[ch.F][curr.used];
s.insert(temp);
}
if(curr.used+1<=k and dist[ch.F][curr.used+1]>dist[curr.node][curr.used]){
state temp(dist[ch.F][curr.used+1],ch.F,curr.used+1);
auto it=s.find(temp);
if(it!=s.end())
s.erase(it);
dist[ch.F][curr.used+1]=dist[curr.node][curr.used];
pa[{ch.F,curr.used+1}]={curr.node,curr.used};
temp.dist=dist[ch.F][curr.used+1];
s.insert(temp);
}
}
}
ll ans=inf;
rep(i,0,k+1){
ans=min(ans,dist[b][i]);
}
if(ans>=inf){
cout<<-1<<endl;
} else{
cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
}
The first code is giving correct answer while second code is giving wrong answer. The only difference between these two codes is:
In the first code the return value is -2*inf in the getmax function while it is -inf in the second code. Can anybody please help me figure out what is the problem?
Link to Problem
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 200100
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll>
void sout(){
cout<<endl;
}
template <typename T,typename... Types>
void sout(T var1,Types... var2){
cout<<var1<<" ";
sout(var2...);
}
/*******************************************************************/
ll arr[N];
ll pre[N];
ll tree[4*N];
ll n,a,b;
void build(ll s,ll e,ll ind=1){
if(s==e){
tree[ind]=pre[s];
return;
}
ll mid=(s+e)/2;
build(s,mid,2*ind);
build(mid+1,e,2*ind+1);
tree[ind]=max(tree[2*ind],tree[2*ind+1]);
}
ll getmax(ll s,ll e,ll l,ll r,ll ind=1){
if(e<l or s>r)
return -2*inf;
if(s>=l and e<=r)
return tree[ind];
ll mid=(s+e)/2;
ll a=getmax(s,mid,l,r,2*ind);
ll b=getmax(mid+1,e,l,r,2*ind+1);
return max(a,b);
}
ll getmax(ll l,ll r){
return getmax(0,n,l,r);
}
void solve(){
cin>>n>>a>>b;
rep(i,1,n+1){
cin>>arr[i];
}
pre[0]=0;
rep(i,1,n+1){
pre[i]=pre[i-1]+arr[i];
}
build(0,n);
ll ans=-inf;
for(ll i=a;i<=n;i++){
ll x=getmax(min(n,i+1),min(n,i+b-a));
x=x-pre[i];
x=max(x,0LL);
// sout("x",x);
ll loc=x+pre[i]-pre[i-a];
ans=max(ans,loc);
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 200100
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll>
void sout(){
cout<<endl;
}
template <typename T,typename... Types>
void sout(T var1,Types... var2){
cout<<var1<<" ";
sout(var2...);
}
/*******************************************************************/
ll arr[N];
ll pre[N];
ll tree[4*N];
ll n,a,b;
void build(ll s,ll e,ll ind=1){
if(s==e){
tree[ind]=pre[s];
return;
}
ll mid=(s+e)/2;
build(s,mid,2*ind);
build(mid+1,e,2*ind+1);
tree[ind]=max(tree[2*ind],tree[2*ind+1]);
}
ll getmax(ll s,ll e,ll l,ll r,ll ind=1){
if(e<l or s>r)
return -inf;
if(s>=l and e<=r)
return tree[ind];
ll mid=(s+e)/2;
ll a=getmax(s,mid,l,r,2*ind);
ll b=getmax(mid+1,e,l,r,2*ind+1);
return max(a,b);
}
ll getmax(ll l,ll r){
return getmax(0,n,l,r);
}
void solve(){
cin>>n>>a>>b;
rep(i,1,n+1){
cin>>arr[i];
}
pre[0]=0;
rep(i,1,n+1){
pre[i]=pre[i-1]+arr[i];
}
build(0,n);
ll ans=-inf;
for(ll i=a;i<=n;i++){
ll x=getmax(min(n,i+1),min(n,i+b-a));
x=x-pre[i];
x=max(x,0LL);
// sout("x",x);
ll loc=x+pre[i]-pre[i-a];
ans=max(ans,loc);
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
}
/**
* author: tourist
* created: 04.07.2020 18:34:48
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(n);
iota(b.begin(), b.end(), 0);
sort(b.begin(), b.end(), [&](int i, int j) {
if (a[i] != a[j]) {
return a[i] < a[j];
}
return i < j;
});
vector<pair<int, int>> ret;
for (int it = 0; it < n; it++) {
for (int i = 0; i < n - 1; i++) {
if (b[i] > b[i + 1]) {
ret.emplace_back(b[i + 1], b[i]);
swap(b[i], b[i + 1]);
}
}
}
cout << ret.size() << '\n';
for (auto& p : ret) {
cout << p.first + 1 << " " << p.second + 1 << '\n';
}
return 0;
}
What I do not understand is how after finding array b we get the correct answer.
Thanks in advance.
Hello guys, I made a video for the Problem The Number of Products
Link to Video
I hope you like this video.
Hello Codeforces, I recently started my YouTube Channel and started to create a Complete Dynamic Programming Course from beginner to advanced. And today I made a video on Flipping Game Problem which I find very interesting. In the video I explained how to reach from O(n^3) to O(n) time complexity.
Link to video
Please watch at 1.25x speed for better experience.
I hope you like the video.
Hello Codeforces, I am going to create Complete Dynamic Programming Course on my YouTube Channel. I will be covering the following topics:
Name |
---|