Hello Codeforces!

On May/13/2022 17:35 (Moscow time) Educational Codeforces Round 128 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Harbour.Space takes over SWERC by winning gold and silver for the first time in its history and will go to the ICPC World Finals. Congratulations to all of our participants and coaches that made this a reality!*

*This is a very important moment in Harbour.Space and Codeforces long partnership, with 127 educational rounds being organized and a big Harbour.Space Scholarship Contest held on July 22th. We have selected contest winners (Xaxixin, Meijer and queen) to form our current teams.*

*Since its creation, one of Harbour.Spaces’s goals has been to win SWERC and compete at a high level in the ICPC globally. On April 24th, that objective was accomplished when Harbour.Space’s team RAW POTS (read it backwards!) won the gold medal and the overall contest against Southwestern Europe’s top contenders.*

*Team Raw Pots — gold medal:*

*Maksym Oboznyi (MaksymOboznyi), Marco Meijer (Meijer), and Danil Zashikhin (Xaxixin)*

*Team Kempirqosaq — silver medal:*

*Temirlan Baibolov (bthero), Dinmukhamed Tursynbay (DimmyT), and Amanbol Kanatuly (queen), ranked 4th and won a silver medal.*

*Team Harbour.Backspace — ranked 27th:*

*Anier Velasco (aniervs), Fadi Younes, and Ekaterina Podruzhko, ranked 27th.*

*The faculty, current students, alumni, and everyone involved with Harbour.Space would like to congratulate the winners and participants at SWERC 2021-2022 for their wonderful performance and hard work.*

*As usual, we are always excited to see Codeforces participants as our students here at Harbour.Space. That’s why we encourage you to apply to our latest apprenticeship program in partnership with Hansgrohe, as a Kotlin Developer until May 31st, 2022.*

*Harbour.Space University Team*

**UPD:** Editorial is out

Wish i will solve problem ABCDE and go orange this time!!!

Good luck.

Me too

Best wishes!

nice try

nvm

good luck to every one :)

Good luck everyone and try your best.（＾ω＾）

Good luck to you too.

I can't wait to get back the rate I lost in #789!!!ψ(｀∇´)ψ

rotavirus face reveal?

All the best everyone!!! Hoping that everyone will get a positive delta

But it's not possible that everyone will get positive.

Do your best guys and never give up

GOOD LUCK!

ok

I hope to solve A,B,C with good speed to get some positive delta.

Good luck everyone!Wishing everyone luck to overcome the curse of Friday the 13th.

Hoping to solve A B C and become green.

Good luck

I Hope to solve A B C D and become specialist.

I didn't participate contest for a long time, very happy to be back and

good luckto everyone!can u provide the score distribution?

Ig there is no score distribution in educational rounds.

Problems are not weighted in educational rounds.

Wish I will go outside the infinite loop between Newbie and Pupil :)Who is like me !!wish i can stay blue!!

How many questions I need to solve to be a specialist if my current rating is 1207 ? Can Somebody tell me ?

just solve at least three problems as fast as you can

Congrats to the gold and silver medalists!

Is it allowed to browse the internet during the contest?

Yes

Yea, you can even copy the exact code from some public websites and it won't be counted for plagiarism. Copying from private websites or from friends is counted for plagiarism

Happy to see Kazakh names on the leaderboard! Good luck everyone!

Sorry if this is harsh, but this was a very poorly prepared round. If you need to make three contest announcements on problem C, change the output format of problem F after half the contest, massively misjudge the difficulty of E, and have major wording issues on problem D, then there hasn't been enough proofreading. That's 4/6 problems in a 6 problem contest having serious issues.

## Clarity issues with C:

Clearly this wasn't explained well enough in the statement, because we needed (or at least we got) 3 contest announcement to clear it up. It's a bit annoying to have to click through a bunch of dialogs during contest about announcements.

## Wording issue with D:

The statement says "what is the maximum possible number of different integer points of the line your dog could have visited". This is equivalent to asking "how many points X exist such that there is some way of replacing 0s with integers -K to K such that your dog would be at point X at some time and eventually return to point 0?". That's not what the problem writers mean though, they should say "You know your dog chooses her path in such a way to visit the most number of spaces. How many spaces did she visit?"

## Difficulty estimation issue with E:

E has

waymore solves than D; I believe rightly so. I won't spoil anything here since the round is ongoing, but I have no idea what the authors were thinking with this relative difficulty estimate. Either unnecessarily complex solution ideas, or perhaps didn't have nearly enough testers, I guess.## Output format flipped with problem F:

For the first half of contest, problem F told you to print 1 if it was

notin the set, or 0 if itwasin the set.agreed. I thought E was quite complex until I see the huge number of people who solved it.

I don't agree about C.I felt all the three announcements made are redundant

But if they were completely redundant (I agree that they were), they shouldn't have been announcements (just clar request answers) because they are mildly annoying to click through for people who can read the statements.

I Agree.

As I already said, these announcements were made to decrease the number of questions.

I do agree on some of these things, like bad output format in F (that's clearly our fault) and difficulty issues with D and E (they should be in reverse order, we overestimated E and underestimated D). However, I don't agree with what you said about C/D.

Regarding C, I believe the problem statement was absolutely fine. All of the announcements I have sent during the contest either repeat what was said in the statement, or tell something completely obvious. The only reason why I had to send these three announcements is just to cut down on the number of questions on this problem — we were getting too much of them, and a lot from people who clearly haven't read some part of the problem. I actually wanted to send the fourth announcement describing that the cost is the

maximumof two values, not thesumof them (even though it is written in bold in the statement, there were lots of people sending their questions where they calculated the cost as the sum of the two values).Now, considering D and its statement. I don't think I can argue about the English grammar (where we can use the phrase "could have" and where we cannot, for example) with someone whose native language is English, but I want to ask you a question. If you think that the statement is equivalent to "how many points X exist such that there is some way of replacing 0s with integers 0 to K such that your dog would be at point X at some time and eventually return to point 0?", then what is the meaning of the words "*maximum possible* number of different integer points"? We clearly don't maximize anything in this understanding of the problem, so it makes no sense.

I think you're right under my incorrect interpretation it'd make more sense to say "total possible" than "maximum possible", but also I think that's relatively normal for people to say incorrectly. I think the real issue with the wording is that you're asking for the number of

reachable spaces, not the number of spaces reached by theoptimal path.Unrelatedly, thank you for the "additional constraints" on input rather than saying "It is guaranteed". :)

I would argue that 'cost of removal' is pretty ambiguous in C.

I myself understood it as a cost of single move — mainly because plural form 'removals' was used in previous sentence.

But I think that task descriptions were fine.

oh wow, I had completely misinterpreted D just as you said. I was wondering why the problem was so easy and yet had so few solves.

Before ending the contest, it's the first time to close it before thinking about problem C. It's a big gap between B and C.

suppose you trim the string to $$$s[i + 1, ..., j]$$$. write out how to describe the two costs with index $$$i, j$$$ and the prefix sum of number of '1' $$$pre[i], pre[j]$$$, then you can find some relationship.

Thank you, I'll upsolve it soon.

learn how to use binary search. (*)

104 minutes by just staring at screen : ( and trying

I don't understand D at all!

Let $$$p_i = a_1 + a_2 + \ldots + a_i$$$. Choose some numbers in $$$[-k, k]$$$ for positions with zeros so that $$$p_n = 0$$$ and you need to maximize $$$max(p_i) - min(p_i) + 1$$$.

me too...

What was the main idea behind problem C? Was it dp, binary search or some other algorithm?

I kind of got there with dp-greedy approach, but unfortuntely I couldn't figure out which edge cases I was missing.

Will highly appreciate to see some dp approaches, however will not mind to hear other algorithms. Thanks in advance!

I used dp.

Would you mind to run me through your idea briefly?

Define $$$pre[i]$$$ as the number of $$$1$$$ in $$$s[1,...i]$$$. Suppose you trim the string to $$$s[i+1,...,j]$$$. The number of remained $$$0$$$ is $$$(j - i) - (pre[j] - pre[i])$$$. The number of removed $$$1$$$ is $$$pre[N] - (pre[j] - pre[i])$$$. So, if $$$j <= pre[N]$$$, the maximal will always be $$$pre[N] - (pre[j] - pre[0]) = pre[N] - pre[j]$$$. if $$$j > pre[N]$$$, you may choose the minimal of $$$pre[N] - (pre[j] - pre[j - pre[N]])$$$ and $$$min_{i=1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$. Note that $$$min_{1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$ could be calculated by a prefix maximum of $$$i - pre[i]$$$. Iterate all possible $$$j$$$ and get answer.

Update: as $$$i - pre[i]$$$ is a non-decreasing sequence, the minimal of $$$min_{1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$ happens at $$$j - tot$$$. So the minimum cost for each $$$j$$$ should be $$$pre[N] - pre[j], if j <= pre[N]$$$, or $$$j - pre[j] - (j - pre[N] - pre[j - pre[N]]) if j > pre[N]$$$.

Yeah, thats pretty nice solution. Thank you!

Not sure my idea was same as that of yours but My idea was there exist an optimal solution in which number of zeroes in resulting sub-string equals total number of ones removed (otherwise, we can increase minimum value without altering the result). Now, zero_count in resulting sub-string = total one_count removed => zero_count in resulting sub-string + one_count in resulting sub-string = total one_count removed + one_count in resulting sub-string => length of resulting sub-string = total one_count of initial string. Now I know length of resulting sub-string (i.e, one_count of whole string) and cost (i.e, zero_count in that sub-string), I can just use prefix sum to minimize the cost in one iteration.

What an elegant solution! I would say it's more easy to understand and implement than any other methods. btw, writing equation using latex maybe more easy to read.

in the case of j<=pre[N], why you didn't consider i like pre[N] — (pre[j] — pre[i]) for all values of i and j?

you took i = 0 and the maximal became pre[N] — (pre[j] — pre[0])

Because $$$pre[i]$$$ is non decreasing.

Can you also tell why you took i = j — pre[N] in second case, I am not getting it?

That’s also because $$$i-pre[i]$$$ is non decreasing.

Thanks

Can you tell what exactly is j-pre[N]?

I tried but I am not getting it, sorry to disturb again and again.

what was the idea for DP ? I have solved with binary and greedy

You have the answer above ^

I did it using Binary search

To check if it is possible to achieve this costWe will take the longest prefix such that number of ones in this prefix is equal to cost and the longest suffix such that there are no ones in it. Now just keep decreasing the length of prefix and increasing the suffix and check if at any time cost of removing the prefix + suffix is lesser than the cost that we want.

I like it, it is a good one too!

can u explain its time compl.

A sliding window approach also seems to work. If the cost comes from the undeleted part of the string you delete more characters from the left, otherwise, you choose to delete fewer characters from the right.

Could you explain it a bit more, please?

Sure, I can try at least although I think it sounds way more complicated when I try to explain it than it sounded in my head.

First of all, I find it easier to think about choosing some substring than choosing how many characters to delete from each side.

Let's now say we have chosen where the substring should begin and try increasing the length of the substring one character at a time. At first, the cost will come solely from the ones but that number will decrease until the number of zeros will start to matter. Then the cost will start increasing again. This means the optimal cost will be when the amount of zeros and ones is the same.

Now in the program, we want to find the optimal substring that begins at each character and then chose the optimal cost therefrom. First, we find the optimal substring that begins at the beginning. It is not hard to convince oneself that the optimal substring that begins with the second character will not end earlier that the optimal substring that begins in the beginning. Therefore we don't need to try substrings that begin earlier than the previous substrings.

To implement this efficiently we can use a classic two-pointer/sliding window strategy. We keep track of where the substring we are currently interested in starts and ends and move the end or the start of the substring by one. All while keeping track of how many zeros and ones there are for the current substring. Each pointer only needs to move the length of the string so the algorithm runs in O(n).

I see the idea, thats a great one!

It can be done with binary search + sliding window(btw isn't sliding window a subset of two pointers?)

Submission

I used ternary search.157084549 Edit: and then got hacked! Can anyone give me proper implementation of ternary search to find minimum

I solved C by greedy.

Let $$$Z$$$ be the number of $$$0$$$ in the initial string.

If we want to remove $$$L$$$ characters, and $$$C$$$ of which are $$$0$$$, then the cost is $$$max(Z - C, L - C)$$$.

If $$$L < Z$$$ , then $$$max(Z - C, L - C) = Z - C$$$, which means we can delete up to $$$Z$$$ characters and the cost won't get higher during the deletion.

If $$$L = Z$$$ and we want to delete another character $$$x$$$:

$$$x = 0$$$

The cost will become $$$max(Z - (C + 1), (L + 1) - (C + 1)) = max(Z - C - 1, L - C) = L - C$$$. We get the same cost as that of $$$L = Z$$$.

$$$x = 1$$$

The cost will become $$$max(Z - C, L + 1 - C) = L + 1 - C$$$, which is higher than that of $$$L = Z$$$.

So the solution is to enumerate all possible deletion that delete

exactly$$$Z$$$ characters and the minimum cost should be the answer.157091140

Nice idea. I've tested it without storing arrays of prefix/suffix sums: 157096927

I didn't notice that the two arrays were not necessary, thanks!

excellent idea....Thanx for sharingI used two pointers and bp. If you have an answer X, then the segment that we don't change can't have more than X zeros. Just do two pointers stuff on that. Total time is $$$O(nlogn)$$$ 157048159

I used binary search the answer

Assume we want to check whether we can get score of $$$X$$$, then I will try to remove $$$i$$$ number of $$$1$$$s from the front and $$$X-i$$$ number of ones from the back ($$$0 \le i \le cnt_1$$$)

If there is such $$$i$$$ so that the remaining substring consists with at most $$$X$$$ number of $$$0$$$s, then we can obtain score of $$$X$$$ and try lowering the answer (or increasing it if there's none such substring)

can you please tell me how you concluded that it is a

`monotonic`

and`continuous`

function? Like if the answer is valid for x then it is also valid for x+1Hey, at start you can observe that the actual answer is <=

`number of 1s in the string`

(as that's the cost if you decide to remove all characters and make the string empty).Now, you set the binary search range

`[low, hi]`

to`[0, number of 1s]`

. Now you guaranteed that the hi value corresponds to a valid cost that can be generated.Now, let's say there is some cost

`X`

between`[low, hi]`

that can be generated by removing some prefix and suffix, reducing the original string to string`S'`

.To observe why all values between X and hi are also achievable, you can see that removing first letter from

`S'`

will change the cost either to`X+1`

, or`X-1`

(depending on if it was zero, or one).If you repeat that operation again and again,

`S'`

will eventually turn into empty string with cost`hi`

. All values between`X -> hi`

will be generated on the way, as each single letter removal increases or decreases the cost by one — no value in between can can be skipped.greedy O(n) — https://codeforces.com/contest/1680/submission/157062229 We check every deletion of 1's from left side, while trying to add 1's from right side as much as possible.

I used ternary search.

Idea is "what is the optimal ans if i keep X 1's in my answer".

How To solve C?

I tried greedy + binary search , to find the nearest 0 from left side(using binary search) and the nearest 0 from right side ,whichever is remove in that direction and update the answer, update the corr left most point & right most point values, till first < last.

Can someone tell me where I am wrong with this approach? Thank you.

Code 157056549

I solved with binary search on the score (and a 2 pointer solution where I removed as many 1's as possible from the front, then added them back in 1 by 1 while removing them from the back to verify if a score was possible).

what if both zeros are equally far from both sides :(

sry to say but bad problem statement :(

In first few mins finished A and B. But with the full remaining time, couldn't even think of a valid logical solution for C.

Who tested C.. the pretests are very strong lmao.

the main observation about C problem is that you need to remove 1's >= 0's

Thats not necessary in my opinion. For example take the string 100110011. Here, for optimum answer(i.e. 2) you remove just one 1 and two 0's (from starting).

it's important for greedy+binary search solution: in your example you can also get acceptable results such as (1001)10011 and (100)11001(1), the answer is the same — 2

Well, I was trying to convey that your observation seems wrong to me through a silly example. Just take the string 100000110011. Here for optimum answer(i.e. 2) we remove one 1 and five 0.

I understand what are you trying to say, but 0's in my statement are the ones which left not removed.

Hello, MrOtter , how this observation is true , can you please explain ? i.e. (no of 1s removed >= no of zeroes left). And why its vice-versa is not true? What's exactly makes the difference ?

actually, wracking my brain for hours and could not get the observation by seeing others implementation. It will be very helpful if you can explain it clearly.

because to minimize answer you need to remove 0s as most as possible and leave 1s as most as possible. in other words you need to find balance between 1s removed and 0s left to minimize difference between them. how you can do it?

you can observe that you can remove 0s from left and right for free while there are none of 1s. but when you get to 1s you can consider them as price to get to next 0s. so you need to construct threshold condition where you allow to remove 1s and it can improve answer. that's how can come up with condition "no of 1s removed >= no of zeroes left" because you can always remove 1s while no of 1s removed < no of 0s left (maxOf(1s, 0s) = 0s) and it will not get answer worse so it is worth to try.

based on this observation you can come up to binary search solution

Ok, MrOtter, i got it now. Very thanks for explaining the doubt in so much detail. Actually, stuck on this solution intuition for a while.

I spent all the last hour working on F,while failing to solve it in time(If only i have ten more minutes).Maybe i need another contest to get orange...

You will get that I am sure!

Can D be solved in O(n)?

Problem F is similar to "Voltage" from JOI Spring Camp 2014: AtCoder oj.uz

It is also on Codeforces

Before I start the contest and for NO reason I decided to take look at problem C first and I found It Crazy a little bit so I decided to not participate in this contest. I am happy to keep my color and not join this stupid contest.

Coward

If you faced a Lion in your way you will fight against him instead of taking your car and escape not to be a "Coward". Right?

Waiting for right contest, only to get positive delta is being coward.

I will have only + delta in my account by this way

Yes, you will, if you keep being coward

Negative delta for a single contest is meaningless.

Skipping a contest is failing to take advantage of a learning opportunity.

DELETED

Why would you compare a CF problem to a lion?

Xinotpyrk And stop making Fake account to participate in the contests I think you are the real Coward here!

Ok

let us see who will get better rank in next contest @Omar_Hafez vs @Xinotpyrk.

I hope C will not be that difficult so that competition can happen.

Hopeforces

I will WIN. (If problem C was easy for sure :) )

Inshallah

Results of this match:Both players managed to solve problems A and B, but Arun_bro1 beat Omar_Hafez by placing 647 ranks higher and solving problemC, which Omar_Hafez failed to solve. Although Arun_bro1 received quite a few Wrong answers on problemAandBat the beginning, he made a comeback by solving problemsB,C, and then finally problemAabout 70 minutes after the contest. This definitely gave Omar_Hafez some room to make his own comeback by solving problemC, which may have given him the lead due to his lower penalties.Winner of this match:Arun_bro1You are Legend bro

can you define coward for me @Omar_Hafez?

Cowards means not brave enough to face any situation.

And he faced the situation !?

This round is really strange. When I was solving B, I literally don't know why I got WA on first two attempts and AC on the third attempt. This is the first time I have this kind of feeling. It took me much longer than expected to solve B, which really brought down my morale. Normally I should be able to solve at least 4 problems and enter top 1000, but this time I only got 2400+ standing with 3 problems solved. This sucks.

Bad days, you know

Can I use the minimum spanning tree to solve E? Just like this question.

How to do E? My idea was to consider every chip as the last remaining chip, then to calculate answer by considering that the chips in the same row will just move towards the selected chip, and chips in the other row would first go towards the cell directly above the selected chip and then in 1 move, move downwards to finally become 1 chip. Am I missing something?

I used 4 status to mark the position of chips in current column. then you can do dp transition.

any body Can Explantion how to solve problem C ?

How to solve C?

Here is my approach: Let's say finally we have the remaining string from s[i...j]. Then answer for this string will be res = max(zero-pref[i-1][0]-suf[j+1][0],pref[i-1][1]+suf[j+1][1]), here I used ternary search as for every i, I need to find optimal j such that this function is minimum and we can see if we traverse j from end towards i value of function will first decrease then increase. So that's how for every i, I found optimal j using ternary search.

Is there a way to solve problem C using recursive dynamic programming?

see my comment above.

A < B< c ~ E < D

How to solve C using

DP?You can find a great solution from Aging1986 a little bit earlier in the comments

It hurts bad when your code gets accepted by just changing l = 1 to l = 0.

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossiblecounter examplefor your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Lenient Vertex Cover: Will add if anyone's stuck on debugging (only till the next 7 days).If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your

submissionandticket(s).Could anybody tell me why 157030318 got AC,but 157022306 got WA?

I'm totally confused.

╥﹏╥

This test case will fail in your code: 1 5 5 LLLLL LLLLL LLLLL LLLLL LLLLR

It should be YES but it gives NO. I tested it locally on my pc and it work but on codefoces custom invocation it will fail

When things pass locally but fail online (see comment from Omar_Hafez), the reason is almost always that you are accessing out of bounds memory by mistake. In this case you were accessing elements s[6][6] but your array's dimensions only allowed for indices from 0 to 5. The changing behaviour depends on what is currently held in the memory accessed inadvertently by s[6][6]. Offline its value was 'ok' so you passed; online its value was 'not ok' so you failed.

jimm89 But this code never reaches s[6][6] it will always be lower than 6 because the flag he made will stop reaching this point

Picture link

It does in custom invocation (see picture). This is something to do with you attempting to read into 's[i] + 1' — it is not behaving as you expect it to.

If you re-index i and j to 0-based, you will pass. Submission with re-indexing — note that I've even reduced to s[5][5] and it's fine.

Cstyle strings need a terminating null character`\0`

at the end. By not reserving the buffer for it, you're going against the rules, hence I'd guess that is what causes this unexpected behavior.In the picture you mention the code will never reach s[6][6] because the flag is 0

if(flag && s[x][y])

That’s true. But the fact that it is 6 6 is still the reason the answer returns NO.

Come on, problem E is really so easy that a simple dp can work it out!!! However, I forgot to give my dp a special judge because I combined the dp in three situations into one--Just the simple code "-(maze[1][j]=='*'&&maze[2][j]=='*')". O.M.G. then I've got wa in the contest and luckily got Accepted 5 minutes after the contest was over... Poor I!

Hi guys, can any one help me what the second loop is doing, a valid solution for C problem.

It finds j such that it is optimal to end up with the segment [i, j] for the given i. As you increase j the number of zeros inside the segment doesn't decrease, while the number of ones outside doesn't increase. You can prove that for larger i's, larger j's will be optimal.

Although the problem was a bit difficult, just because you missed some observations does not mean that problem was terrible. Every Problem has unique observation and implementation... Today i completely misunderstood D('_')

Idea for C: If you select the segment l,r you could find the score on that segment. Now you can search for each i, pretend that is r. Now you answer two questions for the segment ending at ith. 1. What's the best case such that at least as many deleted 1s as 0 on that segment? 2. What's the best case such that at least as many 0s as the 1s deleted?

For both cases, we could find out the number of 1s deleted from the end until ith easily. Now whats the best l for each case? First case favors l being as close to 0th index as much as possible, second case favor l as close to ith as possible. You can binary search this, if you had a prefix sum count for 1s and 0s.

How the answer of this testcase is 9 (Problem E):

1

6

* * * . * *

* . * * * *

I don't know why testcase is not being printed properly, maybe asterisk sign is doing something. If the test case is still not clear please go this ideone link : https://ideone.com/eJEMfj

(2, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (2, 4) -> (2, 5) -> (1, 5) -> (1, 6) -> (2, 6)

My Accepted solution for problem E is here: https://codeforces.com/contest/1680/submission/157075695

and how does it answer my query?

My Solution using binary search and cost function analysis :As given in the problem , The cost of removal is dependent on two parameters : the number of characters

0s leftin the string and the number of characters1s removedfrom the string.It would be always optimal to remove leading and trailing zeroes from the string. So we will remove them from both the sides until we get both leftmost and rightmost element ones.$$${..................................................................................................}$$$

Now let us consider the total counts of ones and zeroes as $$${C_0}$$$ and $$${C_1}$$$ respectively and their prefix counts are stored in $$${o}$$$ and $$${z}$$$ array. Also Note that both prefix $$${zeroes}$$$ and $$${ones}$$$ are $$${increasing}$$$ functions.

Cost function to obtain a substring $$${S(i\hspace{1.5mm},\hspace{1.5mm}j)}$$$ can given as

$$$\hspace{40mm}\underline{Cost(i\hspace{1.5mm},\hspace{1.5mm}j) = max(C_1 - 1 +o(i) - o(j) \hspace{1.5mm} , \hspace{1.5mm} z(j) - z(i))}$$$

Now , let us consider if their exists a pair $$${(i , j)}$$$ with a cost less than equal to $$${K}$$$ i.e.:

$$$\hspace{50mm} {max(C_1 - 1 +o(i) - o(j) \hspace{1.5mm} , \hspace{1.5mm} z(j) - z(i)) \le K}$$$

So for a particular index $$${i}$$$ we need to have $$${j}$$$ such that $$${j \ge i}$$$ satisfying :

$$$\hspace{55mm}$$$

$$${z(j) \le z(i) + K}$$$$$$\hspace{55mm}$$$

$$$ {o(j) \ge C_1 - 1 + o(i) - K}$$$That can be done by finding the rightmost index satisfying first condition(for $$${z}$$$) and leftmost index satisfying second condition (for $$${o}$$$) using binary search. Thus for each index it takes $$${O(logn)}$$$ time . In total it becomes $$${O(nlogn)}$$$ for

predicate checkand finally in total $$${O\left(n(logn)^2\right)}$$$ involving binary search to minimize the net cost.Immature people will downvote you for no reason ,for them meme posts and useless comments is the thing to live for, rather than some useful stuff. You just take 1 sec to downvote not realizing the worth of other's time to help you. I always love to share my solutions along with proper formatting so that anyone who sees it can easily understand but it makes sense some people are too dumb to even understand that. It hurts when some useful comment gets downvoted and some meme gets 100s of upvotes. To me : bro lets just stop caring about these toxic people :)

lol, do u even realise the reason why your comment was downvoted? u don't soft wrap lines which leads to horizontally scalable wide screen making the comment section clunky to navigate for others.

but if your comment is downvoted to a certain point the screen becomes stable again

Congrats Xaxixin!

Congrats antOntrygubX_y

Well, does anyone have some ideas for the problem D?

Let the original sum of array values be $$$sum$$$. If $$$\lceil \dfrac{abs(sum)}{k}\rceil$$$ is greater than the count of $$$i$$$ where $$$arr[i]=0$$$, $$$ans=-1$$$.

Otherwise, the maximum visited points will be the distance moved from the smallest point to the largest point, which is range sum in the final array.

We can iterate on all the $$$N^2$$$ ranges. At each range let's see the largest and smallest sums $$$sum_1$$$ and $$$sum_2$$$ we can have by considering the count of $$$i$$$ where $$$arr[i]=0$$$ at that range, then update $$$ans$$$ by $$$max(ans, abs(sum_1)+1)$$$ and $$$max(ans, abs(sum_2)+1)$$$ (the $$$+1$$$ is to account for the point at the range start).

Submission

Thanks a lot.

Big "thank you" for the streaming after contest, learned alot!

I don't know why but I got different answers for same code 1680C in my compiler and in codeforces. Is this a glitch or what?

It is called undefined behavior (sometimes because you want to access something you can't access like outside the array).

In your code lines 220 and 244 you have to flip the conditions because what you write first got executed first.

The second thing is that you don't give the variable n a value. I think you forgot to write "n = s.size();" (I think two times needed).

you can check my last submission on the problem, I got WA on test 2 after fixing these issues in your code.

Thanks for help!

It happens some time.

I used ternary search in prob C but I didn't know that it doesn't work if the function is not "strictly" increasing + decreasing. But my solution got accepted due to weak pretests.

unlucky

:(

When rating changes.

Why in educational codeforces round(div2) on the first places are coders for who this contest is unrated ? I see that in normal div.2 places are held only by the people for who this contest is rated, but in educational first places are held by people who are over 2200, can somebody explain ? I'm just curios , thank you.

I was running my code on ideone in default setting and someone copied my code and I was not aware about that.I don't have idea that someone can see my solution on ide during contest, that's why i recieved a msg that your solution is collided with others. I will take care from next time. I have not used any unfair means while giving the contest.I have solved all the problems by myself. Please restore my submissions and give me ratings for the contest. I will stop using ideone from now. I promise it won't happen again.

editorial late op

rating change late op

Hey, can anyone help me with problem C. I've thought of a greedy solution whose basic idea was to remove the max number of zeros by removing min number of ones and repeat this till the string becomes empty from zeros.I tried checking with many edge cases but cannot see what is the mistake ive made. So plz can anyone help me I have commented the code for better understanding https://ideone.com/bBoj0b

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Did any one solve C problem using two pointer ??

I was thinking of dp so first step of recursive solution i wrote, i was unable to memoize it if anyone can help it will be great. Thank You in advance.