Lighting fast editorial!

I felt, a huge difference in the difficulty of problems D and E.

One zero should be enough in C right? Since $$$0+0+a = a$$$ which is in the array.

Another speedforces round but problems were good, enjoyed solving them

it's very cool that you can solve every problem in python. Respect to the authors!

Thanks for the fast editorial!!!

162104309 This is my python solution for D. It almost same with the c++ implementation.

I am quite new to problems like D. Can someone give me some tips on this type of question where you have to constantly take input and print . And if possible please share some questions to practice as well . Thank you in advance:)

How did a lot of people solve problem D? It looks very tricky to me.

My solution for problem d on my machine does n't printing zero but it says that i am printing zero when i submit my code 162169758

Can anyone tell me what's the difference between cout.flush(); and fflush(stdout); ?

Used fflush(stdout); 162169561 : Idleness limit exceeded

Used cout.flush(); 162169654 : Accepted

Used fflush(stdout); removed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);162169729 : Accepted

I know we can simply use endl; but what's the difference between these two ?

It was a great Contest!! Solved Interactive for the very first time.

I didn't got the first claim of problem E that strength required is max ai-bi.Suppose a={5,1,2,3,4} b={1,2,3,4,5} still if s=1 a can be converted to b by these operations swap(a1,a2) swap(a2,a3) swap(a3,a4) swap(a4,a5),,then how is the claim true??

Good problems, thanks for fast editorial

I don't think you need sortings for E, making its complexity linear. For the last part, we can just take whatever is left as long as it is at least a[i]-s. We just need to do it in a decreasing order in a[i].

flamestorm The time complexity for problem D is O(n + logn), not O(nlogn). You do only one binary search per test case, and the sum of lengths of all queried subarrays is at most n.

Best Contest for me till date!! Great Tasks and Great Rating Changes as well. Thanks flamestorm and ScarletS

Non-mathy interpretation for G:

First of all treat the corner case of the string having only one 1.

Let's use the string in the leftmost position possible. It's easy to prove that the best answer will have an operation there. Now, while there are more than 2 set positions, let's erase the second leftmost position that has some 1. To do that, just align the leftmost 1 from s with that position. I'll leave the proof of why that gives us the best answer as an exercise to the reader.

Obviously we can't do that because it'd be too slow. Then the solution is just realizing that that process can be rewritten as matrix multiplication mod 2, the idea is that after doing the first operation, we keep a window of bits just to the right of the first set bit and slide it to the right, erasing the first position with an operation if it is 1. After realizing that, we can simply use the Baby-step Giant-step algorithm to find the first occurrence of our target 100000000...

If you want another similar problem here's some problem from 2009 ICPC Brazilian Regionals. The statement is in portuguese and I don't know if it's translated somewhere, sorry for that.

Good C, it took me about 1 hour to guess the hidden conclusion :(

Well,Here is my solution for problem E works in O(n) time
code
Consider to arrange a p[i] for each a[i] which satisfies

1. $$$a[p[i]] - i <= s$$$

2. for each b[i] is not -1 , $$$p[b[i]] = i$$$

Then we make b[p[i]] = i
It can be prove in the same way as the officical solution that it's the sufficient and necessary condition for making such a valid b.

So the answer is ways to arrange p[i].
Firstly if an x is valid to be set as p[i],it must be valid to be set as p[i+1].
So arrange p[i] from 1 to n.
if p[i] is arranged by condition 2, we ignore it.
else we count all the ways $$$all$$$ to arrange p[i] and mutiply our answer.
$$$all$$$ can be calculated during the implementation.

Why the same code about D,in GNU C++20 (64) will getTime limit exceeded on test 1,in GNU C++17 can get accept.

in GNU C++17 162184565 Time limit exceeded on test 1 and in GNU C++20 (64) 162184380 Accepted

Problem F How to prove that those conditions mentioned in the solution are sufficient to determine if a can be turned into b ?

Well, I think the complexity of the solution D is $$$O(n)$$$ rather than $$$O(n \log n)$$$. For the binary search here, the complexity is $$$\sum_i{n/2^i}$$$ which equals to $$$O(n)$$$ not $$$O(n\log n)$$$

plus: The solution is fixed now.

In the Rising Sand problem, if we take an array [2,2,2] as input and k=2, we can make it too tall by alternating increasing one of adjacent piles one at a time. 2 2 2 k=2, 2 3 3 -we take 2nd and 3rd element and perform operation, 3 4 3 -we take 1st and 2nd element and perform operation

This is the best contest ever I've witnessed on codeforces, solving till D in a div 2 is something superb!! and it's my first time managing to do this!! Hats off for you guys! Please make lots of divs2 like this one.

Thank you for the great round.

I went from only solving div. 4A to solving div. 2ABCD over the past two months; hopefully other fellow newbies can see similar improvements soon.

can anyone please explain the approach of problem C ?

Can anyone tell me which case am I missing? It was failing the 5th pretest.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >>t;
    int cas=0;
    while(t--){
        cas++;
        int n,k;
        cin >>n;
        int pos=0,neg=0;
        vector<int> v;
        ll sum=0;
        for(int i=0;i<n;i++){
            int inp;
            cin >>inp;
            v.push_back(inp);
            if(inp<0)
                neg++;
            else if(inp>0)
                pos++;
            sum+=inp;
        }
        if((pos>1||neg>1)&&(pos+neg<n))
            cout<<"NO"<<endl;
        else if(n==3&&((v[0]+v[1]+v[2])==v[0]||(v[0]+v[1]+v[2])==v[1]||(v[0]+v[1]+v[2])==v[2]))
            cout<<"YES"<<endl;
        else if(n==3)
            cout<<"NO"<<endl;
        else if(n==4){
            for(int i=0;i<n;i++){
                ll ss=sum-v[i];
                int flag=0;
                for(int j=0;j<n;j++){
                    if(ss==v[j])
                    flag++;
                }
                if(!flag){
                    cout<<"NO"<<endl;
                    break;
                }
                if(i==3)
                    cout<<"YES"<<endl;
            }
        }
        else if(pos>2||neg>2)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

Thank you!

Well, can anyone explain more about problem G? How is multiply and mod defined in GF(2)?

how to test interactive solutions in the local environment?

can anyone tell me a testcase where my solution for problem C is wrong? my submission 162205607

I have a question about E problem. It is said that the minimum strength needed is max(a_i — b_i). However when the a is [1, 2, 7, 4, 3, 6, 5] and the b is [1, 2, 3, 4, 5, 6, 7], it only need strength 2.First, we swap 5 and 7, then the a changed to [1, 2, 5, 4, 3, 6, 7]. Second, we swap 3 and 5, then the a changed to [1, 2, 3, 4, 5, 6, 7]. It is 2 not 4

C was nice but annyoing. I liked the problems.

Otherwise, it can be shown that there must exist some subarray with equal endpoints that contains b1 followed by b2, so we can reverse it.

Show it then?

F is amazing, tho wish I didn't face undefined behaviour and spend 2h debugging it :noo:

Unable to see why my solution is failing for problem C: https://codeforces.me/contest/1698/submission/162286028

Update: I missed some cases. Accepted here https://codeforces.me/contest/1698/submission/162287499

My E solution with time $$$O(n)$$$:162292830

Can any one help me with verdict Idleness limit exceeded in D , I have not solved much of interactive problems

link to my solution ... Any help is appreciated

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

• A: XOR Mixup
• B: Rising Sand
• C: 3SUM Closure
• E: PermutationForces II
• F: Equal Reversal
• G: Long Binary String

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

In Problem E let strength s = 2 a = [1 6 2 4 3 5] b = [1 2 3 4 5 6]

when i = 1 we swap 4 with 6 a = [1 4 2 6 3 5] b = [1 2 3 4 5 6]

when i = 2 we swap 4 with 2 a = [1 2 4 6 3 5] b = [1 2 3 4 5 6]

when i = 3 we swap 3 with 4 a = [1 2 3 6 4 5] b = [1 2 3 4 5 6]

when i = 4 we swap 4 with 6 a = [1 2 3 4 6 5] b = [1 2 3 4 5 6]

when i = 5 we swap 5 with 6 a = [1 2 3 4 5 6] b = [1 2 3 4 5 6]

when i = 6 we swap 6 with 6 a = [1 2 3 4 5 6] b = [1 2 3 4 5 6]

According to editorial minimum strength required is 4 as a2-b2 = 4 which will be max but here strength 2 is enough.

What am I missing?

Thanks for the great problem set. For problem F, how can we prove this statement:

Otherwise, it can be shown that there must exist some subarray with equal endpoints that contains b1 followed by b2, so we can reverse it.

Can anyone please help me in problem C ? I am getting wrong answer on test 12.

#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int arr[n];
        int pos = 0, neg = 0, zeros = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            if (arr[i] == 0)
            {
                zeros++;
            }
            if (arr[i] > 0)
            {
                pos++;
            }
            if (arr[i] < 0)
            {
                neg++;
            }
        }
        sort(arr, arr + n);
        if (pos >= 3 || neg >= 3)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 2 && neg == 2)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[n - 1] == -arr[0] && arr[n - 2] == -arr[1])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 2 && neg == 1)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[0] == -arr[n - 1] || arr[0] == -arr[n - 2])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 1 && neg == 2)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[n - 1] == -arr[0] || arr[n - 1] == -arr[1])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 2 && neg == 0)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 0 && neg == 2)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 1 && neg == 0)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 0 && neg == 1)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 0 && neg == 0)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 1 && neg == 1)
        {
            if (arr[n - 1] == -arr[0])
            {
                cout << "YES" << endl;
                continue;
            }
            else
            {
                cout << "NO" << endl;
                continue;
            }
        }
    }
    return 0;
}

I think the complexity in problem F should be $$$O(n^2)$$$ because you can find equal endpoints around $$$b_1,b_2$$$ in $$$O(n)$$$

Thanks for the Solution in Python!

I don't understand why we need to have a maximum of two zeroes. If the whole array is made up of zeroes, wouldn't we need at least 3 zeroes in order to have 3 distinct indices?

I have a doubt with 3 sum closure basically its says more than 2 positive or negative number stands out to be no as a output

but see this test case -2 -3 -7 0 9 3 3 in this the answer should be no but -2-7+9 turns out to be 0 which is there in the array

https://codeforces.me/contest/1698/submission/266519241 for problem C can anyone help me figure out why i am getting tle.