CodeMonk (Dynamic Programming Part- I )

CodeMonk (Dynamic Programming Part- I )

 

	///https://www.hackerearth.com/problem/algorithm/vaishu-and-best-friends/description/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 1000006
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	const int Mod = 1e9 + 7;
	int dp[maxn];
	ll pw[maxn];
	void calc()
	{
	pw[0] = 1;
	for (int i = 1; i < maxn; i++) {
	pw[i] = pw[i - 1] * 2ll;
	pw[i] %= Mod;
	}
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i < maxn; i++) {
	dp[i] = dp[i - 1] + dp[i - 2] + 2;
	dp[i] %= Mod;
	}
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	calc();
	int T;
	cin >> T;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	ll tot = pw[n];
	tot += n;
	ll ans = tot - dp[n];
	if (ans < 0) ans += Mod;
	ans %= Mod;
	cout << ans << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Vaishu and Best Friends.cpp hosted with ❤ by GitHub

	///https://www.hackerearth.com/problem/algorithm/vaishu-and-queries/description/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	ll dp[105][105][105];
	ll str[105][2];
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
	string s;
	cin >> s;
	for (auto x : s) {
	if (x == 'B')str[i][0]++;
	else str[i][1]++;
	}
	}
	for (int i = 1; i <= n; i++) {
	for (int j = 0; j < 105; j++) {
	for (int k = 0; k < 105; k++) {
	dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
	if (j >= str[i][0] && k >= str[i][1]) {
	dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - str[i][0]][k - str[i][1]] + 1);
	//dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - str[i][0]][k - str[i][1]] + 1);
	}
	}
	}
	}
	int q;
	cin >> q;
	while (q--) {
	int x, y;
	cin >> x >> y;
	cout << dp[n][y][x] << endl;
	}
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}
	/*--------------------------------------------------------------------------------------*/
	///https://www.hackerearth.com/problem/algorithm/vaishu-and-queries/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int dp[105][105][105];
	int str[105][2];
	int solve(int idx, int x, int y)
	{
	if (idx == -1) return 0;
	int &ret = dp[idx][x][y];
	if (ret != -1) return ret;
	ret = solve(idx - 1, x, y);
	if (x - str[idx][1] >= 0 && y - str[idx][0] >= 0)
	ret = max(ret, 1 + solve(idx - 1, x - str[idx][1], y - str[idx][0]));
	return ret;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
	string s;
	cin >> s;
	for (auto x : s) {
	if (x == 'B')str[i][0]++;
	else str[i][1]++;
	}
	}
	int q;
	cin >> q;
	memset(dp, -1, sizeof dp);
	while (q--) {
	int x, y;
	cin >> x >> y;
	cout << solve(n - 1, x, y) << endl;
	}
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Vaishu and Queries.cpp hosted with ❤ by GitHub

	///https://www.hackerearth.com/problem/algorithm/vaishu-and-tower-arrangements/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	cin >> T;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++) cin >> v[i];
	int neg[n];
	int d = 0;
	for (int i = n - 1; i >= 0; i--) {
	if (v[i] == -1)d++;
	//else d++;
	// pos[i] = u;
	neg[i] = d;
	//dbg3(pos[i], neg[i], i);
	}
	int u = 0;
	int ans = INT_MAX;
	for (int i = 0; i < n - 1; i++) {
	if (v[i] == 1)u++;
	//else d++;
	// int P = d + pos[i + 1]; // left side positive & right side negetive
	int N = u + neg[i + 1];
	ans = min(ans, N);
	}
	cout << ans << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Vaishu and Tower Arrangements.cpp hosted with ❤ by GitHub

Share: