rum3r's blog

By rum3r, 3 weeks ago, In English

I don't know why my code gives RE on this problem. Code . Even I checked any type of out of bound error or memory related issue but nothing fruitful found. Still give RE :(

Read more »

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

By rum3r, 4 weeks ago, In English

Problem

Can anyone explain me, Why only counting the size of the adjacent vertices of a particular vertex(using std::set) and having the max among them, gives WA? 
How this is different with the DSU? Everyone is using DSU in their solution! And even the editorial.

Thanks!!

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By rum3r, history, 4 weeks ago, In English

Just a small doubt regarding this problem.

Can anyone tell me why we are choosing m moves from a total of (n+m) moves to reach coordinate (x, y)?

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By rum3r, history, 2 months ago, In English

What am I doing wrong in this problem?

inline void solve(){
		ll n;
		cin >> n;
		ll a[n], b[n];
		for(int i=0; i<n; ++i) {
			cin >> a[i];
		}
		for(int i=0; i<n; ++i) {
			cin >> b[i];
		}
		ll dp[3][n];
		dp[0][0] = a[0];  //selecting first person
		dp[1][0] = b[0];  //selecting second person
		dp[2][0] = 0;     //not selecting anyone
		for(int i=1; i<n; ++i) {
			dp[0][i] = max(dp[1][i-1]+a[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for first person
			dp[1][i] = max(dp[0][i-1]+b[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for second person
			dp[2][i] = max(dp[0][i-1], dp[1][i-1]);  //for not selecting
		}
		cout << max(dp[0][n-1], dp[1][n-1]) << endl;  //taking max over all..
}

PROBLEM Any help would be appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By rum3r, history, 2 months ago, In English

Cananyone explain me the DP solution of this problem??

Why we are using DP? Why this solution isn't giving correct Answer?

###

What's the complexity of the solution that I have written I know for sieve it's O(N*log(logN)). But I have modified that.

const int maxN = 2e5 + 9;
bool prime[maxN];
int cnt[maxN];
void sieve(){
	for(int i=2; i<=maxN; ++i){
		prime[i] = 1;
		cnt[i] = 0;
	}
	prime[0] = prime[1] = 0;
	for(ll i=2; i*i<=maxN; ++i){
		if(prime[i]){
			cnt[i] = 1;
			//incrementing all the multiples of primes by 1..
			for(int j=2*i; j<=maxN; j+=i){
//				dbg3(i, j, cnt[j]);
				prime[j] = 0;
				cnt[j]++;
			}
		}
	}
	//incrementing all primes after root N by 1.. 
	for(int i=sqrt(maxN); i<=maxN; ++i){
		if(prime[i]){
			cnt[i] =1;
		}
	}
	
}

PROBLEM

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By rum3r, history, 2 months ago, In English

Can anyone tell me why I am getting TLE with this Top Down Recursive (Rectangle Cutting CSES) and also Runtime Error. Thought I have memoized the results. Is the time complexity still more than O(a^2*b + a*b^2). I know you may ask why top down. I am just trying to explore possible ways. Code--

int solve(vector<vector<int>> dp, int l, int b){
	if(l == b){
		return 0;
	}
	if(l==0 || b==0){
		return 0;
	}
	if(dp[l][b] != inf){
		return dp[l][b];
	}
	for(int k=1; k<l; ++k){
		dp[l][b] = min(dp[l][b], 1+solve(dp, k, b)+solve(dp, l-k, b));
	}
	for(int k=1; k<b; ++k){
		dp[l][b] = min(dp[l][b], 1+solve(dp, l, k)+solve(dp, l, b-k));
	}
	return dp[l][b];
}

PROBLEM [](https://cses.fi/problemset/task/1744/)

ANY HELP WOULD BE APPRECIATED!! PEACE!!

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By rum3r, history, 3 months ago, In English
Can somebody explain 2D difference array with prefix sums?

Problem

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By rum3r, history, 4 months ago, In English

This is the program that I am using..

int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		map<int, int> cnt;
		int mx = 0;
		for (auto &it : a) {
			if (it % k == 0) continue;
			++cnt[k &mdash; it % k];
			mx = max(mx, cnt[k &mdash; it % k]);
		}
		long long ans = 0;
		for (auto [key, value] : cnt) {
			if (value == mx) {
				ans = k * 1ll * (value &mdash; 1) + key + 1;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

DOUBTS: 1. Why error is thrown while using ( auto [key, value] ) ? 2. Why we are using map and why we can't use an unordered map (operations are O(1)) in comparison to logN ? 3. Why unordered map is giving wrong answer?

PROBLEM STATEMENT: ~~~~~ https://codeforces.com/problemset/problem/1374/D ~~~~~

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By rum3r, history, 4 months ago, In English
A lot of questions have discrete Maths in CP. (although i have only solved 400+ problems) How much do we need actually? So, I researched about it and I came across this book Discrete Maths [by Kenneth H. Rosen]
Although a great book, but the real issue is that its very long. `So what would you recommend a beginner like me to start with or which are chapter or resources I should pick first.` To enhance my CP skills.
Thanks for helping in advance!!

Read more »

 
 
 
 
  • Vote: I like it
  • -26
  • Vote: I do not like it

By rum3r, history, 4 months ago, In English
Hey guys!
Can anybody explain how to implement binary search on this question? And why my code is not working..
Thanks in Advance. PEACE!

CODE-

while(t--)
		{
			int n; cin>>n;
			vector<int> v;
			v.push_back(5);
			int last = 5;
			for(int i=sqrt(n);i>=0;){
				int l=0,h=sqrt(n);
				while(h-l>1){
					int m = (l+h)>>1;
					if(m<last){
						last = m;
						h = m;
					}else
					l = m+1;
				}
				v.push_back(last);
				i = last;
			}
			cout<<v.size()<<endl;
			sort(v.begin(),v.end());
			for(auto it: v)
			cout<<it<<' ';
			cout<<endl;
		}

}

QUESTION LINK:

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By rum3r, history, 4 months ago, In English
Can anyone please tell me how to submit problems solutions on Topcoder. I know about that Java applet thing but that isn't working. Tell me a proper method to do that.

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it