Links for the codes not working

Thank you very much for interesting problems and good tutorial!

Thank you! :)

In solution for A1, shouldn't there be just $$$O(n^2)$$$ ways to do the splitting because the third segment is completely defined by the first two? The time complexity of the algorithm would still be $$$O(n^3)$$$ though since string equality checking takes $$$O(n)$$$ time if I'm not mistaken.

Easier solution for A2:

If $$$s[1]=a$$$, then we can split it into $$$a=s[0], b=s[1], c=s[2...n-1]$$$.

If $$$s[1]=b$$$, then we can split it into $$$a=s[0], b=s[1....n-2], c=s[n-1]$$$.

Very cool bipartite idea, I couldn't find an elegant way to set up the graph for problem D. Also because it is bipartite it is easy to print the path because we know to skip every other element if I'm not mistaken?

Wait, so my bruteforce submission somehow eventually covered all possible cases?

A-F video editorial for Chinese

BiliBili

In problem D, why is output the distance divided by 2?

I didn't notice that the string consisted of only 'a' and 'b' in problem A and solved it for all letters. just realized it after seeing the editorial :')

E is a great problem. A 2000+ problem with a solution which can be implemented by any beginner is pretty hard to propose. I just completely didn't thought about that such easy solution could exist, and wrote an O(n*log(n)) solution using double linked-list and priority queue, which I failed to debug before the contest ended.

Share a solution for Problem C. First, n & x = x. Second, n became less from lowbit to highbit, and the value make n less is lowbit<<1, for example, n = 10101, x = 10100, lowbit is 1, n became 10100, m is 10100 + 10. However, here has a exception, n = 11010, x = 10000. After n bacame 10000, lowbit = 1000, m = 10000+10000 is illegal.

188746063

In problem F we could let $$$x=\lfloor \frac{p}{2} \rfloor$$$, $$$y=\lceil \frac{p}{2} \rceil$$$ at first, and after each step do $$$x = x-1$$$, $$$y = y+1$$$ until $$$xy<n$$$. Also if $$$x \neq y$$$ we need to consider the symmetric situation. Thus the complexity of each query will be $$$O(n^{1/4})$$$.

Also the official solution just said "you must optimize to $$$O(n)$$$". In fact the final array we get is the 4th convolution power of the array of partition number: $$$p=[1, 1, 2, 3, 5, 7, 11...]$$$ where $$$p[n] = \sum_{i \neq 0}(p[n+(-1)^{i}i(3i-1)/2])$$$ where $$$i$$$ iterate among all non-zero integers. We only need it's value up to $$$\sqrt{maxn}$$$, so we can calculate $$$p[n]$$$ in $$$O(maxn^{3/4})$$$ and calculate the convolution in $$$O(maxn)$$$.

Interesting to see the official solution for problem D. I solved it in a slightly different way, by making the vertices prime numbers and the edges the indices of the arrays. For each pair of prime factors of $$$a_i$$$, I added edge $$$i$$$. I ran a breadth first search, initializing the queue with all prime factors of $$$a_s$$$, running it until I hit edge $$$t$$$. Did anyone else do something similar?

How to solve C using binary search?

I don't understand how dp works to find number of ways to choose staircases in 4 corners of problem F, can anyone explain it clearer?

I can't understand editorial of F, in second para, what does 4 figures that form empty cells in the matrix mean? Where do they come from? And how staircase came into the picture?

Why it said "Code for Problem A", and "Code for Task C"?

How binary search works in problem C? Can someone explain in simple words please

D is nice tho, you have to use set to minimize the complexity of bfs through verticles

Problem E can also be solved with dp.Thanks to callmepandey for explaining this approach to me. For dp we will maintain 2 states.We will be maintaining the types of operations we have done and then at each index updating accoringly. Sample code.

Can anyone explain why (max_prefix — min_prefix) in problem E is working ?

Problem F can be solve in $$$O(n^{0.75}+Tn^{0.25})$$$.

We need to calculation $$$(\prod_{i\ge 1}(1-x^i))^{-4}$$$, which can be solved in $$$O(n^{0.75})$$$ by differentiating the function.

If the width of rectangle is $$$\sqrt n-x$$$, we can found that $$$x$$$ is at most $$$O(n^{0.25})$$$ because $$$(\sqrt n+x)(\sqrt n-x)=n-x^2$$$, it's easily to found that $$$x^2\le \sqrt n$$$.

So the problem can be solved in $$$O(n^{0.75}+Tn^{0.25})$$$.

I used DP for E, since I noticed that the last element $$$a_n$$$ must have exactly $$$a_n$$$ operations applied to it (since any more would just be redundant, if $$$a_n > 0$$$, there's no point in adding 1 to it since we can just choose not to include it in our subsequence)

So then I just apply this idea backwards, keeping track of the operations done so far (how many increases and decreases), and making sure to alternate increases to decreases when necessary. I don't like how messy my solution is though lol.

I have an $$$O(max_n + t n^{1/4})$$$ solution for pF.

A "good shape" can be viewed as a $$$h \times w$$$ square delete some "staircase" for each corner, consider calculate the number of "staircase" consist of $$$x$$$ blocks, which is equivalent to the number of non-decreasing sequence $$$s$$$ whose sum is $$$x$$$ and $$$s_1 > 0$$$, which can be further transform to a unbounded knapsack problem by seeing every object with weight $$$w$$$ as "adding $$$1$$$ to the last $$$w$$$ elements of $$$s$$$".

And here comes the interesting part, consider an $$$h \times w(h < w)$$$ square, we can't delete all element in one row/col, otherwise we can achieve lower perimeter of shape, so it means the calculation of "staircase" for each corner are independent! So after calculate the above dp in $$$O(max_n)$$$ ($$$\sqrt{max_n}$$$ different object weighted from $$$1$$$ to $$$\sqrt{max_n}$$$, max_sum_of_weight = $$$\sqrt{max_n}$$$), and let the final result be $$$cnt$$$, where $$$cnt_i$$$ means the number of "staircase" with $$$i$$$ blocks, then by independence, the number of combination of "staircase" for four corner is just $$$cnt^4$$$, which can be calculate naively in $$$O(max_n)$$$ since the size of $$$cnt$$$ is $$$O(sqrt(max_n))$$$.

Finally, for an $$$n$$$, enumerate all possible height and width of square, let say it is $$$h \times w$$$, then the answer for this square is $$$[x^{(h\times w-n)}]cnt^4$$$, and there are $$$O(n^{1/4})$$$ possible $$$(h, w)$$$.

So we can do it with $$$O(n)$$$ precompute and $$$O(n^{1/4})$$$ per query.

The difficulty of the solution of F can be optimized to $$$O(n+t\times \sqrt{\sqrt n})$$$,just by going through less (x,y) when answering each query.

One specific way can be seen in jiangly's solution.(Just where I find it hah :)

188759886 This submission passed during the contest. But now it gives MLE on test 130 which is one of the hack testcases. Still even after system testing this submission appears to be accepted in the standings. How???

Also, how can I correct the MLE verdict?

Alternate (and I believe simpler) solution for E: Link

We can just iterate over $$$i$$$, and maintain the minimum number of subsequences ending with a $$$+1$$$ element before the $$$i'th$$$ element, and minimum number of subsequences ending with a $$$-1$$$ element before $$$i$$$. For each $$$i$$$ greedily choose the subsequences that the $$$i'th$$$ element will be part of, and create new subsequences if required, such that $$$a[i]$$$ becomes equal to $$$0$$$.

Intuition: Just observe the 1st element, we can easily show that it if is negative, it will only be part of subsequences in which odd elements are positive, and vice versa if it is positive. Then just use some greedy ideas and induction.

I have no clue what the editorial is trying to say, but this problem should be 1500 rated tbh.

Can anyone tell me why this code is causing time limit exceeded?

#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;
int t, n, k, v;
int R[200020];
int P[200020];  // to value index.
int V[100010];
int main() {
    scanf("%d",&t);
    while (t) {
        t--;
        scanf("%d", &n);
        bool res = false;
        memset(R, 0, sizeof(R));
        memset(P, 0, sizeof(P));
        memset(V, -1, sizeof(V));
        for (int i = 0; i < n; i++) {
            scanf("%d", &k);
            bool hasincre = false;
            while (k--) {
                scanf("%d", &v); R[v]++;
                if (R[v] == 1) {
                    hasincre = true;
                    P[v] = i;
                    if (V[i] == -1) { V[i] = 1; }
                    else { V[i]++; }
                }
                else if (R[v] == 2) {
                    V[P[v]]--;
                    if (!V[P[v]]) {
                        res = true;
                    }
                }
            }
            if (!hasincre)
                res = true;
        }
        if (!res) {
            printf("No");
        }
        else {
            printf("Yes");
        }
        if (t > 0)
            printf("\n");
    }
    return 0;
}

we can also solve problem D using dijkstra and gcd function for filling in edges with their weights. code i dont know why my code isn't getting accepted though

In question B making an array of size N * K, isn't that like 10 ^ 10 space, and isn't maximum space allowed 10 ^ 10, then how does the solution still work, please correct me if I am wrong and guide me about what can be the maximum dimension of the array so that it won't give memory limit exceeded

i did same for b but it's giving tle what's the problem with my submission 241361102