Blog entries - Codeforces

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Rock2000's blog

How to solve this problem of CEOI Mirror 2020?

By Rock2000, history, 4 years ago, In English

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.

Full text and comments »

Rock2000
4 years ago
0

How to prove the solution for this problem? Help needed... [Problem: Slava and Tanks]

By Rock2000, 4 years ago, In English

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.

Full text and comments »

#help

Rock2000
4 years ago
2

Flipkart coding test problem... Need help [update: Solved]

By Rock2000, history, 4 years ago, In English

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_

Code

#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();
	}
}

Full text and comments »

#flipkart, #help

Rock2000
4 years ago
20

CSES- Maximum Subarray II | Why is this code giving correct answer?

By Rock2000, history, 4 years ago, In English

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

Code 1

#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();
	}
}

Code 2

#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();
	}
}

Full text and comments »

cses, maximum subarray sum

Rock2000
4 years ago
5

Can anybody explain me this code of tourist from yesterday's contest?

By Rock2000, history, 4 years ago, In English

Problem link

Tourist Code

/**
 *    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.

Full text and comments »

-2

Rock2000
4 years ago
1

[Video Tutorial] DP Tutorial for Beginners "The Number of Products"

By Rock2000, history, 4 years ago, In English

Hello guys, I made a video for the Problem The Number of Products
Link to Video
I hope you like this video.

Full text and comments »

-9

Rock2000
4 years ago
0

[Video Tutorial] Different Way To Solve Flipping Game Problem

By Rock2000, history, 4 years ago, In English

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.

Full text and comments »

-7

Rock2000
4 years ago
1

Complete Dynamic Programming Course

By Rock2000, history, 4 years ago, In English

Hello Codeforces, I am going to create Complete Dynamic Programming Course on my YouTube Channel. I will be covering the following topics:

Dynamic Programming Introduction
One Dimensional DP
Multidimensional DP
Advanced DP: SOS DP, Digit DP, DP with bitmasking, etc.

Links to videos:

1. Dynamic Programming Introduction (May 23 2020)
2. Fibonacci Implementation- Top Down and Bottom Up DP (May 24 2020)
3. States in DP (May 26 2020)
4. Sasha & a Bit of Relax | Codeforces round- 539 | Approaching Easy DP Problem (May 26 2020)
5. Sasha & a Bit of Relax | Coding (May 26 2020)
6. Minimum Steps to One (May 29 2020)
7. Minimum Steps to One | Code (May 29 2020)
8. Prefix Sum Array | 1D | 2D (May 31 2020)
9. Minimum Coin Change (June 2 2020)
10. Wines Problem with Code (June 4 2020)
11. Flipping Game Codeforces (June 6 2020)
12. The Number of Products Codeforces (June 10 2020)
13. Ivan The Fool and The Probability Theory (June 22 2020)

I hope you like the videos.

Full text and comments »

Rock2000
4 years ago
4