binary searching on B worked

can anyone please explain problem A,

Can I get some help with debugging ?

https://codeforces.com/contest/1788/submission/192961698

I have implemented exactly same approach as mentioned in the editorial. During contest I got 2 WA :( ... CAN"T figure out what is wrong...

I didn't understand the part of taking m = (n-1)/2 and how he choses the pairs in prb C. can anyone explain it plz

Any One has code for problem B, I tried binary search it's not working...

Tutorial for Problem B:

NlogXlogN with DSU passes in 2140ms

imho, giving this as final task of a 6-round 2-hour D2 is rough...

https://codeforces.com/contest/1788/submission/192975706

C, D and F are great problems. I think the editorial for C kinda glosses over inspiration for the construction.

Here is my construction idea

Consider

14 13 12 11 10 9  8
1  2  3  4  5  6  7

Currently all pairs have equal sums. If I swap the bottom elements of 2 pairs with difference $$$d$$$, then the sum of one pair increases by $$$d$$$, and the other reduces by $$$d$$$. Over here if I am able to get $$$+d$$$ and $$$-d$$$ for $$$d$$$ from $$$0$$$ to $$$3$$$, it will produce consecutive sums.

14 13 12 11 10 9  8
1  2  3  4  5  6  7
|  |  |  |  |     |
|  |__|  |  |     |
|________|  |_____|

Notice that the odd differences are nested within each other, and so are the even differences. Swapping the shown pairs produces.

14 13 12 11 10 9  8
4  3  2  1  7  6  5

This has consecutive sums from $$$12$$$ to $$$18$$$. Generalising to arbitrary odd $$$n$$$ is not difficult.

This also makes it trivial to see, that even $$$n$$$ is impossible. You can produce any pairing by swapping elements. Each swap will make one pair increase by $$$x$$$, and the other decrease by $$$x$$$. Let us consider the final solution. Each final pair will be $$$2n + 1 + x$$$ for $$$x$$$ in some consecutive range, that adds to $$$0$$$. This is impossible for an even length range. If there are more positive elements, the range will be positive, and negative otherwise. This is very trivial to check. Therefore even $$$n$$$ is impossible.

In problem C you provided one of the possible pairings but how can someone prove it? Or is it just random guesses?

shit contest , constructive force

Was a good Contest, struggled on B for a bit but finally got it. Thanks for the fast tutorial!

Could someone give an explanation on why binary search works for problem B?

I've seen submissions like this one 192978163 and can't figure out why it passes.

1788E and 1667B are similar

For B, I brute forced many numbers and eventually found a pattern

For even you can just do n / 2, n / 2 For odd you will find answer (n + 1)/2 + x, (n — 1)/2 — x Where x = 4, 49, 499, 4999, ..., 8, 89, 899, 8999, ...

Can somebody please prove my solution?

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n;
    std::cin >> n;

    auto f = [&] (int x) {
        int s = 0;
        while(x) {
            s += x % 10;
            x /= 10;
        }
        return s;
    };

    if(std::abs(f(n / 2) - f(n - n / 2)) <= 1) {
        std::cout << n / 2 << " " << n - n / 2 << "\n";
        return;
    }

    int i = 4, x = (n + 1) / 2, y = (n - 1) / 2;
    while(i < n) {
        if(std::abs(f(x + i) - f(y - i)) <= 1) {
            std::cout << x + i << " " << y - i << "\n";
            return;
        }
        i = i * 10 + 9;
    }
    i = 8;
    while(i < n) {
        if(std::abs(f(x + i) - f(y - i)) <= 1) {
            std::cout << x + i << " " << y - i << "\n";
            return;
        }
        i = i * 10 + 9;
    }
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
}

Can anyone explain the pairing part of C?

https://codeforces.com/contest/1788/submission/192980925

Can anyone plz help me why I am getting runtime error on this Java code I have tried different approach on B.

Can anyone please tell me what is wrong in my code for question A. Instead of counting 2's I just maintain prefix and suffix array of multiplication My submission

Can anyone explain me problem B, I am unable to understand it properly.

Why can't E use the method of binary search monotone stack to realize it

Could anyone tell me why the following code to solve problem A didn't work? it failed at the middle of the test 2:

int leftProduct = 1; int k = -1;

for (int i = 0; i < length; i++) { leftProduct *= arr[i];

int rightProduct = 1;
for (int j = i+1; j < length; j++) {
    rightProduct *= arr[j];
}

if (leftProduct == rightProduct) {
    k = i + 1;
    break;
}

}

printf("%d\n", k);

Here is the submission link: https://codeforces.com/contest/1788/submission/192980945

In E, what does it mean to "use coordinate compression on $$$p_i$$$" where $$$p$$$ is the prefix sum array of $$$a$$$ ?

Any dp solution for D?

Can anyone please explain the condition of excluding the unnecessary dots from the subsets in problem D ?

in problem D what according to author i will move to right and j will have to move left but while solving we are taking a lower-bound of 2*a[i]-a[j] and not 2*a[i]-a[j]-1, can any one explain where am i wrong

For problem F, in the formula $$$\bigoplus_{k \in L} p_{r_k} \oplus c$$$, the value of $$$c$$$ is the xor-sum of every path from $$$p_{r_k}$$$ to every vertex in $$$G_k$$$, right?

Then, wouldn't changing the value of $$$p_{r_k}$$$ also change the values of $$$p_i$$$ for some vertices in $$$G_k$$$? If I understand this correctly, we are getting the initial values of $$$p_i$$$ with dfs in each component of $$$G'$$$, setting its value to the xor-path from the dfs root to vertex $$$i$$$. So, if $$$r_k$$$ is in the middle of the path, the value of $$$p_i$$$ would also change.

I'm guessing that I'm not understanding that part correctly, where does the constant $$$c$$$ comes from? Is that the way to get the initial values of $$$p_i$$$?

Thanks.

For problem E,is there a conclusion that "for dp[i], we solve it greedyly.the answer is the leftmost k which p[k]<=p[i]."

it means: dp[i]=min(dp[i-1],dp[j](p[j]<=p[i]&&(∀kp[k]>p[i])));

thx.(pls forgive my poor English:-)

I think problem B can be solved by Binary search. Maybe tag it for binary search

my solution for B: if n even , result is n/2 and n/2 else

we need to assure that the sum of digits of first number and second number differ by at most 1

let's say the big number is x1 x2 x3 x4 .. x(i)

we count sum=x1+x2+x3+x4 and we give the first number a counter of sum/2 and the second number a counter of (sum/2) or ceil(sum/2) (don't use ceil , use (sum+1)/2)

after that we go through the string of the big number and we give the first number the max between (sumForFirst-x(i),0) and we give the second the max between max(sumForSec-restX(i),0)

why this works? because we can only use x1+x2+x3+x4 and we will spread them by the digit, so this will work . ( and the addition of first and second number can't mess things up because the maximum digit is 9 --> so there is no carry when we add the two numbers ) this is my submission : https://codeforces.com/contest/1788/submission/193001440

With how vague the editorial is about finding a matching for C, I'm convinced that it's really just a pattern-finding problem after the initial steps of removing even $$$n$$$ from consideration and finding the target sums for odd $$$n$$$. Now I don't feel so bad for not being able to solve it.

For those who did solve C, can anyone please elaborate on the thought process on how you arrived at a correct matching?

For B We can divide every digit "n" to two parts n / 2 and n — n / 2. if n is odd, the first time we give the first answer the bigger part, at nxt time we give the bigger part to the second.

There is a example: 135246 -> 113123 and 022123

In problem C if k is a integer, then how can we gurantee that n pairs always exists such that their sum is consecutive when sorted?

can anyone please tell what i am doing wrong, wrong answer on test 2 , 61st numbers differ — expected: '316', found: '71' 193009289

Can someone explain the solution of D problem? Thanks in advance

Can anyone tell me the Intuition behind the pattern for finding matching pairs given in the editorial (1,3m+3,),(2,3m+4)....so on).

Please, someone help me to understand the problem A

Why does question B take a brute force approach to the pre-test 1 error, can it provide the data of test 1?

What is the output when n = 19, 39,59.... For B.

How did they reached to that solution for problem B? Is it just intuition or it came from some kind of theorem, formula etc?

Why is binary search working for B?

in C can anyone explain i got k = 3*(n+1)/2 now how to generate pairs like k, k+1, k+2----k+n-1 as sum. Why this tutorial hs considered m as n-1/2 how we got.. pls someone clear the doubt

https://codeforces.com/contest/1788/submission/192882231 why this approach doesnt work i calculated the product suffix and prefix and when prefix of i == suffix of i+1 i break the loop so why it doesnt work ?

I want code.

I did not find the similar approach for C so here it is:
Let's pair all numbers at 1..n(left) with numbers from n+1..2n(right).
Let's start with 1 and some x, their sum is (x + 1) so for next pair sum should be (x + 2). I can't take 2 as next left number cause then I must take x as right number for sum to be (x + 2). So I take 3 as next left number and x-1 as right number. Next pair will be 5 and x-2 and so on. That's how I construct pair with odd numbers from 1..n: I increase left by 2 and decrease right by 1 to make step=1 in sums of pairs.
Then I need to deal with even numbers. After last odd number I need to go to first even number 2. It means I need to decrease left by (last_odd — 2) and increase right by (last_odd — 2) + 1.
Then again I increase left by 2 to iterate over even numbers and decrease right by 1 to make step=1 in sums of pairs.
To make it all work we need to choose x at the beginning. The most critical part is when we go from last odd number to first even number: we need to increase right by (last_odd — 2) + 1 which is equals to n-1 because last_odd=n. So to not overflow 2n limit we need to have right number as 2n-(n-1)=n+1 at most. Apparently this is the least right number we can get from n+1..2n.
So x at the beginning should be (n+1)+(count_odd_numbers_in_1..n — 1)

examples:

submission 192961794

Problem C. Using the formula for the sum of an arithmetic progression, we found that the sum of the first pair is (3n+3)/2. Now how do we restore all pairs? Thank you.

Great contest! you can find the video editorials for problem C and D here .

hope this helps you! happy coding!

In question D can someone explain me

"Now let's solve the problem for subsets. Instead of counting number of adjacent dot that moves toward each other for each subset of dots, we will count the number of subset for each possible 1≤i<j≤N where dot i moves right and dot j moves left and there are no dots between i and j ."

Easiest div2 contest so far, yet I got slain by mere problem D :(

I have a question about Problem B: Since I need to find 2 numbers, A and B, for the input number N such that, a) A + B = N and b) sumofdigits(A) — sumofdigits(B) is at most 1, could I not just use the approach where I do the following:

• if N is even, assign N/2 to both A and B; --> ensures that sumofdigits(A) — sumofdigits(B) = 0
• if N is odd, assign N/2 to A, and (N/2)+1 to B; --> ensures that sumofdigits(A) — sumofdigits(B) = 1

Could someone please clarify this for me, since I think I misunderstood the question?

can someone explain me the the solution for problem E

I cant understand how the dp state is defined in the editorial?

I tried solving this using recursion with dp but getting TLE on Test 4 Submission Link

can anyone explain problem 1788D editorial?

video editorial for Chinese：

BiliBili

include<bits/stdc++.h>

using namespace std; int main(){ int t;cin>>t; while(t--){ int n;cin>>n; if(n%2==0){ cout<<"NO"<<endl; continue; } vector<pair<int,int>> p; cout<<"YES"<<endl; int i=1,j=2*n; while(i<j){ p.push_back({i,j}); i+=2; j--; } i=2; while(i<j){ p.push_back({i,j}); i+=2; j--; } sort(p.begin(),p.end()); for(int i=0;i<p.size();i++){ cout<<p[i].first<<" "<<p[i].second<<endl; } }

}

Ques C) Can anyone tell me what is the error?

Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.

In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540

[user:KAN][user:MikeMirzayanov][user:azberjibiou]

For competitive programming, seek the light, Of knowledge, hard work and perseverance bright, For in its glow, you'll find a winning path, With endless hours of coding, building strength.

Though algorithms may seem complex, so tough, And bug-ridden code will make you frown, Stay true to your dreams, and find a way, And victory shall come to you one day.

A love for logic and a curious mind, Are all that's needed, to leave all behind, For coding is an art, with endless rules, That with each win, shall bring greater jewels.

So don't despair, when challenges arise, For in them lies the key to your prize, And if you're down, and cannot find your way, Just take a break, then come back to play.

For in this game, no player truly loses, For every problem solved, a victory chooses, And so keep pushing, keep trying, don't stop, For the greatest programmer, is the one who never stops.

In problem B, my code passed in a weird way. Can someone help me prove it a little more rigorously?

For the case of n being odd, I set p=(n-1)/2 and q=(n+1)/2, and then I keep doing "p+=5" and "q-=5" to get the answer.Here is the link to my code:https://codeforces.com/contest/1788/submission/192988232 I hope someone can help, because I need to perfect my solution.

thanks for the editorial. <3

Problem B can also be solved with just randomly choosing $$$x$$$ until you find good one.

Link to solution.