Um, hi ... ? Basically we have a number N (N <= 10^5000000) represented by a string. Let say that |N] = the length of string N. Now I'm given an integer k (k <= 1e9). How do I confirm that N is divisible by k in O(|N|) ??

P/S : Notice that I want solution that works in O(|N|), not O(|N|log5000000). Anyone can help me ?

While I'm doing problems on CSES like always, I met with a rather interesting problem : CSES-Stick Lengths. After solving it, I discover there was actually atleast 3 ways to do this problem (all in O(NlogN)): the one I used to AC, other one using Ternary Search, and finally, using a prominent solution that I saw others used. The idea for the third was short : You sort the whole array, take the median (N/2) as the target value and calculate the result using it. Here it how it goes on USACO :

#include <bits/stdc++.h>

using namespace std;

//variables used for the current problem
int n,median;
vector<int> p;
long long ans,cnt;

void solve() {
	cin >> n;
	p.resize(n);
	for (int &x : p){
		cin >> x;
	}
	sort(p.begin(),p.end());
	median=p[n/2];
	for (const int &x : p){
		ans+=abs(median-x); //Calculate the cost to modify the stick length
	}
	cout << ans << "\n";
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

After a while of observation, I myself must admit the solution's correctness. But I just couldn't proof it. Can you guys help me with it ?

Recently I've been doing this USACO problem. After a while I came up with a simple idea. I'll have dp[i][j] as the maximum result from the i-th element to the j-th element, calculate each range in increasing order. If there are two subarrays [L, X] and [X+1, R] and dp[L][X] equal to dp[X+1][R], then result for dp[L][R] is dp[L][X]+1, else I will just take max(dp[L][X], dp[X+1][R]) as an answer. This seem right to me as I tested it against some small cases. But there are 12 tests in total, and I have those WAs from test (7 -> 12). The expected answer is always smaller than my output, for example, if the true answer is X, then my code output X+1. Those test case is just to large for me to check (N = 248) so I'm here asking for help. Why am I wrong ? Which mistake did I make ?

Below is my code for this problem :

#include <bits/stdc++.h>
using namespace std;

const int N = 248;
int n, a[N], dp[N][N];

int32_t main () {
	freopen("248.out", "w", stdout);
	freopen("248.in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for (int i = 0; i < n; i++) cin>>a[i];
	for (int i = 0; i < n; i++) dp[i][i] = a[i];
	for (int len = 2; len <= n; len++) {
		for (int i = 0; i < n; i++) {
			int j = i+len-1;
			if (j >= n) break;
			for (int k = i; k < j; k++) {
				int cur_ans = max(dp[i][k], dp[k+1][j]);
				if (dp[i][k] == dp[k+1][j]) cur_ans++;
				dp[i][j] = max(dp[i][j], cur_ans);
			}
		}
	}
	cout<<dp[0][n-1];
}

And here is the jury code (Java) for this problem :

import java.io.*;
import java.util.*;
public class two48 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("248.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("248.out")));
		int n = Integer.parseInt(br.readLine());
		int[] list = new int[n];
		for(int i = 0; i < n; i++) {
			list[i] = Integer.parseInt(br.readLine());
		}
		int[][] dp = new int[n][n];
		int ret = 0;
		for(int len = 1; len <= n; len++) {
			for(int i = 0; i + len <= n; i++) {
				int j = i+len-1;
				dp[i][j] = -1;
				if(len == 1) {
					dp[i][j] = list[i];
				}
				for(int k = i; k < j; k++) {
					if(dp[i][k] == dp[k+1][j] && dp[i][k] > 0) {
						dp[i][j] = Math.max(dp[i][j], dp[i][k] + 1);
					}
				}
				ret = Math.max(ret, dp[i][j]);
			}
		}
		pw.println(ret);
		pw.close();
	}
}

Now, I think I understand the jury idea for this problem (al least I think so, look pretty much the same as mine). But the is something that bugged me though ... In all of the accepted codes I've read of this problem, they always aim to get a maximum answer (a separate variable named ret in the jury code), while I'm trying to help an optimal answer by dp[0][N-1] (DP result of the whole array). There're some other difference like a small detail about how they calculate dp[i][j] though. I can't see the actual difference. Pls kindly point out where did I screw up ...

Well, I've been trying to solve this problem from USACO January Bronze Division. I think this is a LIS-related problem, so I tried using Dilworth's theorem. The thing is, even if I can calculate the length of the longest anti-chain according to the Cowphabet sequence (using binary search like any other LIS problem), I keep getting these annoying Wrong Answers ... Can you tell me where did a make a mistake ? I can't even figure out under what circumstance my approach would fail, but apparently it seem to be a false solution.

P/S : Yep, this problem can be solved using an O(N^2) approach, but I'm trying to do it with a O(NlogN) ... Anyway, help pls.

EDIT: Uh, and just to clarify, by LIS i mean Longest Increasing Subsequence.

What to do if you are stuck on a seemingly easy DP problem (or so I thought)

Well, I'm just doing some knapsack-DP problems and suddenly came to Problem 837D. At first I thought it's just a classic knapsack with some math stuff ... And here I'm writing this, so you know what happened. After I tried with the old type of transition (pick or left it) and still got test 1 wrong (the first test in the problem statement). I looked at the editorial and I think I got the recurrence formula (did I ?). Anyone can tell me why I keep on failing test 1. (Honestly I'm dying inside but pls help ..).

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 200, MaxP = 900;
int n, k;
ll dp[N][N][MaxP];

ll get2(ll x) { // get the number of 2s ...
	ll s = 0;
	while (x % 2 == 0) s++, x /= 2;
	return s;
}

ll get5(ll x) { // get the number of 5s ...
	ll s = 0;
	while (x % 5 == 0) s++, x /= 5; 
	return s;
}

int main () {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		ll x;
		scanf("%lld", &x);
		ll a = get2(x), b = get5(x);
		for (int j = 1; j <= min(i, k); j++) {
			for (int l = 0; l <= 900; l++) {
				dp[i][j][l] = max(dp[i][j][l], dp[i-1][j][l]);
				if (l-b >= 0)
					dp[i][j][l] = max(dp[i][j][l], dp[i-1][j-1][l-b]+a);
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		for (int l = 0; l <= 900; l++)
			ans = max(ans, min(1ll*l, dp[i][k][l]));
	printf("%lld", ans);
}

P/S : this is just for testing , obviously even if my code work well, it will not get AC due to memory limit ..., but I'm failing such simple test

Hi codeforces, recently I have came across an interesting problem : https://mirror.codeforces.com/problemset/problem/617/E. I had a rough time trying to understand the solution of this problem even after i read the tutorial. Basically I can't see why the add() and del() function work because of my lack of knowledges about the XOR operation. Now after a few hours of thinking, I have officially surrendered ... That's why I'm here, asking for an explanation.

P/S : I'm just dumb, especially when it come to math and other similar stuff. Pls don't be to harsh on me ... And just in case, I'm talking about the add() and del() function in the solution. You will find it in the editorial (of course)

Edit : Just in case, I can't seem to understand why adding cnt[favourite ^ v] help me count the number of pair i, j that satisfies l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k (favourite).

Recently I've came across an interesting DP problem.Here it is . This problem seem very hard to a newbie like me, because W (weight allowed of the bag) <= 10^9. So i came up with a solution (obviously wrong, that why I'm asking u guys ^_^) : I define a function f(i, j), which return the minimum weight we need to add to archive a j value (We will call this value dp[i][j]). I have 2 arrays : wt[i ... n] for weights and val[i ... n] for values (n <= 100). Finally I have ans = 0;(this is the answer of course); If wt[i] <= W (mean we can take only this item), I will have dp[i][j] = min(f(i-1, j), f(i-1, j-val[i])+wt[i]); So if at this point, dp[i][j] still <= W, I'll have ans = max(ans, j); If (wt[i] > W) (well mean I can't pick it) I will have dp[i][j] = f(i-1, j); return dp[i][j];

So my question : "Where did i screw up ???". I'm wrong, so how is this problem supposed to be solved ?? // Thank for taking your time reading this anyway, and if u can help, I'm always open to be corrected.

Recently, I've came across a DP problem. Problem 455A After a while I can't seem to think of any solution so i read the tutorial. Then i've totally lost. I can't understand how the solution work. Anyone can help me ?

P/s : And if you can explain me why could people come up with that solution ( I mean their thoughts process ), that would be a huge help. Anyway, help me pls. I'm stuck !!!

// If anything, forgive me for my bad english. I'm not a native speaker.