Hello Codeforces and welcome back to another div2 round.

YeongTree and I are excited to invite everyone to participate in Codeforces Round 851 (Div. 2), which will be held on Feb/09/2023 17:35 (Moscow time).

This round is rated for the participants with ratings strictly lower than **2100**. You will be given **6 problems** and **2 hours** to solve them. All the problems are authored and prepared by YeongTree and me.

We would like to thank

- Arpa for excellent coordination and help with prepration.
- Alexdat2000 for Russian translation.
- tlsdydaud1, hypergraph_coloring, Kawaii2DIdolOfGSHS, nlog, Ryute, TheQueenOfHatred, hanbyeol_, Physics07, jjang36524, OctaneC8H18, ahgus89, DELTARUNE, Go3, andyandy, PUFL, Pratyush1606, PUPA, Justice_Hui, garam1732, windva, culver0412, nor, maomao90, MagentaCobra, dorijanlendvaj, khiro, mejiamejia, AquaMoon, mjhmjh1104, mister, ayhan23 for testing and feedbacks.
- MikeMirzayanov for great systems Codeforces and Polygon.

The score distributions will be updated later.

**UPD1**: Score distribution: $$$500−1000-1500-2250−2500-3000$$$

**UPD2**: Congratulations to the winners!

Overall:

Rated participants

AC submissions at the last second

**UPD3**: Editorial is out

Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).Looking forward to solve 2-3 problems. Positive delta to all!

Waiting For This Round.

as a tester, mister ORZZZZ

As a tester, the problems were really good.Participants, please enjoy the contest!

Similar names (ᗒᗩᗕ)

thanks aftors

Problem

Cis trash. Change my mind...The problem with number C is that it's not called "trash", it's called "high quality".

Yeah right, it's the best problem ever made. What would Codeforces become if every problem was of this type...

SpoilerHell

As a tester, I enjoyed the round and the statements were brief and clear. I hope to see you on the scoreboard!

What're you talking about? Problem

Cis complete piece of sh*t.As a tester, this was the best contest I have ever seen.

as a tester, this was the best contest I have ever seen.

As a participant , hoping this would be the best contest of [Contests I have ever seen + this contest]

As an apparent tester (I don't remember testing this round recently), I'm sure the problems are good :P

Good luck to everyone!!!

Good Luck for every Candidate Master to promote to Master!

Best of luck for me

OMG South Korean setters, good mathematical problems coming on the way :)

Hahaha as a tester I cannot say about that now, but good luck if you participate!

hahaha haha hahaha haha hahaha haha :(

Haha nicely predicted.

Meme :)...

Omg announcement shorter than tourist round

yes great broo

This round is going to be amazing! Good luck to all!

omg early editorial round!

At the end of the last contest, I submitted the code again, which made my score very low, so I lost the ranking. It's sad, I didn't know this rule before.

This contest may be a bit late, I guess I fell asleep at that time.

good luck everyone!

As a tester, I tested this round in the period about when I was orange for the first time.

Problems are nice tho!

Hope we will learn smth)

2 days left

My first contest was tourist round. I solved 1st 2 problem and earned 389 rating. This will be my 2nd contest .

I will skip an academic seminar in my university and participate in this round.

As a participant, I confirm that i will participate.Sometimes I really want to skip school.

Please down me, thx.

As a tester, I enjoyed this round. Good luck!

All the best everyone.

Thanks for your excitation to invite us to participate in round !

Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).Good Luck and Have Fun!

I will skip an academic seminar in my university and participate in this round

As a grey, already hit the bottom. Hoping to move to green

yeah, i guess it will be unrated round :)

Seems like a huge difficulty gap between C and D.

Wishing you all a positive delta!!

Best wishes for everyone

why I am unable to register for the Div 2 contests?

.

Worst Contest I have Ever Seen. What are these strict time limits !?!?

I do agree

Me after solving C

Waiting for contest to endSame lol

Can you please tell your approach on

C?I was given some pattern in this comment you can see it. I hope it will help you

Or something like this :)

Pattern exampleProblem 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.

explanation c

submission for c

same

Best problem set. Just awesome!!! No doubt the author is a genius. It is the best problem set I have ever experienced in my coding journey.

is that a pattern finding round?

Mo

Starting with problems A Motivation 100 to 50 B Motivation 50 to -100 C Motivation -100 to +50 Depression enters :)

How to solve E? Is this some dp? maybe we can precompute the maximum index, i can jump to from index j while keeping the sum of elements from i to j >= 0 . Am i thinking in the right direction ?

The contest isn't over yet.

no you need to solve A+B first

I thought of doing a segment dp like:

dp[L][R][0] — ans for [L; R]

dp[L][R][1] — ans for (L;R]

dp[L][R][2] — ans for [L;R)

dp[L][R][3] — ans for (L; R)

But had some troubles with calculating dp[L][R][0]. Other states are easy to calculate

SpoilerDP on segment tree with coordinate compression on prefix sums. Iterate from 0 to n-1, then answer for $$$[a_0, a_1 .. a_i] = max(DP_{minprefixsum}....DP_{prefixsum_i}) + i$$$. Then update $$$DP_{prefixsum_i}$$$ to $$$currentanswer - i$$$ if $$$DP_{prefixsum_i}$$$ is not better than the current answer.

Might be an unpopular opinion, but I think all problems were very good and interesting. Congrats to the authors for a beautiful contest. I enjoyed doing the contest very much. Thanks!

Problem

Cwasgood and interesting? You have no taste, BroDid someone constantly get wrong answers on problem B?

Me and Me... Also got TLE Btw, how to solve B? please help somebody...

me too TLE :/

The magic of Binary Search.

can you share your approcah

it's me, huh! My final ratings will be negative. But next contest, i will gonna hit harder..

me ;(

You probably converted the number to string and left a leading zero on during the output (not converting it back to int). It would fail for 101, where you would output 01 and 100. Just my guess. You would have to delete all the leading zeroes instead of just the first one

## include <bits/stdc++.h>

using namespace std;

int main(){ long long t; cin >> t; while(t--){ string str; cin >> str; int y = stoi(str); if(y%2==0){ cout << y/2 << " " << y/2 << endl; } else{

} } }

How to solve C?

ABCforces

How to solve B?

Distribute digit by digit.

Divide n into 2 numbers evenly. One number may be 1 greater than the other. Compare the 2 numbers digit by digit. The digits are either (1) same, (2) 1 vs 0, or (3) 0 vs 9. Keep track of the sum of digits of the 2 numbers so far. In case 3 above, distribute the 9 as 4 and 5 or 5 and 4 depending on the current difference of the sums of digits so far.

If n is even answer is n/2 n/2 else traverse n digit by digit and make answer

if the number is even then n/2,n/2 is the ans. if its odd then n/2,n/2+1; edge cases 1999,3999,599999 etc we can distribute it like eg for 3999 1545 2454

hi, I am new, are there any editorials or discussions section here? I am kind of lost

E looks standard. Can it be solved by dp with d&c?

upd: i think i overcomplicated it

dp[i] = max(dp[i — 1], dp[j] — j + i) while sum(j + 1 ... i) >= 0 (j < i) using map to keep (sum[i], dp[i] — i) increase.

C is too hard

C is just bad, like B, just intuition is needed...

B is common observation that each digit is independent. i meesed up B I tried to split horizontally. I don't know about C. I should have taken help from chatgpt. it would have done it may be one second or may be less

even though huge no of submissions

The time limit is quite strict I think :(

The difference between C and D was massive.

did anyone else also got wrong answer on test 5 in E

yeah me

What was your approach.

I used binary search on previous minimas of sum<=sum[i] if sum[i]<0 for getting subsegment with maximum length ending at i.

Yes, i did the classic dp like LIS but get WA on test 5 don't know why

I know now i forgot about dp[i] = max(dp[i], dp[i — 1])

Hello i am also doing same mistake in other method but not getting ig as i am getting same 126 as answer in test case 5. It will be a great favour if you please look into it

Take a look at Ticket 16726 from

CF Stressfor a counter example.I think that this round had very interesting problems with pretty beautiful possible solutions. Thanks for the contest!

My solution to problem E:

First, create the prefix sum array $$$p_0 = 0, p_i = a_i + p_{i-1}$$$ and compress it. Let $$$dp_i$$$ denote the best answer for the prefix upto element $$$i$$$. Suppose the last segment we take containing $$$i$$$ goes upto $$$\ell+1$$$ and misses $$$\ell$$$. Then $$$\ell < i$$$ and we must have $$$p_i \geq p_{\ell}$$$, and the best possible answer in this case would be $$$dp_{\ell-1} + (i - \ell)$$$. To efficiently compute these values, create a max segment tree over the compressed $$$p_i$$$ values and each time we compute $$$dp_i$$$ as $$$i$$$ plus the maximum over the segment $$$[0, p_{i}]$$$ in the segment tree and after performing $$$dp_i = \max(dp_i, dp_{i-1})$$$ (in case we don't take $$$i$$$ in the optimum answer) we update the $$$p_{i+1}$$$th location by maximising it with $$$dp_{i} - (i+1)$$$. That's it, done. Overall solution works in $$$\mathcal O(n \log n)$$$.

can anyone give idea to solve C please

I was given some pattern in this comment you can see that

Approach for C

https://www.youtube.com/watch?v=1jbhevleu-Y Copy of Problem B...Do Something

ABCforces

how to solve C

assume consecutive sum of n pairs is :

k, k + 1, k + 2, ..., k + n — 1. If u add everything u havek*n + (n — 1)*n / 2. Which should be equal to2n * (2n + 1) / 2(sum of 1, 2, ..., 2*n). Equate both terms and you will getk = (3n + 3) / 2. Now figure out the pairing part by yourself, it's not that hard.Asks for a solution, gets "figure out xyz by yourself, it is not that hard".

Hint: If you cannot figure out the pattern, try to write a brute force solution for small cases.

haha, I did until this step, it's intuitive. I couldn't figure out the pairing part.

if the value of k is a integer, then how can we gurantee that a pair always exists?

I brute forced for n=7 and the find the answer (4,8) (5,9) (6,10) (7,11) (1,12) (2,13) (3,14) then

we are done.hello sir, I am unsure of how to write a brute force algorithm for this question. Do you think you could help me? Thanks.

my total score : 390-8*50.. It looks very difficult, was this contest really hard?

It's normal for a new account to solve only the first (or even zero) problem is the first contest. You just need to take more contests to get familar with the process of CF contests.

Problem D cost much time for me and I didn't have enough time for E.

2D dynamic programming with 6 different arrays to maintain (RL, RL_sum, LL, LL_sum, LL_cnt, LL_cnt_sum) is too easy to make mistake at some details. I've spent much time to find a bug that I allocated too much space on the stack for 2D arrays (using something like ll RL[n][n], where n=3000) instead of declare them as global variables.

How to solve Ddefine 6 2D arrays for DP:

RL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to right (when there are only 2 dots, or the i-th dot is on the left of j, and dist(i,j)<=dist(j,k), which is equivalent to, x[i]>=2*x[j]-x[k]).

LL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to left (when there are more than 2 dots, and the i-th dot is on the left of j, and dist(i,j)>dist(j,k), which is equivalent to, x[i]<2*x[j]-x[k]).

LL_cnt[j][k]: The number of sets which containing more than 2 dots, and the rightmost 2 dots are j, k, and j moves to left.

XX_sum[j][k]: sum(i=0...j)XX[j][k].

Then for each pair of (j, k) where j<k, we use binary search the smallest i0 that x[i0]>=2*x[j]-x[k] (if there's no such i0 then i0=j),then the DP formula is:

LL[j][k]=sum(i=i0...j-1)(RL[i][j]+LL[i][j])

RL[j][k]=1+sum(i=0...i0-1)(RL[i][j]+LL[i][j]+LL_cnt[i][j])

LL_cnt[j][k]=2^i0*(2^(j-i0)-1)

The final answer is sum(i=0...n-1, j=i+1...n-1)(RL[i][j]+LL[i][j]).

My approach for E (Now it has been accepted)Dynamic programming, where the formula is

, which is equivalent to

$1$

where $$$sum[j]$$$ is the prefix sum of $$$a$$$. Then we can solve the problem by segment tree (since $$$sum[j]$$$ can be large, we need to sort $$$sum[j]$$$ first, and give them a new identifier from $$$0$$$ to $$$n-1$$$).

Update: Now my submission 192969220 has been accepted.

AC code of EObserve that the answer is equal to the number of adjacent points which moves toward each other.

We may check every two points $$$x_l,x_r$$$ and count the number of subsets in which $$$x_l$$$ and $$$x_r$$$ are adjacent and move toward each other, which is equal to $$$2$$$ to the power of $$$(L_{l,r}+R_{l,r})$$$, where:

$$$L_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l<x_l-x_p$$$;

$$$R_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l\le x_p-x_r$$$.

for a fixed $$$l$$$, $$$f(i)=L_{l,i}$$$ is monotonic. Similar for $$$R$$$.

The code for the solution above is very easy to implement.

[deleted]

Why are you not considering point which can possibly lie in between xl & xr in the subset? For ex: If x[]={1,13,14,20} and if l=1 & r=4, then by your soln ans would be 1 ({1,20} would be the only such subset), however there could be one more subset ({1,13,14,20}) as well, here also 1 and 20 would meet each other.

for {1,13,14,20}, although 1 and 20 meet each other, they end up in the same place as 13 and 14's. So it is calculated when l=2 and r=3.

Ok, so when two particles collide, they just stop there. I thought that the colliding ones just disappear!

It's the sum over all $$$(l,r)$$$ such that $$$x_l$$$ and $$$x_r$$$ meet each other

and are adjacent.Same approach. It is a miracle that this came to my mind during the time of contest. Finally i can see some improvement.

Thanks to this contest i reached specialist rating.

I didnt use DP. I just iterated over every pair $$$(i,j)$$$ and found the number of subsets of points such that $$$i$$$ and $$$j$$$ meet each other. The idea and code are both simple.

Code for DExcellent solution. Comparing to yours, my solution can even be regarded as wrong answer.

I see that you've used this header file

`#include <atcoder/modint>`

Is it supported in codeforces?

No, it is only available in Atcoder, not in codeforces. My actual submission looks like this

But the AtCoder Library GitHub repo provides a python script that takes a C++ file and replaces the atcoder header file with the atcoder library, enabling it to submit to all platforms. I also use the VSCode extension called CodePal which automates this process.

Thank you. I'll take a look

Can you please explain your dp approach for D . I tried doing this by dp but failed and my obervation skills suck , hence wasnt able to do the question the other way too.

We consider what would happen if we add a new dot at right. We call the previous 2 right-most dots i, j (assume there's >=3 dots in the set, because set with only 2 dots is trivial). In the previous set j would move left since it's right-most dot, and i could move left or right. If j still move left after we add a new dot, the number of final points will not increase. But if j move right, there's 2 situations: if i moves left (we call this situation LL), then it would like RR...LL --> RR...LRL, we can see there's one more final point (by the "RL" we've created), and if i moves right (we call this situation RL), then it would like RL --> RRL, where number of final points remained same. Therefore we can get the transition formula. (don't forget to consider situations of RL when there's only 2 dots in the set)

Also this DP approach need to store prefix sums for optimization. See this comment for a simpler solution.

Was D just a DP on pos[previous][current] then looping through [current+1, n) to try placing the next particle?

The observation there I believe is that for all values <= a[i] + (a[i] — a[p]), the direction is left, while the rest are right, so you can do some casework there to add on that subarray after precomputing prefix sums (the number of dots is equal to the number of adjacent RL's that show up in the final subsequence), but I had a stroke implementing ;-; does anybody have a simple enough implementation of that idea?

Wouldn't this be $$$n^3$$$ ? Each of your $$$O(n^2)$$$ values take some $$$O(n)$$$ time unless there is a trick I am missing.

I couldn't even get the n^3 working cuz I'm bad but I think that the recurrence would look like

Then since every single transition is just solve(i, j) + (a bool) in either case, then you split it up into the ranges whether the bool is true or false with bsearch. The second range never gets added to, and the first range you would casework and then multiply by the length of that range.

So in the end the transition is DP += (sum of everything from DP(i, [j+1, n) )) + (len of good range) * (caseworked boolean)

(though again I didn't get the casework working so I'll still need to work out the conditions)

Though it seems like other people had easier solutions ;-;

had a similar observation but could not come up with the implementation ;(

I have a simpler approach, iterate over i,j (i<j), for every i,j find out a,b such that a<=i,j<b and if every element between [a,b) is not present in a subsequence (except i,j) then $$$a_i$$$ moves towards $$$a_j$$$ and vice versa. Also, $$$b-a$$$ should be minimum so that we exclude minimum elements. Now add $$$2^{n-(b-a)}$$$ to the answer.

Code: 192957360

Let's assign directions to the dots in some subset, they will look like:

(RR...RRLL...LL)|(RR...RRLL...LL)|......|(RR...RRLL...LL)

So the number of distinct endpoints is the number of "LR" adjacent pairs + 1 (to account for the first block). So we can iterate on every pair $$$(i,j)$$$ and count in how many subsets they can exist as an adjacent LR pair.

Based on $$$x[j]-x[i]$$$, we can know how many dots before $$$i$$$ can be directly before $$$i$$$ in a subset and how many dots after $$$j$$$ can be directly after $$$j$$$ in a subset. If $$$[l, i-1]$$$ is the left range and $$$[j+1, r]$$$ is the right range, then the left subset counts can be $$$2^{l-1}$$$, $$$2^l$$$, ..., $$$2^{i-2}$$$, and the right subset counts can be $$$2^{n-r}$$$, $$$2^{n-r+1}$$$, ..., $$$2^{n-j-1}$$$.

So, add $$$(2^{l-1}+2^l+...+2^{i-2})\cdot (2^{n-r}+2^{n-r+1}+...+2^{n-j-1})$$$ to $$$ans$$$. Make sure to initiate $$$ans$$$ with $$$2^n-n-1$$$ to account for the first block in all the subsets.

Submission

B was much more difficult than C In B only case we need to worry about is n%20==19 but even after that it was more of implementation problem than maths which it seemed to be initially

you can solve B with binary search

Could you tell how please?

check my submission

codeNot required

if n%20==19 what should you do next?

Since the guy with more elo literally posted the same answer as mine and my comment is being ignored because of it, I might as well just remove it.

you're too sensitive for these things

Yes I am, because it's happened before. Good thing it was a 5 minutes comment and not a full editorial.

$$$B$$$ can be implemented simpler. Iterate over digits. If digit is even, split it equally for both answers. If digit $$$x$$$ is odd, add $$$x / 2$$$ to first answer, $$$x / 2 + 1$$$ to second answer and then swap them.

At the end remove leading zeros.

Example: 16934 -> 1**** + 0**** -> 13*** + 03*** -> 035** + 134** -> 1342* + 0351* -> 13422 + 03512

Feels like massive cheating on C, I might be wrong but it feels like it.

C is super easy to guess

Cheating is happening too much nowadays..

i guess it is for both B and C, B was much harder than c

how to solve C >

Approach to C

In what universe is B harder than C, only if you cheated cause code might be more trivial for C. To figure out idea for B it takes less than 50 seconds.

yes you maybe right but i am just saying what I felt was observation for C was easier to pick than B

for C if n=5 then

1,10 = 11 -1 2,7 = 9 -2 3,9 = 12 -3 4,6 = 10 -4 5,8 = 13 -5

if we see 1,10=11 next big numbers can be 12,13 since in -2, 3-1=2 and 9+1=10 we compensated for that 1 similarly this can be seen for other cases

but if n%2==0 there will always be a pair such that its sum is repeated in other pair

I am also feeling this

I think , There were not much difference between level of B and C .

SpoilerB was an implementation and C was Observation + Implementation.

What is test 2 for B?

maybe 1999 3999 59999 ....etc any such

i think it could be 100,1000,10000 etc

i think its easy to guess for these nos n/2,n/2=> {50,50},{500,500}....

different emplementation

guessforces

more like observation forces

Kinda solved problem C by guessing. You can calculate the first number in the sequence s through math. Iterate over all possible odd numbers first, then iterate over all possible even numbers. This apparently works, but I would be interested in a proof.

Any proof for C I solved it by just some observations

if n is even then "NO". else sum of first pair should be (3*(n+1)/2). proof: S1 + (S1+1) + (S1+2) + ....... + (s1+n-1) = 2n*(2n+1)/2

The worst round

I also wanna say this... but to be honest the problems are fine and I'm just unlucky.

For me too :(

why? D was alright but maybe D > E. I guess A,B were easier than usual for sure.

Imagine asking how to solve D and getting -13 ^D

It was great PatternForces Round <3

I wish C was 1500-1600, but unfortunately it's more likely to be 1200

How to solve B? please somebody help.

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.

Anyone know why my sol for D is wrong?

dp[i] stands for sum where i is chosen, and tot[i] is total of chosen & not chosen

anyone tried to divide horizontally for problem B ?

Woohoo, my best ever contest :)

After a very long time i was able to solve only one question. Best contest of my lyf (T_T)

I wast stuck in problem C for approximately 2 hours, In problem C multiple kind of pairing was possible so it must be mentioned in the question that we can output any valid answer. I am not talking about order of pairs... actually you can pair any number with 2 values and accordingly I found 2 valid answer exists for each odd number.

Always two problems.Can someone tell me how to train to solve problem C?

the idea is that we find the sum of 1 and 2n and store it, for example, in set(). it is clear that now we will not be able to take the sum of 2 and 2n-1, so we will make a "shift on the right" and take 2 and 2n-2 and mirror the "shift on the left" by taking the sum of 3 and 2n-1. then we need to apply this algorithm to the end, increasing each time the "shifts on the left and right" by 1 (that is, the next two sums are (4 and 2n-5 ) and (6 and 2n-4). it is not difficult to make sure that for even n the answer will always be "No", and for odd n it is possible to split the permutation into pairs using this algorithm (but not for all odd n there is a solution, for example, for n=11 there is no solution) upd: it remains only to be able to carefully remove pairs from the permutation :)

Thank you:). I know it is impossible for even but i spent 50 min to think how to construct the pair .

Not at all! Good luck with C :)

I just would like to say that I didn't fully understand the problem A, could someone please explain it more or provide me more test cases with explanition?

I feel that this round's first problem is a little harder than before.

Thanks in advance.

To think what is useful for multiply

Any Hints For D? I Was Thinking In A DP Direction :(

the main observation is that the distinct points increase when $$$ith$$$ index moves left and $$$i+1th$$$ index moves right. Now try to figure out the contribution of each $$$i$$$ seperately by fixing the position that moves left and the position that moves right.

great contest. for the first time there is no feeling that after B I can't solve anything. this time there was such a feeling only after task C!

Toooooooooooooo much Cheating

Why do you think so?

I haighly agree.

Hello

Can anyone explain E for noobs?

Why is answer no for even n in C?

s, s + 1, ..., s + (n — 1) are sums. So s * n + n * (n — 1) / 2 = 2n * (2n — 1) / 2, so s = (3n + 3) / 2 => n % 2 == 1

Looks like I need to get some sleep. Thanks tho

s, s + 1, -- s + n — 1

suppose they are sum of pairs as given in problem

if we put

s + s + 1 + s + 2 — = 1 + 2 -- 2n

we get

n * s + n * (n — 1) / 2 = n * (2n + 1) we get

s + (n — 1) / 2 = 2n + 1

s = 3 / 2 * (n + 1)

for s to be integer n + 1 should be even

you can calculate the first sum is (3*n+3)/2 if it is a int ,it is impossible for even

see this patterns

An unbalanced round. I got ABC very quickly, but couldn't come up with a fast enough solution for D in time and didn't attempt further problems. I won't say that the problems were bad because they weren't (C was just guessing a pattern, didn't like it that much; others were good). I just think that there should've been a 1600-1800 rated problem between C and D. But the round was still nice.

yea, I agree. Maybe A,B,C could've been made slightly harder to ease up the gradient.

very fast ratings update.

Actually had more trouble with C than F haha.

solved D during the contest, but forgot that modular arithmetic template takes $$$O(\log n)$$$ to calculate $$$2^n$$$... So got TLE couple of minutes before the end after simply rewriting formula I got on paper :(

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

upsolve submission: https://codeforces.com/contest/1788/submission/192968394

Great contest with good problems , thanks!

Empty

Great contest, and super fast rating changes, wow! Absolutely loved all the problems that I read (A-E)!

Also, while I understand the need to have tight TLs on D, as $$$n^3$$$ solutions were to be rejected, I'm slightly irked by the fact that my Java submission failed despite being $$$n^2log(n)$$$. Anyway, that was to be expected since I was using TreeMaps, and Binary Search is understandably faster. So yeah, happy to have learned one more thing :)

Great contest with very clear statements!

ok thanks

The product of the array can go up till pow(2,1000) which is way too large to even fit in long long

MakaPakka ranked? yeah very credible lol

Ac submissions at the last second is very nice , but i am pretty sure that last second submission of problem D by gsmdfaheem is copied. i have seen exact same code that is leaked at just 10 minutes before the contest end.

he just changed the variable names.

ChannelLeaked-CodeHis submission at last secondIn B if i print 1 as 01 it consider it wrong but both are equivalent integers and no intructions are provided regarding leading zero .

stupid testing got WA 2 times.

According to me my E is working but my solution gets WA on test 5 can anyone please help me where i am lagging https://codeforces.com/contest/1788/submission/192944044

Take a look at Ticket 16725 from

CF Stressfor a counter example.## help

For problem A, why are the prefix and suffix methods giving me WA?! I was multiplying pre and suf values and then checking for every position i if pre[i] == suf[i+1] (For i=1 to n-1) or not. I Got WA this way.

well, if i understand you correctly you multiply numbers in the array which may give you overflew since assume if n = 1000 and all elements will be 2 then you have 2 power 1000 which way too large to store in c++

yes, i had quite a hard time solving this but i figured that i could change this into a prefix sum problem instead. i was able to solve it using prefix sums by converting each 1s to 0s and 2s to 1s. truth be told it was not efficient. good luck to us next time!!!

Problem D:

First I identified what are all the possible co-ordinates that all dots can end at. This is a set containing the mid point of every possible dot pair of array. Now we just need to find out in how many subsets each point in the set can appear. I found this using binary search.

Implementation of D

GOT

ACLAST SECONDD just 3 seconds before!!

The time limit of F is too tight. I wrote the correct solution but got TLE on pretest 58. I think it's better to decrease the value of $$$n,q$$$ to 1e5 or increase the tl to maybe 5 secs.

Problems are fun! thanks to authors :)

i am depressed, what time can i get a color name.

Can someone give a small test case on which my solution 192923926 fails?

Take a look at Ticket 16724 from

CF Stressfor a counter example.Very very very standard problem E and F. I cannot accept that.

Weak testcase in B no.In the statement, given1<=n<=1e9. Unconciously, I usedint(as datatype) and passed the pretest. After the contest I noticed my mistake and expected to get wrong answer. But, after final judgement ,my solution passed all the testcase:)192907426

What do you think range

`int`

has in GNU C++17 7.3.0 (your used compiler)?You can always check in Custom Invocation smth like this:

My bad. I knew, int support around 10^6. But, I'm wrong. Thanks for your kind information.

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!

Hello! I submitted two implementations of treap in E, and the "faster" version works 5 times longer! Can anyone explain it? "slower": 193052447 "faster": 193052503 I know that "faster" gets TL on a test with

`a = {0, 0, 0, ..., 0}`

, but I can't realize the reason of`O(n)`

height of a treap.hopeforces

Problem B. Sum of Two Numbers ***** my solution get wrong answer on test case 8, my solution is true and that makes me sure that I take this code copy and submit it again and get accepted, plz check it for my. the solution which gets wrong answer during the contest the same solution gets accepted after the contest !!!

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]

Today I receive a message that my submission dusanesaksham14/ 192925696 is same as sakshamsdusane/ 192924170.I checked it and i think the the basic algorithm used in both the codes are same which might be used by many one. It is just a coincidence and nothing else. My template used in every question is same and that can be noticed. This might be happened due to ideeone.com as you have already mentioned. I have submitted code for B wo time, → 192925185 & → 192925696 , and both time you can see i have used same template. This is just a coincidence and nothing else. If needed i can give more evidences to validate my code.

please do needful

Thank you

About coinciding the solutions: Sorry about that. Both 2020331034_Jahid and Quintessential are my handles. The first one I use for academic purposes and the second one is for practice purposes.

About coinciding the solutions: Sorry about that. Both 2020331034_Jahid and Quintessential are my handles. The first one I use for academic purposes and the second one is for practice purposes.