Hi, Codeforces!

I finally get to return something to this great community, so I am glad to invite you to take part in Codeforces Round #703 (Div. 2), which will take place on Feb/18/2021 17:35 (Moscow time). The round will be **rated for the participants with rating lower than 2100**. Participants from the first division are also welcomed to take part out of competition.

You will be given **2 hours 15 minutes** to solve **6 problems**. All the problems were created and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

I would also like to thank:

- antontrygubO_o for excellent coordination!
- Monogon, 3EVEHAR_KOAVA, Akulyat, Aleks5d, BRCode, Osama_Alkhodairy, PO3OBAR_Bblnb, arzhantsev64, bWayne, Aditya_Mittal_31, kassutta, kclee2172, kalki411, sdl for testing the round and giving valuable feedback.
- Aleks5d for proposing another solution to one of the problems.
- MikeMirzayanov for great Codeforces and Polygon platforms!

Scoring: $$$500-1000-(750+750)-1750-2250-3000$$$.

Don't forget to read ALL the problems. I wish you good luck and high ratings!

I tried my best to create some good problems and clear statements, so I hope you'll enjoy the round:)

**Story**

**UPD:** Editorial

**UPD:** Winners and First to solve

Div1 + Div2

Place | Participant |
---|---|

1 | renascencepjw0510 |

2 | dlalswp25 |

3 | Bohun |

4 | kmjp |

5 | theodor.moroianu |

Div2

Place | Participant |
---|---|

1 | renascencepjw0510 |

2 | Quirrel |

3 | YuuKoito |

4 | _Nyusha_ |

5 | JackF |

First to solve

Task | Participant |
---|---|

A | king_of_tt |

B | IgorI |

C1 | dlalswp25 |

C2 | dlalswp25 |

D | Omer223 |

E | lulzz |

F | JackF |

As a tester, I must say problems are really interesting !! Good luck to all :)

Oo maa go TURU SPOILER

I will not trust you again.

Problems were interesting (that idk) but till now I don't have any proof of solution of problem B!! I was submitting all the different possibilities and one of them passed :)

My plan succeeded! Now I will always be the lexicographically first tester!

Indeed, your plans are beyond someone's imagination

As a tester, nice to see Monogon as a tester.

Hmm.. I'm sure that after you have posted this, at some point of time a user will make his/her name "1-" thus foiling your plans.It seems unlikely that such a scenario will ever occur, but let's wait....:)

we love to see your name in the first place.

Here is some suggestion that you should choose as lesser ASCII value as possible like this one -is-this-fft- can challenge you for first place. Just saying.

We want cf round from you :)

Unless...

i am wondering why there is no 0-gon

Did he really thank Anton w/o any jokes? :upside_down_face:

PictureAs a tester, good luck. You would need it.

Is it that hard?

Just me trying to comment something different for all the rounds I test.

This statement seems like a challenge

Now I know why you said

You would need it.;-;Whenever authors recommend reading ALL problems...Looking forward to go gray in this round. This green is off-putting.

Chance for master xD

good luck!

All The Best. And, My Chance to become a Specialist xD :(

As a fellow victim of antontrygub I wish you a speedy recovery after the round

As a

You're liar!!!!!!!!!!!! YOU ARE hUaAnS

I request authors to disclose problems rejected by Anton.

+1

They are just waiting for the coordinator to change and suggest them again;)

I request authors to stop making contest for a while.

okwedook Is it blue tears in ur pfp after rejection of 29 problems by Anton?

What's pfp? And why blue??

OMG, I've googled it. It's a nice assumption, but the photo was taken before any rejects:)

And there is some intention behind having that blue tear :P or I am just overthinking by seeing it?

Yeah, you're definitely overthinking;)

Even you reposting your memes

I just saw this picture and felt it fits it more and it's not a problem to repost 1 year old meme so many could not have seen it and that's not the first time I repost a meme

Howdie! Detective want some real coke?

true :XD

The KING of Ad-hoc is back again as a coordinator!

This is his 1st round as a writer, isn't it?

OMG 29 problems were rejected !! Can you share some of them after contest?

Scoring shows 7 questions but you said there will be 6 questions.

What is correct?

I think Problem C will have both an easy and a hard version.

So they are counted as one question? Okay, got it

"My

first message from message fromMikeMirzayanov was more than a year ago!"Shouldn't that be "My

first message fromMikeMirzayanov was more than a year ago!"?Or is it a message from a message...:)

I never get to figure out why some comments receives upvotes beyond imagination, while mine are always downvoted :(

I read the same statement twice but couldn't figure out "message from" was written twice. I uncounciously skipped the duplication

If Anton would have been rejecting

`29 problems in 135 minutes`

of the contest time that would make "a speed of rejection" almost about a problem every single 5 minutesMemeProblem D: Anton and Rejection

This will also get rejected! xD!

answer may be very large, so compute the answer modulo 1e9+7

please tell how to solve "C" after contest:) Update::first tell how to solve "B"

sometimes i feel like how life would be if i donot get downvotes!

Please notice the unusual Score distribution. i.e. it seems that C1 will be easier than B.

I wouldn’t infer that. It could be true, but I find it more likely that the problem as a whole is 1500, and if you can only solve it on reduced constraints you get half marks.

C is interactive. Change my mind.

I have some questions:

1- Can the rejected problem be modified and proposed again?

2- If not, can we have rejected problems in Gym added by setters?

As you know, if the problem was rejected, then it is not prepared, because why

Hope I get my green shade back this time

Score for problem C is 750 so it means it will be easier than the problem B (having score 1000)?

problem C will be an interactive problem

I too think so

note:

unusual durationXDMeme![ ]()

...

I hope you didn't set all math problems

Why I am not improving !!!?

Getting you have submitted the same code, but I haven't made any submission!!

Got same problem. And now i am sure that i just banged my head by giving this contest.

I'm not sure what' happening. I can't seem to send a solution for A. It always says I have sent this solution before, but when I look in my submissions I don't see it. I don't see anything. I have tried putting random stuff in it, I have tried from another browser. Nothing.

I'm having the same problem... Can't submit anything.

make an empty loop ... i think it will work

IF I ask more than 40 queries in problem C1, what error will I get? I am getting TLE. I want to know if its due to asking > 40 queries.

You can't it will be a wrong answer you are supposed to find it in 40 or less

I really appreciate the efforts behind setting these problems. Everybody knows it was interesting. However all the problems starting from A were of a slightly higher level than usual. I understand the need to set interesting problems. But div2 is literally the most frequent round that is held, which means it needs to be catering to most ratings atleast for the first 3 problems. In that aspect, I am forced to think this round was a failure. I might be just another noob but I have only solved the first problem. But I know for a fact that the rest weren't the same level as other div2 rounds.

Its time to leave earth (after seeing problems). Bye guys! Anyway problems were interesting :)

I wonder why antontrygubO_o didn't reject all of your problems :(

that's rude :v

Not more than problem B :'(

Your inability to solve a problem doesn't make it rude!

I am sorry. I got carried away. I will be waiting for the next round by okwedook to perform well.

+1

Problem D looks similar to this

Nope.

A& B look like :

lol agree

DifficultForces :(

After seeing the problems I am sure why @antontrygubO_o rejected all your questions last time (that was really a nice story). Ok but as you told the questions were really interesting. "! But you should be in between the difficulty level of div2 !" Very first time I am seeing that the contest blog page upvotes are decreasing after and during the contest.

+1

This particular comment didn't age really well:) Just practice more and you'll get to solve more problems

what is pretest 5 for c1?

Pretest 4 for E?

damn, what's test 7 on D?

ONCE AGAIN EASY D (1750)

What's the approach, my sol gets WA on test 7

as a youtuber, here is the video solution to problem C2: https://youtu.be/TvosdMg9GXE

submission link: https://codeforces.com/contest/1486/submission/107881420

![ ]()

better than

I bet all of my life on E, farewell everyone here!

Well, I learned that an array of 1 elements is in increasing order the hard way

Please help why i am getting compilation error in C1,C2 ? i think my code is fine , help needed ?

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

## define LL long long

using namespace std;

const LL N = 1e6 + 10; int n; int Ask (int l , int r) { cout << "? " << l << r << endl; int res; cin >> res; return res; // fflush(stdout); }

void solve() {

}

Correct me if i'm wrong but isn't that comment in

`// fflush(stdout); }`

including the brackets?No dude it only comments fflush not the brackets !! what is my mistake can u tell me ? it is showing compilation error u can go to my profile and check the whole code !!

There isn't a

`;`

after`int res = -1`

edit: there is also no main functionohh , fuck thanks dude !!

no dude , it did not resolve the problem again it is showing the compilation error !!

Try to read your code carefully, you need to add the main function

Will binary search on BIT work in problem D ? Gave wrong answer on test 4

How to solve B?

I thought iterating $$$x$$$ in $$$[median(X_i) - 100, median(X_i) + 100]$$$ and $$$y$$$ in $$$[median(Y_i) - 100, median(Y_i) + 100]$$$ would suffice the solution.

Exactly my thought too, tho instead of median, i did average, and from -5 to +5

an easy hack against your solution, n=2 points at (0,0) and (1000,1000) the whole square is solution.

Reading the problem D: Aha! A similar problem, just use the sliding window medium

Few moments later: Why I always failed at pretest 7?

Happened to me too

Same, also fall into that trap. For those who want to use a dynamic size sliding window, you can try this test case

Damn I was just able to solve E theoretically with like 2 minutes left :((

Can someone tell me if this is the solution? You build a graph with V_even and V_odd. You run Dijkstra, but instead of updating the the distance of V_odd, you simply add all the options of parents to it, together with the weight of the edge and the weight of the last edge. Then when it's Vodd's turn, you go over all it's neighbors and choose the best combo of path + (edge1 + edge2)^2. The problem — it runs in m^2. The solution —

w_i <= 50 so you don't have to save all the options, just the best option for every 1<=w<=50! then you iterate over all the neighbors at most 50 timesIs this the correct solution?holly shit I got WA on pretest 2 on A don't know why then I jumped to B and didn't know how it could be solved then jumped to C and got TLE on pretest 4

I wish my meme is true cause I will lose 170 rating ugh that hurts

you can check for this test case: 5

4 2 5 1 3 this will be taking more than 40 queries for larger n

damn I didn't have the time to think about this cause i submitted in the last minute

Holy shit, feel you bro. Can't still understand why sum>=n*(n-1)/2 ? "YES" : "NO" will give the wrong answer on test case 2

Consider the array

`0 0 6`

. The sum is >= 6 but because we cannot move blocks leftwards, we cannot make it strictly increasing.Your code will fail on the following test case: n=5 1 1 0 3 5 You should check sum>=i*(i-1)/2 on every index or try a different approach.

For problem D, this was helpful https://codeforces.com/blog/entry/21103

If you are need a test case that break your solution, these may help

And I foresee problem D will become yet another coding interview question.

Yeah for D, you can also have a look at Edu binary search step 4

The second test case's N should be 11 not 4

Oh yes thank you

Why am I getting idelness limit exceeded? 107863650

try using cout.flush()

But I flushed the output several times and also used endl...

Sorry for bumping but I can't really get the problem that the solution gives idelness limit exceeded

I guess it's because endl has a flush effect. try #define endl '\n' on the top of the code

People like me, who had seen Cf Edu Binary Search step 4, can easily get the intuition for D. Loved the problemset. D was savior.

Can you please give the link of "Cf Edu Binary Search step 4" , which you mentioned ?

(Beacuse , I want to read that first before upsolving D )

https://codeforces.com/edu/course/2/lesson/6/4 it's just in the menu above

B killed me

Problem D is exactly the same as this one

For problem F, you can copy this code (statement: calculate how many pairs of paths intersect with each other) and 1336F - Путешествия then subtract the answer from the previous one.

Implemented some simple brute force in E which passed in ~800ms, now assume systest will make it fail. How to correctly solve E?

time limit is 4 seconds . Why it will fail ?

I am basically iterating all paths of len=2 and build a second graph from that. That feels to simple to be the right solution.

It should ideally fail, consider any star graph, that will give you $$$O(n^2)$$$ edges in the new graph.

Yes. Funfact, it passed the systests, so I got the nice plus delta, then later was hacked ;)

Your first solution to E was skipped on main tests. What is it why does it happen?

It didn't failed ;) . Was that due to to weak tests ?

Yes.

How to solve B?

I know it's lame to ask... but please, any short solution would work.

Try plotting some random points on Desmos or some other tool and brute force the answers. You'd see the pattern.

I tried proving the solution for an hour, gave up and this seemed the only option left. :p

Noiceee!!

I can give you a hint if you want. Ia a rush rn.

It's related to median. For both x and y coordinates.

Yes, I know that relation, but wondering how wd that be useful here.

Problem B is a 2D problem which can be broken down into two independent 1D problems. First, minimize the sum of |xi-x| and then do the same for |yi-y|. The median of an array comes into play here.

For array ai .... an, you have to choose a value k such that summation of |ai-k| is minimized. This can be done using median. You can apply it to the above 1D problem.

It is a very vague explanation but hope this helps !!

Thanks a lot!

C was a really nice use of binary search. Hope pretests were strong enough.

Someone please tell me why my solution is wrong and the other solution is correct. http://codeforces.com/contest/1486/submission/107798098 http://codeforces.com/contest/1486/submission/107782432

In your submission, you do:

so you break early before you finish reading all of the input. Because there are multiple test cases, the input then spills over to the next test case, and everything gets messed up.

Thanks a lot, Finally understood my mess after submitting it almost 4-5 wrong submission. :-:

Your handle is also "smax", are you the author of Problem C1 and Problem C2? hhh...

For B question .. why does the count from avg-1,avg,avg+1 fails ?

Average is not a correct answer to get minimum distance. For example, if we look only on X-axis and points at 0, at 4 and at 4 again, the average of them will be 8/3~2.66, but the best point to get minimum distance will be 4

sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )

In any case we need to use median instead of average. Lets imagine, that we have array of

`N`

different points and`N = K*2 + 1`

(just to make the explanation easier).Lets then pick median of this array as point

`P`

and calculate total distance to all points, it will be some number`D`

. We may notice, that`K`

points are to the left of`P`

and`K`

points are to the right of`P`

. Denote distance to points to the left of`P`

as`D_left`

and distance to points to the right of`P`

as`D_right`

. So`D = D_left + D_right`

Then look at neighbour point

`P - 1`

and calculate total distance:So by picking any other point then

`P`

we will increase total distance.Got it !! Thank you so much dude :)

i handled the repeating cases separately

Take this array as example

`[2, 2, 11]`

. The avg is 5 which results in a total distance of 12. But if you use median instead of the avg, you definitely would get a better result. In this case when you choose 2 (which is the array's median) instead of 5 the total distance will be 9, which is better than 12.sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )

i handled the repeating cases separately..

`[2, 3, 1000]`

your ans: 1330

correct ans: 998

The median is an optimal choice, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger then the median, the sum becomes smaller by decreasing x.—CP handbookThank you so much :)

This is the first-ever time I got an idea on how to solve Problem D, to know the median in constant time we can use two heap approach, I made the window as two heap's and each time I move the window I insert an element into heap O(log K) time, but I don't know how to remove a random element from the heap in the logarithmic time since while sliding the window we need to pop the 1st element of the window each time. so I went by removing elements in O(K) time, but went with TLE in Test case 7. can someone help me on how to remove random elements from the heap with less complexity or any other better approach to solve the D problem?

Attaching my Python Solution. MY solution in Python Using Two Heap

If codeforce were kind enough to accept sortedcontainers you could use SortedList. Also I think your solution would only return the maximum median of subarray of size exactly k and not at least k. so on n=5 k=2 a=2 1 2 1 2 your algorithm would answer 1 instead of 2 if it considers subarray of size 3.

I once wrote a simple class to maintain a median, where you can add and remove values in O(logN). see this submission

Memory limit exceeded for using map in problem B. Anyone, any trick to modify this code to avoid MLE. I used map for storing the visited points in a recursive function.

Le me after this round -

Спойлер...

Poor me created 5 cpp files for the contest and I only solved A (-_-)

What is the failing case for this submission? https://codeforces.com/contest/1486/submission/107861220

Test with array $$$[1, 2, 3]$$$:

Yikes! I did try [1 2 3 4 5] during the contest, smh. Thanks!

Edit — The one I submitted before this didn't have this problem. Can you think of some case for this one too? https://codeforces.com/contest/1486/submission/107847201. I tried to come up with something by myself but couldn't.

With array $$$[8, 9, 6, 7, 4, 5, 2, 3, 1, 10]$$$, you get the following:

Can you see the pattern? If I use a larger array with the same pattern, you will definitely exceed the query limit.

Yes I get it. Thanks again!

Before realising the intended solution to E, I was thinking about using Convex Hull Trick to optimize dijkstra in the following way. If I am at some vertex $$$u$$$, for every edge $$$(u, v)$$$ I insert into the convex hull data structure (initially empty) the line $$$mx + c$$$ where $$$m = 2 * w(u, v), c = dist[v] + w(u, v) * w(u, v)$$$. After inserting all of them, then for each vertex v I do $$$dist[v] = min(dist[v], w(u, v) * w(u, v) + query(w(u, v)))$$$, where query is the usual query for the convex hull trick data structure (returns the minimum function value) and $$$dist$$$ is an array containing the answer for all the vertices. I think implementing this directly in dijkstra won't work for a variety of reasons. I wanted to ask if there is any way in which we can use this trick to solve this problem for arbitrarily large edge weights (say $$$1 \le w \le 10^9$$$).

.

In problem B "sum of distance" instead of "summary distance" would have saved time of both setters and participants .

Wow!

What a wonderful contest! It made my day

`:D`

Can D be solved using ordered multiset and considering the subarrays of size k only? like this,

CodeI think it will fail on test 7. I did the same approach

3 2 2 1 2 actual answer is 2 your answer is 1, but it I still wonder if you consider only k and k+1 if it would work

I ran the same approach for k to k+10, it passed test 7 but it failed test 8 then

I found https://stackoverflow.com/questions/55785883/how-to-calculate-the-maximum-median-in-an-array, which proves that subarrays of 2 or 3 are sufficient when k is 1. However I don't think that proof generalizes to a constant number of subarrays for an arbitrary k, you need at least 2k or 2k + 1 to apply the same logic used in one of the comments.

Impressive, Qzy___ solves B on 0:11 (107793144) and D on 0:12 (107794288). How do you guys do it with such difference in the code style? Do you keep two different templates for some reason?

107793970

Where does my solution fail in A. Can anyone help

Your early return causes issues since you still need to read all $$$n$$$ integers.

My goodness!!A contest could not be worse

why the brute-force is passing problem E????

Answer for problem F is the number of path pairs that intersect at least one edge minus the number of path pairs that intersect at least one vertex

Can someone tell me whats wrong with this solution for problem A: https://codeforces.com/contest/1486/submission/107836476

You are answering before reading the whole array.

Oh my god, how could I be so dumb! Even failed system tests for C1, Bad day!

Happens, you can tell this incident here

Brothers!!

The pretests for A were that good, that there was no test where submissions without long long would not pass. Good job!

How do you check how many solutions FSTed? Is it through the status tab?

On standing page, on the bottom.

I hope I promote to pupil :D

I hope I promote to expert :D

Please release the editorial.

Which was the point of E? It was just an easy and classic Dijkstra.

The system test is TOO WEAK.

I also thought so.

The official can tell me why my code was skipped for C1 question, I didn’t give anyone my code.

Your submition skips when you submit another one that passes pretests.

Today I learned a lesson — don't participate in a contest while sick with (probably) COVID-19. :)

For the first time, in my room no solution failed system tests!! Thanks for strong pretests!!

Well, it's easy to make it appear like there are strong pretests when systests are absolutely garbage :)

Deleted

c1 should have larger amount of queries, my code was right but i did not bother to do a simple optimization on queries as there was already a c2 with less queries.

Your mistakes should be fixed by you, not by problems setters.

Yes, sorry i agree that it was my mistake, but c2 with less queries just messed that thing in my mind.

How can a $$$O(n \times m)$$$ solution pass the system testing (or even the pretests) on problem E?

This is the submission. Clearly two for loops.

107866037

له له له

I think Problem C1 and C2 are just like one problem? I can't feel the gap between them.

In C1 you can perform two queries in each iteration of binary search which gives a simpler solution than that for C2.

OK. As it seems someone really tried to make weak pretests. There was so obvious error in my code. And I got pretests passed. What's the point of giving feedback, if obviously wrong solutions pass pretests? just look what have I written: "if(ans==ind)r=mid,l=mid;" and it passed pretests. I will worry about my rating, but it's funny

E should be retested.

Can anyone tell me what does the Error in this solution means https://codeforces.com/contest/1486/submission/107864397

, And can someone give me one TC on which this solution fails. Helping in even one would be highly appreciated . Thanks in Advance

With array $$$[1, 2, 3, 5, 4]$$$:

The last query shown above is invalid, since the subarray needs to have at least size 2.

Is this the Error that the CF judge has also mentioned BTW Thanks for your help

I made a stupid mistake and used k+1 instead of k in D, passed pretests, but failed in system testing:(

And I went all the way from Rank 3 to Rank 23:(

Looks like you a red coder in your main account.

E should be retested. There are codes that solves E by making a M^2 edges Graph

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

The problems were really interesting!

Kudos to the authors, and the coordinators involved! :)

okwedook MikeMirzayanov I would like to request a rejudge of E because the judge behaviour is inconsistent: 107850881 is TLE and 107877393 is AC but both are the same code (you can check with Compare)

UPD: of course, the algorithm itself is not randomized in any way

This comment might be able to explain the mentioned judge behaviour.

I understand why this may happen, but I think that it is not my problem if the CF server was a bit slower in one of the runs. The behaviour should be consistent because, if I understand the situation correctly, I passed the pretest during the contest and failed the same pretest afterwards. This is clearly unfair because I was lured into the fake sense of security by 25! strong pretests, and (based on the "passed pretests" verdict) decided not to optimize my solution further during the contest not to lose points.

You passed pretests with 3992ms. And then decided to not optimize further? Sorry, but that is known to be no good idea.

When I see such execution times on a high number of pretests, I think "oh, they must be quite strong". Regardless of what I think, CF cannot implicitly assume that I should optimize my code whenever I see high execution times on pretests because I may fail the same test later.

Well... CF can. And does.

Ok, after a bit of thinking I came to the conclusion that rejudge is not a good solution in a long run, and my best idea so far is not to re-run the pretests during the system testing. This way my argument about inconsistent behaviour will not be as legitimate.

wrong answer Integer parameter [name=query_r] equals to 27671, violates the range [27672, 99999]

Could anyone please tell me what this means? I got this for C1

I too had the same error , it means that in a query , your l and r are equal

Great question C2 really liked it

what a great set of problems. thank you and thanks to the coordinator for rejecting the other problems.

very weak test cases in C2, E....

I am getting runtime error on testcase 6 for the E problem , here is the link of my submission , can some one please check it!!, What I have done is kept n*51 states and edge of weight 0 between (u,0) & (v,w) , edge of weight (a+w)^2 between (u,a) & (v,w) , for the edge u,v with weight w given in question, I applied dijkstras on transformed graph..

Strange

See This blog

Thanks

i whink DE is a bit too easy for its position, D ia a sinple binary search and E's dijkstra solution is O(m log 50m)

maybe better if put them in CD and get a harder problem for E

For problem E, O(NM) passed system tests. The hack cases can be generated easily with a simple source. It's amazing that the system tests didn't had any hack cases for the O(NM) solutions...

Can someone help me to find what's wrong with my solution for Problem A ? 107831213

You are not taking the complete input.

see this : https://codeforces.com/contest/1486/submission/107900253

the approach discussed in Question B can be extend to 3D plane also ?

Yes, any number of dimensions. They'll all be independent.

Can someone elaborate how you all are creating graph before applying Dijkstra?

I am observing about a 2x difference between the runtimes of two solutions, by just changing the way I am indexing the array. I understand that this is because of different localities of reference between the solutions.

Yet, I am not able to figure out why one of these has a higher locality of reference. If someone can help me figure out the same, it will be greatly appreciated.

These are the two submissions: 108047029 108047388