**Unfortunately, due to Internet provider network issues, we have to postpone the round. The current plan, that the round is postponed by 24 hours, will start on May/05/2021 17:35 (Moscow time).**

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #719 (Div. 3) will start at May/05/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 7 problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and Aris.

Thanks to Gassa, BledDest, Programmer, bugdone, ruban, RedAnt, songsinger and Gornak40 for help with testing the round.

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

Editorial is ready!

Most awaited round of the month.

wow how ironic now that the round is postponed.

My first rated contest pretty excited :)

First rated contest with a new Alt? :P

as I am a beginner, my friend suggested giving div 3 as they have some easy problems, so waited for a div 3 :)

My first unrated div 3 :)

All the best!

Everyone !! Did any Rating changes occurred I am unable to see any rating changes for me, So here I am asking ! -_-

Same here, and even it is showing in unrated contest in my profile

however I am on official standingsCan't wait for rating changes.

Until rating is actually credited/debited in your profile, Every contest is shown in unrated.

thanks, I was really confused

They just did another system testing. Wait for 2 hours now and hope no more system testings.

Tom's smile always kills me LOL : )

Tom's movements and expressions are best ngl xD

do it again,contest postponed :P

What about ratings. been staring at screen since morning

Sorry but I don't really understand the trusted rules :( Does that mean I can't use clones?

Div. 4 when?

What is div 4 ?

Does a contest always mean solving hard problems :)? Even a div. 4 contest with easy/tricky problems can be fun at times.

What I think is, coding is not always about solving hard problems, let there be fun.

I can't disagree, but what's the point of solving easy problems if they don't bring you any benefit, just a waste of time? is not it ?

I think solving easier problems(which we can solve faster), can be a really good warm-up.

Sometime when I feel dull, or like I am unable to perform well, I go for solving some easier problems. That really helps in gaining pace.

Where do such good arguments come from?)

yes, agreed but most of the people asking for div 4 are generally doing it just in hope of positive rating.

nice argument

++++++

Funny calling him noob when he has a rating higher than you.

Why did you get downvoted ur saying facts

I didn’t call him a noob, I asked him

The power of the edit button

300 iq )

Really excited for my second contest , hoping i would cross 1000 this time. Any tips are welcomed. TIA

Enjoy beauty of contest, never think about rating and never go for cheating.

thanks buddy, really a well defined ans.

You did really well in your first round, you will soon be in top trust me. I still struggle to get above 6000 rank. Hoping to get better with future contests.

WTF! You solved 4 in Global round and still got a positive delta of only 600?

sed lyf bro.

how to become red coder in 1 month???? any tips and tricks???

Yes, just win every contest you step in and you'll be red within a month

Wait for January 2022, you will don't have to wait a month, 1 sec would be good enough. xD

why, what will happen then?

Magic!

Codeforces allow user to change the color of their usernames every New Year,it called "Magic".

Then, we see some grandmasters with 8000 rank LOL!

And they solved problem G

I became a LGM in January and posted on social media just to baffle my friends.

start in December and when new year comes, they will give you an option to change your color for few days. That's my secret of becoming a red coder.

yes, there are two ways either you paint your laptop screen with red colour , or solve 3000 plus questions in a month ,lol

Few years ago，when the initial Rating was 1500,LxL became gold only after three div.2s.

Becoming red in 1 month? Just go to bed and have a good dream. There is everything in dreams.

My chance to become a pupil

solve 3 problems in tomorrows div 3 contest...u will surely reach pupil

Hmmm, why aren't we seeing vovuh as a problem setter in recent div.3 contests?

I hope he's not COVID positive in these uncertain times.

Stepavly contests are like the old DIV 3.5, Vovuh DIV 3's were, indeed, a bit tricky especially the latter problems.

Hope to see a cool problemset. Best of luck, All.

As a tester I can assure you the problem set is cool :)

Also be sure to read all the problems. Setters often write this, but in Div2 I think most of the time the last problems are really hard. But for Div3 I think it's really worth doing it (at least reading the first N-1 problems in a N problem set).

Looking forward

why doesn't this comment has the number of upvotes it deserves.

Hmm note that testers are usually part of conspiracies. So the N'th problem could be the easiest, we should try to solve that first.

Looking forward to the contest, hoping to learn some new concepts :)

Can i become pupil after this round?

One more new author of div 3 *o*

Hope I become pupil again

I still remember the time when vovuh was a coordinator of Div3, it has been so long.

*has, try improving your grammar. Would really go a long way in interview preparation.

try not correcting others' grammar errors. would really go a long way in your interview process if interviewer's grammar isnt that great:)

please schedule the contest 1 hr earlier as it perfectly ends before dinner and good discussion time before going to sleep

You don't know how many time zones in the world, do you?

most of the contestant are from india i guess :}

Then...?

This request is the perfect definition for self centered.

i was not saying to schedule this contest but if possible in future contests if doesn't affect other guys previously some contest were 1 hr earlier which had some comments that's why I thought of sharing thought with community :/ had some personal interest also lol

Good luck 4 everyone! Have funI wish that u'll up your cf ratingAgain, that's impossible. If you have good delta you have bad delta. If you have extremely good delta, you have extremely bad delta.

very helpful contest for beginners :)

Ah yes, finally i can reach pupil.

hopefully

I can leave a message again Yea~

can i say that div 3 is the best training contest for who is less than 1600 rating and will be better if problem standard

Oh I thought, Div 3 = Div (1 | 2). lol.

Oh I thought, Div 3 = Div (1 ^ 2). lol.

It seems that the queue is really long......Can this round hold on time?

Verdict: In queue

There is a problem with submission, it shows the "In Queue" verdict. Wish this will not happen in today's contest.

i think this div3 round is going to be unrated !! "In queue" fact

Anyone else getting Bad Gateway errors lately?

Yes, I think there is a server issue on cf.

Hope this won't occur during contest , DIV3s are imp for beginners.

they changed the contest date to 5th may

Notice unusual change in schedule.. :(

I think it's better to have a postponed rated round than an unrated round

(it doesn't matter to you as it is already unrated for you :D)

I hope today, there will be no queue in codeforces,

Delayforces!!! :(

It's been an hour since I submitted a problem. Still in queue :(

Yes! my submission is also in the queue. :(

um so how many registrations will this round have now?

Maybe 35K registrations ;)

The least they can do is to reset the participants so that there won't be another 30k contest and it becomes unrated, seems like no one cares about div.3 contests.

What do you mean by no one cares about div.3 contests?

It's my first time to see a 24-hour delay here.

But it is ok then a unrated contest.

+1 , was really excited for the contest :(

why mike why

Nooo :((

Peeporiot ;-;

Better delay than unrated :(:( :( :( I have planned to go to my village tomorrow

So,30k+ participants this time?

Delay 1 day ?

Round postponed

round is postponed, I was waiting and refreshing every 1 minute to see how much time left. sad life.

Since the contest was postponed, can you please open the registration again?

Div 3 — Let's rock today.

(postponed :{ )-

Let's practice today :}

can't even practice

due to long queues :(

due to Internet × wait until the registered participants over 30k √

I finished my talk over phone with bae just 5 mins before the contest only to know this... (Cry Emoji)

downvote this guy.

Yes please add salt to my wounds... Sadists

You doing the same to us.

I just logged into my system to see this shitpost...(cry Emoji)

All this time.. i was refreshing my browser..thinking issue on my side.

The round has been postponed- NO WORRIES

IPL has been postponed- CRY, CRY, CRY :(

postponed for 24 hours!I will never participate in a CF contest if this contest has been postponed again!my exact reaction

Stepavly

please enable the register button so that the people who have not registered and are the official trusted participants can register !! ** Thanks in advance ** !!UPD : THANKS !! I have successfully registered now !

YES , NOW ITS DONE U CAN CHECK THANKS FOR LETTING US KNOW !!

when I finish my dinner fast for the contest...

Unfortunately, due to Internet provider network issues, we have to postpone the round.

you are genius bro!

and then 24 more hours for ratings change. I don't know whats there in calculating ratings that takes 2 or more hours.

Thanks for changing the time. I was having issue since noon. ( contest starts on my local time at 8:30 pm at night ). m1 m2 and m3 all were down and showing "bad gateway 503", I thought, I wont be able to join the contest due to this network issue. Thanks a lot to the organizer to consider the issue.

Verdict: No Color! :(

Cf: Hmm you're mad because we delay the round for 5 min sometimes WEll How About 24 hours !! Muahaha

Really excited for the contest , hoping I would cross 1100 this time. Any tips are welcomed. TIA

Tip : you have done it before.

Hopefully, I become pupil today.

Good luck to everyone!

when you heard the round was delayed

Did we break a registrants record?

In one of the div3 rounds, there were 30k+ registrations. Unfortunately round went unrated due to long queue

that is why they shoudnt allow >1600 to submit during the contests..so as to reduce the queue..almost 2000 are there ....this should run properly...only once in a month...div3

This will be my second contest. I participated in last global round and I still don't know how the score works perfectly. In that contest I think they gave me less points for a problem with previous wrong submissions. Here when it says there's a 10 minutes penalty for wrong submission, is it saying that I will lose 10 minutes from the total 2 hours of the contest for every wrong answer?

You are judged by number of solved problems, and penalty points. Foreach AC submission you get 1 solved problem, and the number of minutes from start of contest plus 10 minutes per wrong submission of that problem as penalty.

Thank you. I thought it meant I would have less time to solve problems, misunderstood that

I have -3 Contribute, please upvote for me :((

i have a feeling that site may crash !!!!!

yes it has already started lagging.

Hemlo Joshi(cout_wolf) dear!!!

this is not chatting site

Hope minimum FSTs....

Why on equal rank in div3 contest gives less positive delta then div2 on same rank. Suppose x rank in div3 will give less positive delta than x rank in div2 ?

coz having the same rank in a more difficult contest(since better rated participants are rated in Div2 contests, than in Div3) is better.

So , greater number of participation theory fails here!

Hope the contests won't get unrated because of long queue, we are reaching close to 30k , at this rate we might be reaching around 32k easily

Registered people might not give contest today!

Round got ruined due to long queues. :/ Submitted a solution in the last 20 seconds, site kept loading till the contest ended. Solution didn't get submitted before that due to queue. But it got AC after the contest. I dunno if Mike can do something about it or whether I am set to lose points for that solution. Sed life!

Got It.

no score distribution in div3

It's starting finally: the most awaited contest since yesterday :)

Cheers Codeforces for 30K registrations once again!!!

lgega queue aaj

30k registrations aaj lgega queue :(

It is 30000+ contestants today. I hope CF doesn't crumble :(

my code is running from more than 10 min, i also tried to cout<<"HELLO"; but it also taking more than 10 min ; MY internet connectivity is good. i also tried to logout and log in

Is there any queue issue :( , my code is in the queue for last 20 minutes

It seems that my submission for G is executed twice, is this right...?

G has 100+ test cases wtf

On 60th and hoping, been 10 minutes.

And yet, even so many tests were not enough to cover incorrect TL solutions. (Lots of hacks)

Including my solution lol

you guys should give atleast some weight to out-of-contest submissions. It's not like everyone participates in div3 :|

;

THE QUEUE IS TOOOOOOO LONG I CANT STAND IT PLEASE MAKE IT UNRATEDgot WA on test 1 after that !

Unfortunately, I got WA on test 2 not 1

After waiting for 4-5 minutes.

WA on test 1

Queueforces :(

questions were very interesting but the long queue snatched away all the fun :(

my highest queue time 8 min on question D among all of them

Make this round unrated. Continuous 5 minute queue isn't suitable thing to run a rated round

That "In Queue" annoys me a lot!! Ruined my contest.

No way this can be rated!

It has to be...you are slow.

And you are bdan.

Interactive is not good when long queue time is there.

This Contest should have been extended by 15-20 min to compensate for long queue

what if some people have work after it ? Extending round is always a bad idea. They can keep it for 15-20 min extra but it should be announced before the contest. for majority of people queue time didn't matter much and it was fair for everyone since everything was same for everyone.

Actually, there have been situations in which the contest was extended due to long queue. I think it wasn't a really smart choice to put >100 cases in G considering that both F1 and F2 were interactive, though.

I agree that people may have other commitments after the contest but extension has been done many times during some the previous Div 3 Rounds and extension gives relief in some sense . if you have another work just go for it , there will always be some contest in a week after it so you can make a comeback in it to recover your rating loss

I am eagerly waiting to see test case 5 of problem "D".

Maybe you did not use long long!

Yes,,,you got it.

oops man even i got WA because of that now did long long and submitted and it got accepted

Same vaya,,,soooo,saaaad.

For me the trick was storing the frequency of the difference as long long.

I got it.

I got wrong on test 5, then I changed my min=1e18 and it got accepted... :)

Yes,,,I got the point.Thank you.

it's because u didn't use int64_t or longlong. The test case made the answer greater than the limit of 32 bit integer. I guess your logic is totally correct but just didn't use the correct datatype.

Thank,you.

C,D<A<<B<<<E,F1<<<<<F2<<<<<<<<<<<G I know the number of solves indicate otherwise (difficulty distribution linear from A to G) But just look at the number of wrong answers and solution size.

Can someone confirm if problem G was dijkstra ? I just submitted it and excited if my approach is correct.

No. Brute force Dijkstra should TLE because the complexity is of the order $$$\mathcal{O}(E(G)) \sim 10^{12}$$$

dijkstra is O(ElogV) and not O(EG) if you use min priority queue

How is $$$E(G)$$$ not $$$10^{12}$$$? If you directly bruteforce from each teleporter you have $$$mn \sim 10^6$$$ edges from each node and so it behaves like Dijkstra on a complete graph which obviously exceeds time limits. I just dropped the $$$\log V(G)$$$ factor because removing that doesn't make my argument fail.

there is actually a better way to do this, you can add a dummy node to which you connect all teleporters (from), and then you connect the dummy node to all teleporters (to). So in this Case you only have

O(E)edgesSorry, but I don't see how that's an improvement in the complexity.

Like floki said, each cell has 4 edges going out of it (up, down, left, right), but also for each teleporter you add an additional edge to a dummy node (at most $$$nm$$$ more edges), and an edge from the dummy node to each teleporter (at most $$$nm$$$ more edges). So the total number of edges is at most $$$6nm$$$, which is reasonable but still hard to get to pass on this problem.

Google-forces

So, I waited 10 minutes to get a TLE on test 114 of G after the contest had ended already . LOL

I got TLE at TC-69

N I C E

sounds kinky (•◡•)

Literally I spent 8 minutes to get

Wrong answer on pretest 4Same problem as E

How do you guys get so much time to find similar problem in google during the contest!

Actually I didn't search I knew I had done it before

A lot of people prioritize searching on Google over thinking about it themselves. You know, just in case, they don't even have to solve it themselves. Just yoink the already written code by someone else, and boom Positive delta.

SlowForces

Waiting for this comment. In queue

WHAT A BAD ROUND!I must wait 8 minutes for the result of my submission.

yes and because of that couldn't make changes in ans if it was wrong...literally 2 hrs passed so fast.

The queue was so much annoying !

I remember getting up for Kickstart round H last year, quite early in the morning, I think it was worth getting up. But not on that that day, its today, cuz problem E is literally this lol. Also Thanks to people like Galen, Ecnerwala, Neal, who posted solution to (problem E) that round that day. High rated people do have time machine xD.

F2 was an absolute bomb. It's been a while that I see such a beautiful problem.

Agreed, the rest of the problems felt very standard and paled in comparison to F2.

Depends on your solution... Mine was using something like SQRT decomposition and was really boring. But the intended soln is indeed beautiful.

Hey Stepavly, MikeMirzayanov

I submitted problem-A in last 19 seconds but the CF website just kept loading and loading. The time got up, contest ended and my solution couldn't be submitted. How would you take this into account?

UPD: Submitted just now again and it got AC. Here it is 115328838

Would I gain no points for this? :'(

Bad internet situation.

I submitted no. (D.same difference) before the contest ended. But it is still in the queue. Will it be counted?

Problem B : https://www.geeksforgeeks.org/count-of-numbers-with-all-digits-same-in-a-given-range/

I forgot to delete a part of my code in F1 that I used to verify my solution, but since I was still in the queue I did not realize it, I feel very bad :(

same here i also face same problem in c i printed NO instead -1 :( when i realize contest is over :-(

yes, and the worst thing is that my solution was correct :(

mine too (you can verify)

Can anyone explain problem F2 and G?

F2: You can query each prefix of the array with step of 8 (that is, 1, 9, 17, ...) and store the number of zeros in it. Now to answer the query, you must first binary-search these prefixes (takes 0 queries), and then search among the remaining 8 elements using exactly 3 queries. Now what happens when we change some 0 to 1? Some suffix of our array with prefixes has to be decreased by 1. To perform these operations quickly, you could use a segment tree. BIT and sqrt decomposition should also work.

The total number of queries is t*3+n/8 ~ 5,5*10^4 < 6*10^4

IDK if this solution is the same as the author's one, but this one seems really beautiful to me.

G: Notice that you either don't use the portals at all or use them exactly once (since we can omit the intermediate steps). The variant without portals is solved using trivial BFS. About the case with portals: you first go from (1, 1) to a portal, then pay its cost, then the cost of the second portal, and then you go from portal 2 to the end. You can compute these sum of the portal's cost and the cost to go to this portal from (1, 1) and select the one which minimizes this quantity as the first one. The case with the second portal is symmetric.

For F2, you can break the interval into blocks of size 32 ([1,32], [33,64], ...) and query the number of 0s in each of them. This takes roughly 2*10^5/32 = 6250 queries. Then you can answer each k by finding its appropriate block and binary searching on it.

Each answer will require 5 queries, so we use at most 5*10^4+6250=56250<6*10^4 queries.

The advantage of using blocks instead of prefixes is that we only need to update a single block after each answer. Also, since we chose a block size of 32, we can directly iterate to find the block that will contain the answer (since 10^4*2*10^5/32 = 6.25*10^7).

My sqrt decomposition solution of F2 is giving wrong answer on test case 21 (queries limit exceeded). has anyone done using sqrt decomposition

for me, taking block size as $$$n^.5$$$ failed on TC 21, but taking block size as $$$n^.25$$$ worked.

thanks bro it worked

Taking block of sqrt(n) will not pass. In worst case with block size of n^0.5 length will be 450 and log of 450 is 8.8 ~ 9. so for 10^4 tests atleast 9*10^4 queries will be made.

It's helpful. Thanks !!

For G using k+1 portals is never more optimal than using k portals. Hence we shall use either 0 or 1 portal. let cost[i][j] = minimum cost to move from [i,j] to n,m using only adjacent moves. Now for each portal do cost[i][j] += matrix[i][j] and find the minimum cost to travel from a portal to n,m. Let this value be equal to min_cost.Now the answer to the problem would be minimum cost to reach from a portal [i,j] to [1,1] + min_cost + matrix[i][j]. Which is equivalent to moving from [1,1] -> p1 -> p2 -> [n,m]. Dont forget the case when you use 0 portals.

must be unrated i waited so long for in queue

Please make this round unrated. Couldn't solve the problems on time due to the waiting thing.

It took 10 mins to get the final verdict to one submission.

Absolute right. only because of this i couldn't try F1 in last minutes.

Please do something about "**In Queue**" while submitting in the contest. It always gets stuck in the middle of contest.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 or greater than 1600 or even equal, then the round will be

un-ratedfor you.Someone confirm I'm not blind, this was the sample shown for problem F2:

So this seems to imply that you have to read in a 0 after each test case, which is a thing that some interactive problems make you do. But not this problem. When I tried to read in 0, I got runtime error on test 1, and removing that worked. So did the samples lie to me?

The first '2' query (line 2) is actually the value for K for the first test case. It is only to be read, it does not correspond to any output line :)

Ah I see what happened, ok thanks.

In F2, There is also an input for 'k' after running for each 't'.

Please check this submission for F2 :- https://codeforces.com/contest/1520/submission/115329302

Video Tutorial B: https://www.youtube.com/watch?v=eBPTxfi6raY

Video Tutorial C: https://www.youtube.com/watch?v=Rhr-eHnnGrg

Task E : https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/description/

There should've been extra 10-15 minutes for such a long queue!

Not "such a long", it was less than 4 minutes u should say. Thats fairly normal considering the huge number of participant

In last 5 minutes, I faced around

7-8minutes long queue! Consideringevery last minute matters, it was huge for me! Submission link: https://codeforces.com/contest/1520/submission/115324831Site was down for the last few minutes.

Did CF copy almost every problem today?

B — https://www.geeksforgeeks.org/count-of-numbers-with-all-digits-same-in-a-given-range/

D-https://www.geeksforgeeks.org/count-the-pairs-in-an-array-such-that-the-difference-between-them-and-their-indices-is-equal/

E-https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/

Did you find all of them during contest ?

I checked his profile, doesn't seems he attended the contest.

Solving problems is faster and exciting then finding it on google! :)

Exciting- Very true

But any regular CP-er has already practiced these common problems and knows where they can be exactly found.

That's our weakness that we didn't practice those problems. Right? :)

I never said weakness. You solve the problems during the contest, kudos to you. I have attended every contest of codeforces and leetcode from the past 1.5 years (not from this account) and have practiced these problems more than 7-8 times, which doesn't make for me to again write the same code.

They paracticed those similar problems erarlier so they had more knowledge than u, thats why they solved those because they can relate those idea with the given problems. Not necessarily to searching and copying everything from google

If you have already seen those problems somewhere before then gj here's a candy

Let us (newbies) enjoy those quality problems.

also imo, adding classical problems in a div3 is actually a good idea as they are hosted to improve your skill not the ratings

but hey! you can switch the platform whenever you feel like ;)

i think u went overboard

The queue sucked. This round should be unrated!

Started the contest 15 minutes late, but still managed to get till F1 in 1 hr 30 minutes. My best performance so far, thanks for the round and hope it remains rated.

"

Started the contest 15 minutes late"lol, you made 2 submissions before starting, thats so cool!!

I count starting the contest when I get first AC, this way it keeps me motivated even if it takes 1 hr to solve A lol.

Anybody else think that solutions should be regraded for problem G with an easier time constraint? Maybe it's just java idk :P

frog ORZ FROGGY FROGGY

editorials??

Can someone tell me whats wrong in this code 115328097

answer can be greater than INT_MAX. initializing mini with some bigger value should work.

If long queue would not have been there then I could have got F1 and F2 right in time.

Did someone got G?? I got WA on test-26

can someone tell me why i got TLE PLEASE for(int i=0;i<n;i++){cin>> a[i];

hashmap[a[i]-i]++; }

else if(a[i]<i){ x=neg[i-a[i]];count+=x;

neg[i-a[i]]++; }

}

At least there should have been a 10/15mins extension of contest duration was needed due to the long queue problem. I just needed to change the answer from int to long long to get problem E AC. :(

This comment is deleted , {how to delete a comment ??}

I'm so stupid!!! I used INT_MAX as infinity value in problem E :(

wrong ans on test 5"wrong answer 1st numbers differ — expected: '62517316129', found: '2147483647'"Same for me.. Then thought for a while and got that the min ans could be long then INT_MIN.

same here !!!!

too many copy-paste problem :(

That's unfortunate. I solved till E and all by myself and I was so proud of my approach to E, but now since I found out that it was on the internet, I feel cheated :)

its not the point bro. the point is that you should have faith in yourself, don't cheat yourself, and give your best in contests.

Did anyone else get WA on test case 37 for G? My submission if anyone wants to check it out.

My approach:

Do Dijkstra's algorithm, and find the shortest path to enter a portal (call it $$$P$$$). Then, run a multi-source Dijkstra's, with each source being a portal, and the starting distance to the portal as $$$P$$$.

In my code, the priority_queue stores

`<-distance, pii{i, j}>`

, and the distance is stored as negative, because Dijkstra's uses a min heap, while the default priority_queue<> uses a max heap.The dijkstra lambda function is just so that I don't need to copy-paste the code.

The portal variable stores the shortest distance to a portal.

Maybe the optimal answer may not contain a portal? It depends on how you wrote your code

That's not it, because I only update a node if it has a new shortest distance.

That's the purpose of the

`if (dis[i][j] <= -d) continue;`

code.Hey could you help me with my code for problem G. The memory limit is exceeding for test case 13.

https://codeforces.com/contest/1520/submission/115414656

Me after giving this contest -> https://www.youtube.com/watch?v=Uz-sPvopjvY

Weak test cases for problem D. Disappointed :|

Nice problems, but really bad problem statement in F, especially F2, description is hardly understandable, and description of input simply wrong.

I am shown as +100, but would rather see it if it were unrated.

Also the queue was slow.

How to check expected rating change before official changes ??

download an extension

which extension?

It is called "CF-Predictor", should be available by google search.

I use Carrot, and it works really well. Idk why it's named "Carrot" though lol

Carrot is better than cf-predictor... (i used both)

Totally agree about F2

It is rather confusing to say the least

First there are too many letters to be easily comprehended. But that's not the only problem

For example at some point they talk about "requests", then there are "queries". You would think it is different things,

Then right after the description of the output format there is "In case of an incorrect query, -1 will be displayed" and you try to match with the format, thinking that maybe you need to read some confirmation code after you cout the answer because it is natural to think outputing the answer is a kind of query

Finally there is brilliant statement "Then t lines follow, each of which contains one integer k". I don't know about others but for me it means that at this point I can read t lines.

Yes, it is possible to figure out what was meant by rereading the samples and 1KB statement a few times or by requesting clarificiation, but I find it rather inconvenient. It is especially inconvenient when the server barely works.

Can someone please help, why is this giving TLE in test 3 ? 115323338 , 1520F2 - Guess the K-th Zero (Hard version) Thanks ! UPD: I got it, since I used RUPQ Fenwick tree I forgot to update(r+1,-v) when I update(r,v)

Not only the blog was almost-copy-pasted-part. But also the problems. Idk what did the testers do really test. And did not report for such well known problems.

I've just started getting the knack of codeforces. And I was able to solve A, B, C, D in this contest. But I was slow to think of the approaches and hence my rank is around 6k. Hopefully, I will get better at thinking fast about the solutions. If any tips that may help, please do tell me cause that would be great.

Practice

What helps me to solve problems faster is to get better at math, especially competitive math, because the easier math problems have similar styles to the first few problems in a Div3 or Div2. Also, solving Codeforces Div3's and Atcoder abc's (Atcoder Beginner Contest) was one of the biggest factors in my speed. Now I just need to improve on actually getting the solutions...

how to solve F1?

Binary search the answer. Let's say you know sum(1,cur), then if cur-sum(1,cur) (which is the number of zeroes in that range) is greater than or equal to k then you know that the kth zero should be in the range [1;cur]. Else if n-sum(1,cur)<k then the kth zero is in the range ]cur;n]. So binary search over cur. 115289534 PS: sorry for not using LATEX

Explanation for Problem F1

Problem D Video Editorial (in Detail Explanation) : https://youtu.be/7IRsFvqgWlw

I was facing huge network delay during the contest . every question took around 5 minutes just to submit . Was anyone else facing this issue ?

What is the intended solution for F2???

It seems that the author's solution is just do binary search every time and avoid query one segment twice.

But there's another very beautiful solution that divides $$$1$$$ to $$$n$$$ into blocks of $$$8$$$ and use data structures to maintain.

What is this technique of division to 8 blocks called?

It's not a common technique.

That solution is only used for F2