Why editorial for D1C in Russian?

How is it written 2weeks ago?

1322B — Подарок придумал Tudor Costin & Oncescu Costin, а подготовил Tudor Costin

http://info1cup.com/files/Xorsum-editorial.pdf

Div1.D reminds me 2048.

can anyone explain div2 D problem

How can I split the vertices with same neighboring set in div1 C? I tired hashing with mod 1000000009 and add vertices with same hash values, but got WA at main test 88 :(

Is the time limit of Div1B set according to $$$O(n \log n \log C)$$$ solution? My submission 72640450 runs 2979ms, which is very close to get TLE.

I will try to provide some intuition to the solution of Div1 C.

Look at the image below, each node in the left half of the graph is drawn as a cricle (denoting a set, not the problem's defined set, but a new set we're going to define). The numbers in the rectangles are the ID's of the nodes and the characters are the elements included in the node's set. These set elements (the characters) represent sum of node values of the right half of the graph.

For example, if $$$S = \{ 0 \}$$$ then $$$F(S) = a + b + c + d$$$. if $$$S = \{0, 2\}$$$ then $$$F(S) = a + b + c + d + f + g$$$. Note that each character in picture may denote more than one node in the right half of the original graph.

Now assume you've computed the gcd of all intersections of sets like the editorial have mentioned in the first paragraph. In the image below this will mean you've computed $$$gcd(a, g, e, d + c, b + c, c + f, c) = m$$$

You will observe that if you union any number of sets now, the summation will (hopefully) be multiple of $$$m$$$. For example if $$$S = \{0, 1\}$$$ then $$$F(S) = a + b + c + d + e + f$$$, or if $$$S = \{0, 1, 2\}$$$ then $$$F(S) = a + b + c + d + e + f + g$$$. You will find that each term in the summation is a multiple of $$$m$$$.

I'm not sure how to prove this formally (if someone can formalize all this trash, it would be appreciated!), but I wanted to show some intuition on how one would approach such problem.

It's my code:https://codeforces.net/contest/1323/submission/72668413

I just use the loop. esay,but of course TLE.So, I have some trouble.

I do not really understand the editorial.

And, what should I do to improve my code.

please help me, thanks!

If the intended solution was O(nlognlog(1e7)) for div 1 B, where can I reduce the constant factor in my code. I am not very experienced in optimizations so any help is appreciated.

Completely different solution to D1E:

1. Prove that if $$$a_i$$$ doesn't change at some moment of time, then it will never change anymore.
2. Assume that $$$a_{i-1} < a_i > a_{i+1}$$$. Prove that each odd-indexed change to $$$a_i$$$ will decrease the number, and each even-indexed change will increase it. (A symmetric claim works if $$$a_{i-1} > a_i < a_{i+1}$$$.)
3. If $$$a_i$$$ decreased in the first step and increased in the second step, each of the values $$$a_{i-1}, a_{i+1}$$$ must have increased in the first step. So if $$$a_i$$$ changes at least twice, $$$a_{i-2} > a_{i-1} < a_i > a_{i+1} < a_{i+2}$$$ must hold. (Similar claim follows for any number of changes).
4. Assume that $$$a_{i-1} < a_i > a_{i+1}$$$. Prove that the value of $$$a_i$$$ after $$$k$$$ changes is equal to $$$\max(a_{i-k}, a_{i-k+2}, a_{i-k+4}, \dots, a_{i+k})$$$ if $$$k$$$ is odd, and $$$\min(\text{same stuff})$$$ if $$$k$$$ is even. (For $$$a_{i-1} > a_i < a_{i+1}$$$, $$$\max$$$ and $$$\min$$$ are swapped.)
5. Therefore, $$$a_i$$$ changes at least $$$k$$$ times if each $$$a_{i-1}, a_{i+1}$$$ changes at least $$$k-1$$$ times and after $$$k-1$$$ operations, $$$a'_i$$$ is not the median of $$${a'_{i-1}, a'_i, a'_{i+1}}$$$.
6. In particular, if $$$a_i$$$ changes exactly $$$k$$$ times, then $$$a_{i+1}$$$ will change exactly $$$k-1$$$, $$$k$$$ or $$$k+1$$$ times.
7. Then, for each $$$a_i$$$ we will compute how many times this value changes. Obviously, $$$a_1$$$ changes 0 times. For each following $$$a_i$$$, we have three options on the number of times $$$k$$$ that $$$a_i$$$ will change. We can check if $$$a_i$$$ will change, by computing $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$ after $$$k-1$$$ operations using simple RMQ (we need 4 RMQ instances for computing min/max on odd/even-indexed values) and checking if $$$a_i$$$ is not the median of these three values.
8. After we compute these values, the rest is easy: we know maximum number of times the sequence will change, and we can restore the final sequence using the formulas in (4).

Not everything in here is sound, but it's possible to write down and analyze all formulas and find out everything should be OK with this solution.

Total runtime is $$$O(n + \text{RMQBuild} + n \cdot \text{RMQQuery})$$$. When RMQ is implemented using a sparse table or a segment tree, we end up with a very fast $$$O(n \log n)$$$ solution: 72662345. Using the optimal RMQ, we can solve the problem in $$$O(n)$$$ time.

Can someone walk me through the complexity of D2 B of the editorial. I thought it will led to TLE but it didn't.

What was the intended complexity of div2B? I can see so many solutions running in about sqrt(k)*(n+m). Shouldn't that TLE?

I had come up with something similar too early in the contest but didn't submit because I thought it will TLE :/. Ended up submitting an optimisation of the same, which runs in somewhat similar complexity.

In D you can also be an idiot, not reverse the sequence, and barely pass in 1980ms like this: 72679047. The complexity is $$$\mathcal{O}(nm \log m)$$$, were you trying to cut solutions like this?

I didn't quite get the editorial of Div.1A, can someone please explain it to me?

Can someone please explain their intuition and code behind Div2D/Div1B? The tutorial doesn't help me much.

For Div2D / Div1B, I think people counted in a different way as editorial, the number of pairs which have k'th bit set in their sum. Can someone share a better approach?

Is this solution (72639972) to div2B hackable? It's $$$O(n \cdot numDivisors(k))$$$, which might be a bit slow with standard Java HashMaps

Update: This is my hack attempt generator: https://pastebin.com/2wyjDVMB . Local testing seems to indicate that my solution should still pass with it though (about 70ms, excluding input and startup overhead). Maybe excluding out-of-bounds divisor pairs sped it up enough to be unnoticeable with these input constraints, or even improve the big-O bound.

Update 2: Yep, was unsuccessful. Thanks anyway

For div1 B,if you use two pointers and radix sort.Then it will be n log C.

For div1 B,you can use two pointers and radix sort,then the time complexity will be n log C.

I think the time limit for Div2D is quite tight, I had a O(nlogc*logc) solution using Fenwick Tree but got a TLE

Can someone explain div1D because I can't get much of what the editorial is saying?

why 1323 B , gb[k/i] is not giving runtime , i applied same logic but got runtime at tc 5 ... Please someone clarify

Где можно посмотреть разбор на русском?

for question B, Count subrectangles : plz can somebody tell me why following code in giving wrong answer in test case 7??

include <bits/stdc++.h>

define int long long int

using namespace std;

int max(int a,int b) { return a>b?a:b; }

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //cout<<"I must do it...Yeahhh";

int t=1;
//cin>>t;
while(t--)
{
    int n,m,k;
    cin>>n>>m>>k;

    int a[n],b[m];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i]; 

    int x=0,ans=0;
    vector<int>va,vb;

    vector<int>check;
    for(int i=1;i<=sqrt(k);i++)
        if(k%i==0)
            check.push_back(i);

    x=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]==1)
            x++;
        else if(a[i]==0 && a[i-1]==1)
        {
            va.push_back(x);
            x=0;
        }
        else
            x=0;
    }
    if(a[n-1]==1)
        va.push_back(x);
    /*for(int i=0;i<va.size();i++)
        cout<<va[i]<<' ';*/
    //cout<<'\n';
    x=b[0];
    for(int i=1;i<m;i++)
    {
        if(b[i]==1)
            x++;
        else if(b[i]==0 && b[i-1]==1)
        {
            vb.push_back(x);
            x=0;
        }
        else
            x=0;
    }
    if(b[n-1]==1)
        vb.push_back(x);
    /*for(int i=0;i<vb.size();i++)
        cout<<vb[i]<<' ';
    cout<<'\n'<<va.size()<<' '<<vb.size();*/
    for(int i=0;i<check.size();i++)
    {
        int x=check[i];
        int y=k/check[i];

        for(int j=0;j<va.size();j++)
        {
            for(int k=0;k<vb.size();k++)
            {
                if(k<=va[j]*vb[k])
                {
                    if(y==x)
                    {
                        ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
                    }
                    else
                    {
                        ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
                        ans+=(max(va[j]-y+1,0) * max(vb[k]-x+1,0));
                    }
                }
            }
        }
    }
    cout<<ans;
}
return 0;

}

Thanks in advance

Bonus of 1322B:

What's the $$$O(n)$$$ solution for E?

For Div1 B, 72638208 doesn't check the sum to fall in two ranges and just uses one pass instead of four passes. Anybody know why?

Can anyone explain Div1D. I have no idea what the editorial is saying.

After reshuffling 2 segments of total length 8, we can get a right bracketed sequence:()()((()())

it isn't right bracketed.

Can anybody explain how to use two pointers method in Div2 D?

Is editorial's proof of Div1C(Instant Noodles) correct on this test?

3 6   //n, m
1 3 5
1 1
1 3
2 1
2 2
3 2
3 3

Anyone know how to solve div1 B in Nlog(C)??

I have been trying to understand the editorial for Div.1 D for a whole day, but I still can't get it.

Now I have a question about the problem description:

"The show host reviewes applications of all candidates from $$$i=1$$$ to $$$i=n$$$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $$$i$$$ is strictly higher than that of any already accepted candidates, then the candidate $$$i$$$ will definitely be rejected."

Does it mean we should first choose the set of participants to accept which $$$l_i$$$ is non-ascending then let them do the show and fight against each other? If a participant was defeated, is it still regarded as "already accepted"?

In the tag of div2 B problem, it is showing binary search as a tag, but there is no use of it in problem, why it is so?

I wrote a more detailed editorial of 1332E — Instant Noodles I wanted to write it down so that I could understand it more.

https://gist.github.com/mightymercado/9f281177bcb9d39b7d55ff4a9ab29f4d

why does this tle for count rectangles submission, i have basically the exact same thing as editorial said

I took part in the competition in Moscow and now I wanna ask you — is there a place where I can read tutorial like this here but about the other two problems (“Double palindrome” and “Latin Square”), that weren’t included here in this Codeforces round. It’ll be great if I can also practice them somewhere. I’ll be very grateful if somebody helps me :).

nobody used stack for div1 A 1322A - Unusual Competitions ?

Implementation of ques C-Unusual Competition using Stack, storing position of unbalanced braces. https://codeforces.net/contest/1323/submission/97906786

why count subsequences problem have binary search tag??