Greeting,

I was trying to implement that algorithm but i don't know how to calculate F = (I — Q) ^ -1 part, I can not calculate the inverse of the matrix (because i also want to keep the proper fractions as it is)..

Any thoughts? (Or even a blog to read).

Hello guys,

I was trying to solve this task you can say for the last three hours.

I got the idea but idk why am i getting TLE at all, maybe cause of a big factor idk.

But this submission and this one are the same except of one single space in scanf, the question is would one space cause about 700ms OR this is not normal at all?

And you can compare between the two submissions to see the difference and to be exact #include and the space.

Also i know that it's not dp at all and i had to choose a better name, consider it length.

OK, Now i just copy pasted an AC solution already and changed to the same compiler and got TLE.

Can anyone explain how is this even possible?

I was trying to solve this problem but i am totally stuck.

I can use binary lifting to know the sum from node a to b i believe or walk specific number of moves but i can't just figure out how i will maintain that multiplication process.

I also faced other problems like this before but i couldn't solve any sadly so hope if someone can give me a hint, or explain any valid solution.

Similar problems like adding arithmetic progression to a specific range.

Hello guys..

I was trying to solve this task on SPOOJ but i am getting WA for some reason so hope if someone can help me..

The problem in-short asks you to find the count of prime number in specific interval which are also less than or equal to 1e7 after some modifications.

1. I just look for the primes until i reach 1e3, why? because i think if we are just looking for primes until 1e7 then we can check primes until square root of x only right? if it wasn't divisible by any prime then it's a prime number and i may be wrong...

2. After that i just build a segment tree with lazy propagation.

3. For propagation the count for specific interval with be either the length (rx — lx) or zero. depends if the new value will be a valid prime.

4. For a single point update i keep go down from the root until i reach to that point and it's count should be either 0 or 1.

5. Just calculate the count of sub-segment like any other segment tree, the count should refer to the number of valid items in my two halves.

I really don't know if this is a hard problem but it seems not and if my idea is correct then i believe my code has some bugs and i wish if someone can help since i am new to segment tree.

Here's my code and if it's not readable to you so i am sorry but i tried to make it look clean..

Gonna try to put the code here even though i never tried that before.

Thanks in advance.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int mxN = 1e5 + 5;
vector<int> primes;
int lazy[mxN * 4], a[mxN], n;
bool vis[mxN];

struct node {
	int val;
	int cnt;
} tree[mxN * 4];

bool is_prime(int x) {
	if(x == 1)
		return false;
	for(int p : primes)
		if(x % p == 0 && x != p)
			return false;
	return true;
}

void propagate(int x, int lx, int rx) {
	if(lazy[x] == -1)
		return;
	tree[x].val = lazy[x];
	tree[x].cnt = 0;
	if(lazy[x] <= 1e7 && is_prime(lazy[x]))
		tree[x].cnt = rx - lx;
	if(rx - lx == 1) {
		lazy[x] = -1;
		return;
	}
	lazy[2 * x + 1] = lazy[2 * x + 2] = lazy[x];
	lazy[x] = -1;
}

void build(int x = 0, int lx = 0, int rx = n) {
	if(rx - lx == 1) {
		tree[x].val = a[lx];
		if(a[lx] <= 1e7)
			tree[x].cnt = is_prime(a[lx]);
		return;
	}
	int mid = (lx + rx) / 2;
	build(2 * x + 1, lx, mid);
	build(2 * x + 2, mid, rx);
	tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}

void update_point(int node, int v, int x = 0, int lx = 0, int rx = n) {
	propagate(x, lx, rx);
	if(rx - lx == 1) {
		tree[x].val += v;
		tree[x].cnt = 0;
		if(tree[x].val <= 1e7 && is_prime(tree[x].val))
			tree[x].cnt = 1;
		return;
	}
	int mid = (lx + rx) / 2;
	if(node < mid)
		update_point(node, v, 2 * x + 1, lx, mid);
	else
		update_point(node, v, 2 * x + 2, mid, rx);
	tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}

void range_update(int l, int r, int v, int x = 0, int lx = 0, int rx = n) {
	propagate(x, lx, rx);
	if(lx >= l && rx <= r) {
		lazy[x] = v;
		propagate(x, lx, rx);
		return;
	}
	if(lx >= r || l >= rx)
		return;
	int mid = (lx + rx) / 2;
	range_update(l, r, v, 2 * x +1, lx, mid);
	range_update(l, r, v, 2 * x +2, mid, rx);
	tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}

int query(int l, int r, int x = 0, int lx = 0, int rx = n) {
	propagate(x, lx, rx);
	if(lx >= l && rx <= r)
		return tree[x].cnt;
	if(lx >= r || l >= rx)
		return 0;
	int mid = (lx + rx) / 2;
	int c1 = query(l, r, 2 * x + 1, lx, mid);
	int c2 = query(l, r, 2 * x +2, mid, rx);
	return c1 + c2;
}
 
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int q;
	cin >> n >> q;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	memset(lazy, -1, sizeof lazy);
	for(int i = 2; i <= 1e3; ++i) {
		if(vis[i])
			continue;
		primes.push_back(i);
		for(int j = i + i; j <= 1e3; j += i)
			vis[j] = true;
	}
	build();
	while(q--) {
		char c;
		cin >> c;
		if(c == 'A') {
			int v, pos;
			cin >> v >> pos;
			--pos;
			update_point(pos, v);
		}
		else if(c == 'R') {
			int v, l, r;
			cin >> v >> l >> r;
			--l;
			range_update(l, r, v);
		}
		else {
			int l, r;
			cin >> l >> r;
			--l;
			cout << query(l, r) << '\n';
		}
	}
}

Hello..

I was solving this problem And i am getting TLE on test 29 but not sure why?

i believe the only reason is using map< pair<int, int>, int> but still the complexity should be log n for insertion and finding the item or am i wrong?..

The code is simple just look for the middle point and add the count of it to answer but not sure if that's the reason.

If anyone can confirm the complexity of using map< pair<int, int>, int> would be nice.

Thanks in advance.

Can anyone tell me briefly what's the difference between ad-hock and greedy problems?

probably wrong : but i know that there are two types of greedy.

• One that can give you most optimal answer.

• Second one which can give you a correct answer but not necessary optimal.

Now is ad-hock considered to be the same as second type? i just don't know.

Thanks in advance.

Greeting,

I tried to solve this problem a year ago and i couldn't understand what's wrong with my submission and when i tried to solve it again now i couldn't get that edge case by my self again.

Can anyone tell me what's wrong with trying every possible segment with length k?

And i really tried the last submission was from 2019.

or maybe i didn't understand the problem correctly?

My submission. Thanks for your time.

The problem should be really simple, i just need to find the connected component and each node represent an index of the array the sort the value of all indices and put them in the correct position, do the same for each component.

But i am getting WA test 16 for unknown reason i even checked all the small test cases and my code passed so hopefully someone can help..

Problem link : Here. Solution link : Here.

Thanks in advance.

i am getting WA test 6. Here is the Problem. Here is also my submission.. it should be a simple problem but i don't know why am i getting wrong answer. my approach for maximum isolated nodes is to make a fully connected graph with k nodes that will take all of the m edges.

Hello guys.. i read the tutorial and the comments and i can't get it sadly so far.. so if anyone can give me a hint for this problem Magic Formula gonna be grateful too much. The thing that i can't get in the tutorial is the flipping of (i % 1) ^ (i % 2) ^ ..... (i % n) to (1 % i) ^ (2 % i) ^ ..... (3 % i) ... (n % i).. and WHY would he do so.. Thanks in advance.

Is it possible to do prime factorization for (A + B) before doing the summation? I mean lets suppose that we want to prime factorize A^n + B^n and 1 <= A, B, N <= 1e12 .... how can i do so? or it's impossible and it's a stupid question?..