Given two arrays of integers $$$x$$$ and $$$y$$$, of length $$$n$$$, find a partition of indices $$${1, \ldots, n}$$$ such that you minimise the score, where the score of a partition $$$S_1, S_2$$$ is defined as $$$\max(\sum \limits_{j \in S_1} x[j], \sum \limits_{j \in S_2} y[j])$$$

just find the minimum score that can be achieved, I fancy a dp approach, any help is appreciated, thanks

EDIT : assume the sums of $$$x$$$ and $$$y$$$ are bounded above by $$$M$$$, then a solution with time complexity parametrised by $$$M$$$ might be good

Submission : https://codeforces.com/contest/1878/submission/252116337

I am new to python so I was practicing it on codeforces problems, the submission I referenced above is exceeding memory limits for very small values of $$$n$$$.

I think you don't need to really understand the problem statement, I suspect the problem is in implementation of segment tree. (as the solve() function really only has binary search which is implemented iteratively)

Any help will be appreciated

here is the code :

tree=[0 for i in range(4*n)]
build_tree(1, a, tree, 0, n-1)

q=int(input())
for j in range(q):
    l, k=map(int, input().strip().split())
    l-=1

    left=l
    right=n-1
    while right-left>1:
        mid=(left+right)//2
        if query(1, tree, 0, n-1, l, mid) >= k:
            left=mid
        else:
            right=mid-1
    # right<=left+1
    r=l
    if right==left+1 and query(1, tree, 0, n-1, l, right) >= k:
        r=right
    else:
        r=left

    if query(1, tree, 0, n-1, l, r) < k:
        print(-1, end=' ')
    else:
        print(r+1, end=' ')
print()
return

Problem Link : https://codeforces.com/problemset/problem/1912/K

My approach : Reduce all the numbers mod 2 and then work with the following,

$$$dp[i][xy] = $$$ # subsequences in $$$a_1 \ldots a_i$$$ with consecutive sum of 3 is divisible by 2 which ends with $$$x, y$$$.

$$$dp[i][xy] = $$$ if $$$y = a_i$$$ then $$$ dp[i-1][xy] $$$ (not choose $$$a_i$$$) + $$$dp[i-1][zx]$$$ (choose $$$a_i$$$) ($$$z$$$ here is $$$(x+y) \textrm{mod} 2)$$$ ; else $$$ dp[i-1][xy] $$$

Base case $$$dp[2][a_1 a_2] = 1$$$ (others are initialised to 0)

But I'm not really getting correct answer with this approach, I can't really see why this is wrong. Any help is appreciated

I know the contest problems are written by the community members themselves, how can I propose problem for an official codeforces contest or be a tester of one, is there a rating requirement for this or something like that ?

Problem Statement : https://www.codechef.com/problems/QCHEF?tab=statement

I was practicing MO's algorithm and encountered this question, but I am getting TLE here is my submission : https://www.codechef.com/viewsolution/1036034418

I'll explain my approach here : So for every range $$$[L, R]$$$ you need to answer the query asked in question i.e. $$$\mathrm{max} { |x-y| | L \leq x, y \leq R \; \mathrm{and} \; A_x = A_y }$$$

Since all the values are bounded above by $$$M$$$, I could use MO's algorithm to solve this problem by maintaining current max difference corresponding to each distinct value present in current range

In other words, I could maintain an array $$$T$$$, where $$$T[x]$$$ stores current range's max difference value corresponding to value $$$x$$$.

It is easy to maintain this array as you're adding or removing elements from the range, if you add an element say $$$A[idx]$$$, you simply update $$$T[A[idx]]$$$, say you're adding it from the left, then you need to find the rightmost index in the range whose value is also $$$A[idx]$$$. You can realise this easily using binary search by storing indices of each value occurring in array in increasing order.

Similarly, you can handle the cases where an element is removed

Since, I need max of this array $$$T$$$ after every query, I am using a segment tree to do that.

Time complexity of solution is $$$O((N+K)\sqrt{N} \log M)$$$, because each add/remove/get_answer methods from MO's algorithm takes $$$O(\log M)$$$ time (binary search, segtree update, segtree query)

Any help would be greatly appreciated, Thanks

I was practicing randomised algorithm problems and I stumbled across this nice problem : https://codeforces.com/contest/364/problem/D

My approach to this problem is as follows : Let $$$g$$$ be the ghd of the input, then prob($$$g | a_i$$$) = 1/2 (where $$$a_i$$$ is random number from the input) thus with 1/2 probability $$$g$$$ is divisor of $$$a_i$$$, so divisors of $$$a_i$$$ can be good candidate for $$$g$$$

So my algorithm is repeat 20 times : take random number $$$a_i$$$ from the input array, compute its divisors iterate over its divisors list, and for each divisor $$$d$$$ of $$$a_i$$$, compute number of $$$a_j$$$ such that $$$d | a_j$$$, if it is $$$\geq \frac{n}{2}$$$ then $$$d$$$ is candidate $$$g$$$

Probability I don't get correct answer = probability in none of the 20 trails I get the correct $$$a_i$$$ = $$$1/2^{20}$$$ approx $$$10^{-6}$$$

Time complexity of the solution is : $$$O((n d + \sqrt{A})m)$$$ ,where $$$m$$$ is number of trails, $$$A = \textrm{max} a_i$$$, and $$$d$$$ is max number of divisors (which is typically very small and grows logarithmically)

Here is my submission link : https://codeforces.com/contest/364/submission/237431910

I am getting TLE, what can be the problem ?

UPDATE : I did some optimizations, and passed the 3rd test-case now I am stuck at 4th These two test cases are very similar I don't know why there is this problem

updated submission : https://codeforces.com/contest/364/submission/237449074

I just learned about Mo's algorithm and went to solve some problems.

here is the problem link where I'm stuck : https://www.spoj.com/problems/DQUERY/

I used the standard implementation of Mo's algorithm from cp-algorithms here : https://cp-algorithms.com/data_structures/sqrt_decomposition.html

My solution is giving TLE (I'm pasting my code here)

map<int, int> mp;
vector<int> a;
int sz;
class Query {
public:
	int l, r, idx;

	bool operator<(const Query &other) {
		return make_pair(this->l/sz, this->r) < make_pair(other.l/sz, other.r);
	}
};
inline void remove(int idx) {
	int x=a[idx];
	mp[x]-=1;
	if (mp[x]==0) mp.erase(x);
}
inline void add(int idx) {
	mp[a[idx]]+=1;
}
inline int get_answer() {
	return mp.size();
}

void solve() {
	int n;cin>>n;
	a.assign(n, 0);
	for(int i=0;i<n;i++) cin>>a[i];
	sz=(int)ceil(sqrt(n));
	int q;cin>>q;
	vector<Query> queries;
	for(int j=0;j<q;j++) {
		int l, r;cin>>l>>r;
		--l, --r;
		queries.push_back({l, r, j});
	}
        // Mo's algorithm
	vector<int> answer(q);
	sort(queries.begin(), queries.end());
	int curl=0, curr=-1;
	for(Query query : queries) {
		while (curl>query.l) {
			curl--;
			add(curl);
		}
		while (curr<query.r) {
			curr++;
			add(curr);
		}
		while (curl<query.l) {
			remove(curl);
			curl++;
		}
		while (curr>query.r) {
			remove(curr);
			curr--;
		}
		answer[query.idx]=get_answer();
	}
	for(int ans : answer) cout<<ans<<endl;
}

int main() {
	solve();
}

How fast can we do gaussian elimination over $$$\mathbb{Z}/2\mathbb{Z}$$$ ?

I know the usual time complexity of gaussian elimination over reals is $$$O(n^3)$$$ which is horrible, but can we do very fast over $$$\mathbb{Z}/2\mathbb{Z}$$$ ?

Any references would be nice if there are such techniques, I searched the internet but couldn't find my answer

Can someone explain how to solve Required Substring problem in CSES : https://cses.fi/problemset/task/1112

Your task is to calculate the number of strings of length n having a given pattern of length m as their substring. All strings consist of characters A–Z.

My approach :

I was thinking of some dp approach and instead of counting the required quantity directly, I'd count the complement and subtract from $$$26^n$$$

But, I am stuck with this approach, I thought of the following recursion

$$$dp(i, j) = # of strings of length i not containing s, whose suffix of length i is a prefix of s (i.e. s_1\ldots s_j)$$$

$$$dp(i, j) = \sum_{j'\in S} dp(i-1, j') + dp(i-1, j-1)$$$, where $$$S$$$ = set of all $$$j'$$$ such that $$$s_1 \ldots s_{j'}$$$ has a prefix of length $$$j-1$$$ which is also its suffix

and then finally compute : $$$dp(i) = 26*dp(i-1)-dp(i-1,m-1)$$$ (supposed to count strings of length i not containing s)

but I cannot figure out how to instantiate the base case $$$dp(i, 0)$$$ for $$$i > m$$$ or $$$dp(i, 1)$$$

Any help is appreciated, thank you