Hi, I was just working on this problem, and I noticed that when I changed my operations from division to addition, it resulted in a huge time difference. With division, my code TLEs, while with addition, my code runs in 400ms (you can see where I changed the code on lines 136 and 142). Division is a more costly operation than addition, but why is it causing such a big difference in runtime? Should we avoid more costly operations to prevent TLE?

Today, I tried logging into my account in Google Chrome, but I can't because I cannot press the login button. When I press it, nothing happens. I then tried it in firefox, and now it is working. Is anyone having the same issue?

UPD: I tried again in google chrome and it looks like sometimes, when I press login, nothing happens, and sometimes, it just shows a 403 forbidden error. the login also works in safari

UPD2: MikeMirzayanov

Hi, I am trying to check if an array (consisting of the numbers from 1 to N, where N is the length of the array) is a permutation of N elements using hashing. My idea is to assign a randomized value as a hash for each value between 1 and N. The hash value of an array would be them sum of these individual hashes, and I compare this sum to the sum of the hashes for a permutation of length N.

I am wondering, what is the probability of collisions using this type of hashing? I couldn't find much online other than the probability for rolling hashes. Thank you!

In this problem, we are asked to partition an array into two arrays A and B, and maximize seg(A) + seg(B), where seg(array) is the number of occurrences of i such that a[i] != a[i-1], plus 1. It is also the number of segments of the array, where each element on the segment has the same value, and the segment cannot be made larger. So for an array like 1,1,2,2,3,1 the "seg" value of the array is 4.

My approach for this is as follows: Since the original array is composed of these segments as well, we can look at each segment separately. For each segment, I think we can just let the first element of the segment be part of array A, and the rest to be part of array B. Then, we just calculate seg(A) and seg(B) and add them to get the result.

My logic for why this works is that if we change this construction by moving one element of array A to array B, the answer won't change. Let's say, for example, the original array looks like this:

a,a,...,a,a,b,b,b,..,b,b,b,c,c,c,...,c,c,c, where a, b, c are some random integers.

According to our construction,
A = a,b,c.
B = a,a,a, ...,a,b,b,...,b,c,c,c, ...,c.

If we move an element from B to A, then A just gets one more of a,b, or c and the answer is still the same. If we move an element from A to B, the same thing happens.

I am pretty convinced that my approach is correct, but my approach doesn't work for test case 6 of this problem (you can view my submission here). Does anyone know an example or reason why my logic fails? Thank you!

I have been thinking about the following problem lately: we are given a tree (rooted at vertex 1) and an array. We want to answer some queries. In each query, we are given a vertex v and two indices L and R, and we want to output the "YES" or "NO". The answer is "YES" if on the subarray from L to R, there exists a vertex u such that v belongs to the subtree of u.

I could think of a solution with quadratic time complexity (loop from L to R and check if u exists), which is not efficient.

Another thought I had was to maintain two arrays tin and tout, which store the time when we process the vertex and when we finish processing the vertex. Then, we just need to check if there exists u on the subsegment such that tin[u] <= tin[v] and tout[u] >= tout[v], but I haven't thought of how to get solution from this.

Do you have idea how to solve this? Thanks!

Hi, I'm trying to solve a problem I just gave myself using lazy propagation and segment tree. Essentially, we have some queries on an array, where each query consists of two integers $$$L$$$ and $$$R$$$, and we are supposed to update the array by multiplying each element in the range by $$$2$$$, and then adding $$$1$$$ to every element. Every element a[i] within the range becomes 2 * a[i] + 1. For each query, we just print the sum of all elements.

Let N be the number of elements, A be the array.

So, for this test case:

N = 5. A = {1, 2, 3, 4, 5}. 1 Query: [L, R] = [1, 2]

The answer should be 20, but my code prints 19.

Here is my attempt:

int N;
vi t, a, laz1, laz2;
// laz1 stores the aggregate of the multiplications
// laz2 stores the aggregate the additions

void build(int u, int l, int r) {
    if (l == r) {
        t[u] = a[l];
    } else {
        int mid = (l + r)/2;
        build(2 * u, l, mid);
        build(2 * u + 1, mid+1, r);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void addd(int u) { // lazy propagation for additions
    laz2[2 * u] += laz2[u];
    laz2[2 * u + 1] += laz2[u];
    t[2 * u] += laz2[u];
    t[2 * u + 1] += laz2[u];
    laz2[u] = 0;
}

void multiply(int u) { // lazy propagation for multiplication
    laz1[2 * u] *= laz1[u];
    laz1[2 * u + 1] *= laz1[u];
    t[2 * u] *= laz1[u];
    t[2 * u + 1] *= laz1[u];
    laz1[u] = 1;
}

void mult(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] *= val;
        laz1[u] *= val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        mult(2 * u, tl, mid, l, min(mid, r), val);
        mult(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void add(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] += val;
        laz2[u] += val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        add(2 * u, tl, mid, l, min(mid, r), val);
        add(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

int main() { 
    setIO("");
    cin >> N;
    t.rsz(4 * N, 0), a.rsz(N), laz1.rsz(4 * N, 1), laz2.rsz(4 * N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    build(1, 0, N-1);
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        mult(1, 0, N-1, l, r, 2);
        add(1, 0, N-1, l, r, 1);
        cout << t[1] << endl;
    }
}

I split up each query into two updates: multiplying everything in the range by 2 and then adding by 1.

It seems that I am propagating correctly, why am I getting the wrong answer? Thank you in advance!

Hi, I'm trying to find an algorithm to answer queries to find the most frequent element in a subsegment of an array. I've read this post on StackOverflow, which mentions a method to get $$$O(\sqrt{N})$$$ per query: https://stackoverflow.com/questions/40302407/how-to-find-the-most-frequent-number-and-its-frequency-in-an-array-in-range-l-r.

Basically, the author of the answer says that we can choose a value $$$B = C \cdot \sqrt{N}$$$, and then handle the queries on the subsegment $$$(L, R)$$$ with casework: Case 1. If $$$R - L + 1 < 2 \cdot B$$$, then just loop through every value between $$$L$$$ and $$$R$$$ and take maximum of all frequencies. Case 2. If $$$R - L + 1 \geq 2 \cdot B$$$, then loop through all elements of the array that are "heavy" (aka they appear more than $$$B$$$ times in the entire array) and take the maximum of their frequencies over the interval.

I can see why this approach will work, but I tried using it on this problem and it got WA. I follow basically the same idea in the editorial. I find the rightmost k and the leftmost k occurrences, and then find the mode on the subsegment of the array in between (using the algorithm described). Here is my code.

Not only does my code get WA, but if I change the value of $$$B$$$ I actually pass different amounts of test cases. With the value of $$$B = 3 \sqrt {N}$$$, I can pass the first 14. If I change this to $$$2 \sqrt{N}$$$, then I can only pass the first 7.

Is there some problem with the approach described in the StackOverflow post or is it because of some other error in my code? Your help is greatly appreciated!

Hi, I wrote this code, which basically follows the same idea as in the editorial, but I'm not sure how my code is getting WA on test case 5.

My approach is divided in two steps. The first step is to find the numbers that we can use to assign for the edges. I put these values in the array "factos." I split the input into two cases: either there are less than or equal to N-1 prime factors or there are more than N-1 prime factors. In the first case, all of the prime factors given in the input can be assigned to the edges, and for any leftover edges we can assign them a weight of 1. In the second case, we can reduce the number of prime factors by multiplying the N-M+2 greatest prime factors together, merging them into one composite number.

The second step is to find the distribution index. Using a DFS, I found the product of the number of vertices in the first component and the number of vertices in the second component (denote this as w[i]), when edge i is removed from the tree. Since this is equal to the number of distinct paths that pass through the removed edge, I multiply this amount with one of the numbers in the vector "factos", always multiplying larger values of w[i] with larger values of "factos" to get the answer.

I've read the solution several times and double checked my method and I can't seem to understand why my code gives wrong answer. My approach seems to be the same as the solution presented in the editorial. Could someone please help explain? Thank you!

Hi, I am working on 1530D and I'm not sure why this code gets TLE on test case 4. I've calculated the time complexity several times, and it looks like O(NLogN) (there is a nested loop but it only goes through N iterations in total, and in each iteration we do an O(logN) binary search). I've also tried fast I/O, but that didn't work. Does anybody know why this code is getting TLE? Thank you!

Hi, I'm working on problem 296C and I am trying to solve it using a BIT. However, I keep getting WA on test 11. I've tried my own test cases but could not find the problem in my code. Here is my submission: 211297450. Could someone help me find it? Thank you!

I was working on the problem 1371D — Grid-00100 and I submitted this code: 206708949. For some reason, Codeforces said that my code had an "out of bounds" error on line 79. I'm not sure why this error occurred, because my matrix indices are clearly within bounds. Additionally, on test case 8 of test 2, the checker comment was "wrong answer Integer -1849096384 violates the range [0, 18] (test case 8)", but I tested test case 8 locally and got the correct answer. Does anyone know why this could be happening? Your help is appreciated!

I recently read that you could improve the performance of the Dijkstra algorithm by getting rid of pairs and doing comparison operator overloading (https://cp-algorithms.com/graph/dijkstra_sparse.html#getting-rid-of-pairs)

Does anyone have this implementation?