Stalin69's blog

By Stalin69, history, 8 days ago, In English
  • I have this doubt from a very long time about tags of the problems.
  • when problem have tags like dp, greedy and brute force (1600+ rated problems), so is it really mean that the problem can be solved independently with these tags.
  • Does that mean, I can solve the problem using just greedy approach without some precomputation of dp or any brute force.
  • How these tags decided ?

Full text and comments »

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

By Stalin69, history, 10 days ago, In English
  • I was solving this problem from the last 2 hour almost -> 1334C - Circle of Monsters
  • I made quite submissions but I was getting TLE for my code.
  • Then I looked for some red coders solution and the thing is the logic and implementation was same, but I still submit the red coder's code and I'm surprised that IT STILL GOT TLE WHY ?
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second

void solve() {
    ll n; cin >> n;
    vector<ll> a(n), b(n);
    for (ll i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    vector<ll> cost(n, 0);
    for (ll i = 0; i < n; i++)
        cost[i] = max(0LL, a[i] - b[(i + n - 1) % n]);

    ll sum = accumulate(cost.begin(), cost.end(), 0LL);
    ll ans = (ll)1e18;
    for (ll i = 0; i < n; i++) {
        ans = min(ans, sum - cost[i] + a[i]);
    }
    cout << ans << endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll tc;
    cin >> tc;
    while (tc--)
        solve();
    return 0;
}
  • I don't know what's the problem in this very simple and clean code and still I'm facing this issue.
  • Can anyone please consider this problem and tell me, why it is giving me TLE ?

Full text and comments »

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

By Stalin69, history, 3 weeks ago, In English

CSES Problem runtime Error :

Today, I was solving a CSES problem named Book Shop which is a standard DP problem, But I'm getting runtime error on same solution when I'm using long long instead of int. I'm not able to figure the reason, why it is not working.

But working with the same solution when I used int and it got accepted.

Can anybody just tell me the exact reason and when these types of problems can occur ?

Here is the code that gives me runtime error (used long long everywhere)

// A.cpp
 
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e17
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits(x) __builtin_popcountll(x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
 
void solve() {
	ll n, x;
	cin >> n >> x;
 
	vector<pair<ll, ll>> arr(n + 1);
	for (ll i = 1; i <= n; i++)
		cin >> arr[i].ff;
	for (ll i = 1; i <= n; i++)
		cin >> arr[i].ss;
 
	vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, 0LL));
 
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= x; j++)
			dp[i][j] = (j >= arr[i].ff ? max(dp[i - 1][j], dp[i - 1][j - arr[i].ff] + arr[i].ss) : dp[i - 1][j]);
 
	cout << dp[n][x] << endl;
}
 
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll tc;
	tc = 1;
	// cin >> tc;
	for (ll i = 1; i <= tc; i++) {
		solve();
	}
 
	return 0;
}

Is it due to strict memory guidelines on CSES ? So I need to use int for most of the problems.

Full text and comments »

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