Problem idea: azberjibiou

**Tutorial**

Problem idea: azberjibiou

**Tutorial**

Problem idea: azberjibiou

**Tutorial**

Problem idea: azberjibiou

**Tutorial**

Problem idea: azberjibiou

Problem solver: YeongTree

**Tutorial**

1788F - XOR, Tree, and Queries

Problem idea: azberjibiou

**Tutorial**

binary searching on B worked

do you have the code?

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

please share the code !

You can check his code: https://codeforces.com/contest/1788/submission/192954046

use string properties it is easy

Can you prove that the invariant of binary search holds correct mathematically ?

i didn't, but i think its possible

Lol, I was thinking of binary search, but didn't thought it would work awesome man.

I speculate that you were just

luckythat your binary search (192900488) worked.For binary search to reliably work, your data

must be sortedby the search key (which is not the case for this problem).There is this sentence in the tutorial:

My first guess is that your solution were lucky enough to pass due to the same reason a

random searchwould pass :)There is an interesting exercise, by the way: could you find a

counter examplefor your solution (some test case which were absent in system tests but which would break your solution).i thought a lot but couldnt find any such test cases? i would really appreciaite if there are any.

Hmm... now I could not find myself any $$$n$$$ for which the submission would not work.

I can not explain why it works for this problem.

Strictly speaking, the submission implements

some algorithmwhich issimilar to binary searchesbut which is not a binary search. That means that reasoning we usually use for analysing a binary search could be invalid.Example for n=1999:In what ways it differs from a binary search:

the search range is not divided in half on each step (note width=11 after width=18)

it's not obvious that the algorithm must converge with a necessity: abs(x-y) does not get smaller on each step (note (x-y)=12 after (x-y)=-4)

can anyone please explain problem A,

you need to find the position k that divides the array in a way that the product of elements from the start until element in position k = the product of all elements after this position k

why prefix and suffix arrays for storing the multiplication will not work for problem A ?

Because the maximum possible product is 2^1000 and there is not in C++ any data type that can store that value, actually when n equals to 65 and each element in A is equal to 2, the prefix, suffix idea fails

thanks for the clarification ! got it !

Python will work here , because python can calculate till

and we need 1000 only.`pow(2,14284)`

i don't use prefix multiply, i only use same hint like that. let's call dp[i]=d[i-1]+(a[i]==2), then you find position i that dp[i]=dp[n]-dp[i], you can do it in O(N).

Array only consists of 1 and 2, you can notice that multiplying by 1 does nothing, so we count the number of 2's in the array, to divide the array into two equal parts, there must be an equal number of twos on each part, using a second variable we can loop from N to 2 and check if the array value is 2, if it is, we add 1 to the current variable, and subtract 1 from the original count, when 2 variables are equal, means we can create equal parts by splitting the array at current position

Could you please tell me why my code is giving wrong answer instead of counting number of two's I just make prefix and suffix array of multiplication My submission

Its because of the constraints where n=1000. Take the worst case where all are 2 then in the suffix you will have to evaluate 2^1000 which will give TLE.

okk I undestand Thanks

2^1000 will not give TLE. TLE means time limit exceeded. Instead, it will overflow and give WA — wrong answer.

I tried to solve this problem in the hard way, but I don't know why it failed on the middle of the test 2. Could you please check my submission here: https://codeforces.com/contest/1788/submission/192980945

Its because of the constraints where n=1000. Take the worst case where all are 2 then in the suffix you will have to evaluate 2^1000 which will give TLE.

in the multiplication, only 2 matters. So you need to divide the array such that number of 2's on left part is equal to number of 2's on right part.

Count the number of twos in the given array and store it in variable two. If the number of twos is odd, then the output will be -1; If the number of tows is 0, that means the output is 1. Otherwise, run a loop until you find the number of two/2 th 2. Once you find that, break the loop. Index of two/2 th 2 is the output in that case.

Check this solution.192969686

Can you explain the last step in which you did count = two/2; I didn't get that part ?

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 found the error in my code. I made very stupid mistake...

Got AC with single line change :(

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

wish I could spot error during contest.

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

check out this submission you will understand https://codeforces.com/contest/1788/submission/193067198

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

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

Every thing is Nice, But how do you know that we can skip the whole series if the number is not present at (l+r)/2 i.e. abs(f(mid) — f(n — mid)) <= 1, and move to further new l+r/2 which is Log(n); of whole series i think.

Spoilerhttps://codeforces.com/contest/1788/submission/192977088

Tutorial for Problem B:

Hint 1Think in term of digits

Hint 2Can we divide each digit by 2 and then assign in the two numbers.

SolutionLet a and b be empty arrays , from which we form number a1 and b1 later.

Traverse from the least significant digit ,Divide each digit by 2 ,now two cases arise :

Case1: Digit is even, Then simply push digit/2 in a and b.

Case2: Digit is odd ,As We have to maintain the sum of digits of a and b equal to 0 or 1 ,so if there are multiple odd digits then we have to maintain a flag such that we can push (digit+1)/2 and (digit)/2 alternatively in number a and b.

for eg .n= 134

we traverse the number in the way 431 :

initially a={ } b={ }

FOR digit 4 , a={2} b={2} 4/2=2 (case of even digit)

For digit 3 , a={2,2} b={2,1} as (3+1)/2=2 and (3/2)=1 (case of odd digit).

for digit 1 a={2,2,0} b={2,1,1} as we have already push for an odd number in a then this time we will push (digit+1)/2 in b.

So final number formed from a is a1=220 and from b is b1= 211 (i am assuming you may know how to form a number from given digits.)

mycode . Note : this is one of the approach ,there can be multiple optimized approaches.

apologize for my shit English.

thanks!!

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

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.

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

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.

Wow, this is exactly what I thought about but I couldn't get the last observation of nested swapping for the same parity. It took me the whole round thinking about how to perform swapping in vain.

Nice idea, maybe better than my construction idea.

Here is my construction idea.

For some integer $$$x$$$ and $$$y$$$, $$$(x, y), (x+1, y+1), \ldots, (x+k, y+k)$$$ will give an arithmetic sequence of common difference $$$2$$$.

Arithmetic sequence from $$$x_1+y_1$$$ will cover the even part, and another arithmetic sequence from $$$x_2+y_2$$$ will cover the odd part. After some work, you can find $$$x_1, y_1, x_2, y_2$$$.

Nope, I found your idea much more intuitive than the one mentioned above. I was dead stuck on the problem and knew I was missing something for sure but after reading you comment here, solved it in the next 10 mins.

Super intuitive solution for C

Note that n is only possible when (3*n+3) is divisible by 2, can be proved by equalizing the total sum and the sequence sum.

Nice idea, but I am unable to implement it. Can anyone share the implementation?

how you were able to construct this idea so fast? Will studying number theory help me with this problem?

Hi Everule,

I think I have a much simpler construction for this problem. A bit of math will tell you that the smallest sum will be 3(n + 1)/2.

Let,

S = 3(n + 1)/2

Now break up the sequence [1, 2n] in two parts [1, n] and [n + 1, 2n].

First pair is (1, S — 1)

Second pair is (2, S — 1 + 1)

and so on...

Just make sure to loop around the first number of the pair in the range [1, n] and second number in the range [n + 1, 2n]. You will generate all sums in the range [S, S + n — 1].

Proof left as an exercise for the reader. :)

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

Adding proof because some people asked for it.

Lemma 1:Lemma 2:Terminology:Lets call sums with even difference from S,

even sums.Lets call sums with odd differences from S,

odd sums.So [S, S + 2, S + 4, S + 6, ...] are even sums.

And [S + 1, S + 3, S + 5, ...] are odd sums.

Main Proof:We have to make n sums in the range

`[S, S + n - 1]`

, since according toLemma 1, smallest sum must be S and we have to make n consecutive sums.So, we have to make

`ceil(n / 2) even sums and floor(n / 2) odd sums`

.Visually, we have to make

Lets take this as our first pair.

`[1, S - 1]`

, clearly this makes sum S one of even sum.Next pairs will be -

`[2, S]`

,`[3, S + 1]`

....`[ceil(n / 2), 2n]`

This is the key point.The last pair will have

`[ceil(n / 2), 2n]`

because ofLemma #2.`S - 1`

was the middle number and we move till end so the first number in the pair becomes`ceil(n / 2)`

.Consequently, we have

`ceil(n / 2)`

pairs and the sum of each pair is greater than the previous by 2,so we have generated all the Even Sums.After this we are going to loop around the range

`[n + 1, 2n]`

for the second number of the pair.So, next pair will be

`[ceil(n / 2) + 1, n + 1]`

The sum will be

`(n + 1) / 2 + 1 + n + 1 = S + 1`

.Now if we keep generating subsequent pairs until we reach

`[n, S - 2]`

, we will have generated all the odd sums starting from S + 1.Both Lemmas can be easily proved with a bit of math.

I suppose the edi glossed over it because there are a lot of valid constructions.

For example mine https://codeforces.com/contest/1788/submission/193410581.

I realized all the sums have to be different mod n so if I increase one of the numbers by 1 and decrease the other by 2 it it will always be different mod n.

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

It became obvious for me after I wrote down on paper the pairings (and the sums) by the formula for n=9 (m=4, k=15).

Trying to attach the photo:

mivael-cdfr-1788C-n9-example.pngshit contest , constructive force

not shit but hard, atleast for me

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.

My guess is above.

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?

Can anyone explain the pairing part of C?

Maybe you'll find this useful.

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

2^1000 is huge.

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

Process each digit ($$$d$$$) separately.

Divide the digit in two smaller digits:

$$$a = \lfloor\frac{d}{2}\rfloor$$$

$$$b = d - a$$$

First time when $$$a \ne b$$$, place $$$a$$$ to $$$x$$$, $$$b$$$ to $$$y$$$.

Second time when $$$a \ne b$$$, place $$$a$$$ to $$$y$$$, $$$b$$$ to $$$x$$$.

...

Example:$$$1094038$$$ can be represented as $$$(52014 + 1042024)$$$:

`n: 1 0 9 4 0 3 8 (sum of digits: 25)`

`x: 0 0 5 2 0 1 4 (sum of digits: 12)`

`y: 1 0 4 2 0 2 4 (sum of digits: 13)`

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

counter-test for your last submission:

-1 -1 2 -2 -1 1

your solution returns 4 (segment [3, 6]), while the answer is 5 (segments are [1, 3], [5, 6]).

Here's how alternate solution you said works.

Note the recurrence in the official solution:

Solving it with brute-force costs $O(n^2)$ time. But we can solving it in almost linear time with a technique similar to Monotonous Queue.

We find that when there's a pair of index $$$(x,y)$$$ s.t. $$$dp_x-x<dp_y-y$$$ while $$$p_x\ge p_y$$$, if we use $$$k=x$$$ in one recurrence, we can always use $$$k=y$$$ (since $$$p_y \le p_x \le p_i$$$) with an better value, so $$$x$$$ can never be the optimal decision in a recurrence.

We use a set to maintain all pair $$$(dp_k-k, p_k)$$$ (sorting by $$$p_k$$$) possibly optimal for a recurrence. When adding $$$i$$$, we can maintain it by erasing all $$$x$$$ with $$$dp_x-x<dp_i-i, p_x\ge p_i$$$, and check if $$$i$$$ will be erased after adding $$$i$$$. And then it satisfies something similar to Monotonous Queue: if $$$p_x<p_y$$$ then $$$dp_x-x<dp_y-y$$$. So we can search for the maximum $$$p_k$$$ for the optimal decision($$$O(\log n)$$$ per recurrence).

code (Note that this solution calculate the minimum count of numbers

notpresent in any segment you choose instead.)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];

}

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

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

You evaluate 2 ^ 1000 in worst case, you must use MOD if you want to handle the results:

int MOD = 1e9 + 7;

rightProduct = (rightProduct * arr[j]) % MOD;

Ah, Thanks! I didn't notice that. Can I use MOD in C normally? and does is have Cons (disadvantages)?

As a Gray I don't recommend it unless you know there won't be any collisions given the constraints of the problem or your submission could be hacked or it will just give WA, actually I didn't think about that when I answered you, it works for this problem because the constraints are small

You can use Mod in C.

same approach i used it failed on tc2 also https://codeforces.com/contest/1788/submission/192882231

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

precompute all the possible prefixes of the given array and then map them to the range 0 — k-1 based on their relative values (k is the number of unique prefixes). eg- if the prefixes or -3 4 2 -1 then this will be converted to 0 3 2 1.

My Submission

Makes total sense, thank you !

Any dp solution for D?

my solution was something like dp[i][j][dir] -> number of collisions if you are standing on the ith index, you chose the jth index before you and the jth index had a direction left/right.

what would the transitions be?

let K be the first index such that

`dist[i]-dist[j] <= dist[k]-dist[i]`

My Submission

All right thank you!

Thank you. Can you clarify a bit more about what do you mean by,

`you chose the j-th index before you and the j-th index had a direction left/right`

. But the problem says each dot moves in the direction of the closest dot (different from itself) until it meets another dot. So doesn't it mean each dot has their directions fixed ?I am assuming that

My final answer is the sum of

`dp[i][[j][right]`

for all pairs of i and j.If you are thinking that maybe the

`dp[i][j][left]`

is not a valid state because j has no closer element on its left w.r.t to i. Then that state will never be calculated in our answer.I had a similar sol but couldn't implement it-tons of debugging :(

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

It is because in the question it is mentioned that if its a tie the point will move left so if a point is equal to 2*a[i]-a[j] i will move left instead of right.

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.

If you change $$$p_{r_k}$$$, $$$p_i$$$ would also change. Here is one example.

If $$$G'$$$ has $$$3$$$ vertices, $$$r_k=2$$$ and the edges are $$$(1, 2, 3), (2, 3, 1)$$$

$$$p_3=p_2 \oplus 1$$$ and $$$p_1=p_2 \oplus 3$$$.

Odd degree vertices are $$$1$$$ and $$$3$$$, so we get $$$p_1 \oplus p_3 = p_2 \oplus 1 \oplus p_2 \oplus 3 = 2$$$

In this case, $$$c=2$$$.

Thanks a lot! I get it now. I should have reviewed that part more thoroughly.

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

Can you prove it?

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?

I didn't participated in the contest, but I solved after . my thought process: proofing if n is even we have no solution

after that I randomly tested bunch of ways to solve the match, one worked for all(and kinda proofed that it always work for n odd (like the editorial with the m thing), so I coded it . that's really it.

Pattern finding is the case for me. I first tried getting the sum of $$$(a_1 + b_1)$$$ with a little bit of math which turned out to be $$$\frac{(3n + 3)}{2}$$$ and noticed that from pair $$$(a_i,b_i)$$$, we can get to the next sum $$$(a_{i+1}, b_{i+1})$$$ with a difference of $$$1$$$ by adding $$$+2$$$ to $$$a_i$$$ and $$$-1$$$ to $$$b_i$$$. After randomly testing many ways to do the matching, setting $$$a_1 = 1$$$ and $$$b_1 = \frac{(3n+3)}{2} - 1$$$ worked. I also stress-tested this with a bunch of random test cases to confirm. (I left out some details which you can check in my submission if interested).

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?

We could probably prove it by construction. (I did not formally prove that myself but maybe this illustration on paper will help to get the idea in that direction.)

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

You're trying to compute the products, but this would not even fit

`long long`

if there are many 2s. If there are 1000 $$$2$$$s, the result is $$$2^{1000}$$$, which requires around 1000 bits. The`long long`

type only supports 64 bits.Rather than calculate the products directly, I would suggest that you instead keep track of the power of 2 that the product has, i.e., how many 2s were present in this desired product.

thank u brother , i solved

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

Suppose you take a specific subset of $$$\geq 2$$$ dots. You can then represent each dot as L or R based on whether it moves left or right, and construct a string of Ls and Rs. String always begins with R and ends with L. The number of distinct stopping coordinates for this subset is equal to the number of instances of the substring "RL" (each R stops at the same place as its next L, and each L stops at the same place as its previous R).

Therefore, the objective is to output the sum of the number of RL substrings in ALL possible subsets of size 2. However, this can be rephrased as follows: for each pair of dots $$$i$$$ and $$$j$$$, count the total number of subsets where dot $$$i$$$ and dot $$$j$$$ form an RL substring, and output the sum for all pairs.

Given $$$i$$$ and $$$j$$$, when will dot $$$i$$$ and dot $$$j$$$ form an RL substring? This arises only in a subset for which dot $$$j$$$ is the closest dot to dot $$$i$$$ (no ties allowed, since $$$i$$$ breaks ties by going left, away from $$$j$$$) and dot $$$i$$$ is the closest dot to dot $$$j$$$ (ties allowed, since $$$j$$$ breaks ties by going left, towards $$$i$$$). To count how many of these there, we can first count the number of dots, excluding $$$i$$$ and $$$j$$$, such that the presence of these dots will not prevent $$$i$$$ and $$$j$$$ from moving towards each other.

Let $$$d = x_j - x_i$$$. Dots with positions $$$< x_i - d$$$ are allowed, since $$$i$$$ still moves to $$$j$$$, and the dots with positions $$$\geq x_j + d$$$ are also allowed, since $$$j$$$ still moves to $$$i$$$. We can count how many such dots there are with two binary searches: one for $$$x_i - d$$$ and another for $$$x_j + d$$$. If we have $$$s$$$ such dots, then there are $$$2^s$$$ subsets of these $$$s$$$ dots that we can include alongside $$$i$$$ and $$$j$$$ to generate a subset (of all dots) where $$$i$$$ and $$$j$$$ form an RL pair.

The final output is the sum of $$$2^s$$$ for each $$$(i, j)$$$ pair, modulo $$$10^9 + 7$$$.

My submission: 193040606. The

`pw`

vector stores the powers of 2 modulo $$$10^9 + 7$$$. The variables`lsz`

and`rsz`

denote the number of allowed dots that are left of $$$i$$$ and right of $$$j$$$ respectively. The way the built-in`lower_bound`

is defined conveniently fits with how ties are handled in this problem.Great Explanation Thanks.

It looks kind of contribution technique. I understood that nubers of points for a given subset is no of LR transititons LLL..RRRR..LLL..RRR. I was kind of trying to fix i and j as first and last indexex in given subset and i guess it's a deadend i went nowwhere from there

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).

I found the intuituion after writing down the pairs and the sums for n=9.

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.

14 5 24 15 34 25

For 19, 39, 59 respectively but Why??

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

If you reorder the proposed sequence of pairs (make the pairs be sorted by their sums), then you get the $$$k, k+1, k+2, \ldots$$$ sequence.

Sorted:$$$(m+1,2m+2), (1,3m+3), (m+2,2m+3), (2,3m+4), (m+3,2m+4), \ldots$$$

Correspondent sums:$$$3m+3, 3m+4, 3m+5, 3m+6, 3m+7, \ldots$$$

The first sum is k:$$$3m+3 = 3\frac{n-1}{2}+3 = 3(\frac{n-1}{2}+1) = \frac{3}{2}(n+1) = k$$$

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:

n=31 5

3 4

2 6

n=51 8

3 7

5 6

2 10

4 9

n=71 11

3 10

5 9

7 8

2 14

4 13

6 12

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 ."

We need to count pair of dots that adjacent to each other amony all subsets, and instead of iterate the subsets, it's eaiser to iterate all pairs of dots that moves toward each other and count how many subsets contain them. (my english is bad, if you still can't understand I don't blame you QAQ)

Yeah, I got it now. I just have to change the order of summation in that double summation.

image source: https://youtu.be/HkGdJod75Po

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:

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

I think you understood the question, but your approach is incorrect. Consider $$$N = 19$$$, where $$$N/2 = 9$$$ (whose digits sum to 9) and $$$N/2 + 1 = 10$$$ (whose digits sum to 1). There are many other edge cases (like if you have consecutive 9s) that this kind of approach would not be suitable.

Ah, I see your point. Thank you for your help! :D

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.

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.