By awoo, history, 9 months ago, translation,

Hello Codeforces!

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.

Apply | Scholarship

Harbour.Space University Team

UPD: Editorial is out

• +169

 » 9 months ago, # |   +31 Wish i will solve problem ABCDE and go orange this time!!!
•  » » 9 months ago, # ^ |   0 Good luck.
•  » » 9 months ago, # ^ |   0 Me too
•  » » » 9 months ago, # ^ |   0 Best wishes!
•  » » 9 months ago, # ^ |   +1 nice try
 » 9 months ago, # | ← Rev. 3 →   +47 nvm
 » 9 months ago, # |   +7 good luck to every one :)
 » 9 months ago, # |   0 Good luck everyone and try your best.（＾ω＾）
•  » » 9 months ago, # ^ |   0 Good luck to you too.
 » 9 months ago, # |   0 I can't wait to get back the rate I lost in #789!!!ψ(｀∇´)ψ
 » 9 months ago, # |   +13 rotavirus face reveal?
 » 9 months ago, # |   -9 All the best everyone!!! Hoping that everyone will get a positive delta
•  » » 9 months ago, # ^ |   0 But it's not possible that everyone will get positive.
 » 9 months ago, # |   +1 Do your best guys and never give upGOOD LUCK!
•  » » 9 months ago, # ^ |   0 ok
 » 9 months ago, # |   0 I hope to solve A,B,C with good speed to get some positive delta.
 » 9 months ago, # |   0 Good luck everyone!
 » 9 months ago, # |   +17 Wishing everyone luck to overcome the curse of Friday the 13th.
 » 9 months ago, # |   0 Hoping to solve A B C and become green.
 » 9 months ago, # |   0 Good luck
 » 9 months ago, # |   +12 I Hope to solve A B C D and become specialist.
 » 9 months ago, # |   +12 I didn't participate contest for a long time, very happy to be back and good luck to everyone!
 » 9 months ago, # |   0 can u provide the score distribution?
•  » » 9 months ago, # ^ |   +12 Ig there is no score distribution in educational rounds.
•  » » 9 months ago, # ^ |   0 Problems are not weighted in educational rounds.
 » 9 months ago, # |   +1 Wish I will go outside the infinite loop between Newbie and Pupil :)Who is like me !!
•  » » 9 months ago, # ^ |   +6 wish i can stay blue!!
 » 9 months ago, # |   -9 How many questions I need to solve to be a specialist if my current rating is 1207 ? Can Somebody tell me ?
•  » » 9 months ago, # ^ |   +3 just solve at least three problems as fast as you can
 » 9 months ago, # |   +12 Congrats to the gold and silver medalists!
 » 9 months ago, # |   +1 Is it allowed to browse the internet during the contest?
•  » » 9 months ago, # ^ |   0 Yes
•  » » 9 months ago, # ^ |   +14 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
 » 9 months ago, # | ← Rev. 2 →   +6 Happy to see Kazakh names on the leaderboard! Good luck everyone!
»
9 months ago, # |
Rev. 2   +27

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 way more 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 not in the set, or 0 if it was in the set.

•  » » 9 months ago, # ^ |   +6 agreed. I thought E was quite complex until I see the huge number of people who solved it.
•  » » 9 months ago, # ^ |   +75 I don't agree about C.I felt all the three announcements made are redundant
•  » » » 9 months ago, # ^ |   +4 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.
•  » » » » 9 months ago, # ^ |   0 I Agree.
•  » » » » » 9 months ago, # ^ |   +21 As I already said, these announcements were made to decrease the number of questions.
•  » » 9 months ago, # ^ |   +68 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 maximum of two values, not the sum of 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.
•  » » » 9 months ago, # ^ |   0 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 the optimal path.Unrelatedly, thank you for the "additional constraints" on input rather than saying "It is guaranteed". :)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   +1 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.
•  » » 9 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 Thank you, I'll upsolve it soon.
•  » » 9 months ago, # ^ |   0 learn how to use binary search. (*)
 » 9 months ago, # |   +5 104 minutes by just staring at screen : ( and trying
 » 9 months ago, # |   0 I don't understand D at all!
•  » » 9 months ago, # ^ | ← Rev. 2 →   +19 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$.
•  » » 9 months ago, # ^ |   0 me too...
 » 9 months ago, # |   +1 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!
•  » » 9 months ago, # ^ |   0 I used dp.
•  » » » 9 months ago, # ^ |   0 Would you mind to run me through your idea briefly?
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +7 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]$.
•  » » » » » 9 months ago, # ^ |   0 Yeah, thats pretty nice solution. Thank you!
•  » » » » » 9 months ago, # ^ |   +3 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.
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 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. $N_{0\ in\ result\ substring}\ =\ N_{1\ in\ removed\ string}\ \ => \\ N_{0\ in\ result\ substring}\ +N_{1\ in\ result\ substring}\ =\ N_{1\ in\ removed\ string}\ +N_{1\ in\ result\ substring}\ \ => \\ length\ of\ result\ substring\ =\ N_{1\ total}$
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 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])
•  » » » » » » 9 months ago, # ^ |   0 Because $pre[i]$ is non decreasing.
•  » » » » » » » 9 months ago, # ^ |   0 Can you also tell why you took i = j — pre[N] in second case, I am not getting it?
•  » » » » » » » » 9 months ago, # ^ |   0 That’s also because $i-pre[i]$ is non decreasing.
•  » » » » » » » » » 9 months ago, # ^ |   0 Thanks
•  » » » » » » » » » 9 months ago, # ^ |   0 Can you tell what exactly is j-pre[N]? I tried but I am not getting it, sorry to disturb again and again.
•  » » » 9 months ago, # ^ |   +9 what was the idea for DP ? I have solved with binary and greedy
•  » » » » 9 months ago, # ^ |   0 You have the answer above ^
•  » » 9 months ago, # ^ |   +7 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.
•  » » » 9 months ago, # ^ |   0 I like it, it is a good one too!
•  » » » 8 months ago, # ^ |   0 can u explain its time compl.
•  » » 9 months ago, # ^ |   +3 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.
•  » » » 9 months ago, # ^ |   0 Could you explain it a bit more, please?
•  » » » » 9 months ago, # ^ |   0 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).
•  » » » » » 9 months ago, # ^ |   0 I see the idea, thats a great one!
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 It can be done with binary search + sliding window(btw isn't sliding window a subset of two pointers?)Submission
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 I used ternary search.157084549 Edit: and then got hacked! Can anyone give me proper implementation of ternary search to find minimum
•  » » 9 months ago, # ^ | ← Rev. 3 →   +11 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
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Nice idea. I've tested it without storing arrays of prefix/suffix sums: 157096927
•  » » » » 9 months ago, # ^ |   0 I didn't notice that the two arrays were not necessary, thanks!
•  » » » 6 months ago, # ^ |   0 excellent idea.... Thanx for sharing
•  » » 9 months ago, # ^ | ← Rev. 4 →   0 I 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
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I used binary search the answerAssume 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)
•  » » » 9 months ago, # ^ | ← Rev. 4 →   +1 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+1
•  » » » » 9 months ago, # ^ |   +1 Hey, 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.
•  » » 9 months ago, # ^ |   0 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.
•  » » 9 months ago, # ^ |   0 I used ternary search. Idea is "what is the optimal ans if i keep X 1's in my answer".
 » 9 months ago, # |   +1 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.
•  » » 9 months ago, # ^ |   0 Code 157056549
•  » » 9 months ago, # ^ |   0 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).
•  » » 9 months ago, # ^ |   0 what if both zeros are equally far from both sides :(
 » 9 months ago, # |   0 sry to say but bad problem statement :(
 » 9 months ago, # |   0 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.
 » 9 months ago, # |   +3 Who tested C.. the pretests are very strong lmao.
 » 9 months ago, # |   0 the main observation about C problem is that you need to remove 1's >= 0's
•  » » 9 months ago, # ^ |   0 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).
•  » » » 9 months ago, # ^ |   0 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
•  » » » » 9 months ago, # ^ |   0 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.
•  » » » » » 9 months ago, # ^ |   0 I understand what are you trying to say, but 0's in my statement are the ones which left not removed.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 8 months ago, # ^ |   0 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
•  » » » » 8 months ago, # ^ |   0 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.
 » 9 months ago, # |   +4 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...
•  » » 9 months ago, # ^ |   0 You will get that I am sure!
 » 9 months ago, # |   0 Can D be solved in O(n)?
 » 9 months ago, # |   +20 Problem F is similar to "Voltage" from JOI Spring Camp 2014: AtCoder oj.uz
•  » » 9 months ago, # ^ |   +16 It is also on Codeforces
 » 9 months ago, # |   -48 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.
•  » » 9 months ago, # ^ |   +32 Coward
•  » » » 9 months ago, # ^ |   -42 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?
•  » » » » 9 months ago, # ^ |   +20 Waiting for right contest, only to get positive delta is being coward.
•  » » » » » 9 months ago, # ^ |   -24 I will have only + delta in my account by this way
•  » » » » » » 9 months ago, # ^ |   +12 Yes, you will, if you keep being coward
•  » » » » » » 9 months ago, # ^ |   +11 Negative delta for a single contest is meaningless.Skipping a contest is failing to take advantage of a learning opportunity.
•  » » » » » » » 9 months ago, # ^ | ← Rev. 3 →   -9 DELETED
•  » » » » 9 months ago, # ^ |   +6 Why would you compare a CF problem to a lion?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   -9 Xinotpyrk And stop making Fake account to participate in the contests I think you are the real Coward here!
•  » » » » 9 months ago, # ^ |   0 Ok
•  » » » » 9 months ago, # ^ |   +2 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.
•  » » » » » 9 months ago, # ^ |   0 Hopeforces
•  » » » » » 9 months ago, # ^ |   0 I will WIN. (If problem C was easy for sure :) )
•  » » » » » » 9 months ago, # ^ |   0 Inshallah
•  » » » » » » » 9 months ago, # ^ |   +4 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 problem C, which Omar_Hafez failed to solve. Although Arun_bro1 received quite a few Wrong answers on problem A and B at the beginning, he made a comeback by solving problems B, C, and then finally problem A about 70 minutes after the contest. This definitely gave Omar_Hafez some room to make his own comeback by solving problem C, which may have given him the lead due to his lower penalties.Winner of this match: Arun_bro1
•  » » » » » » » » 9 months ago, # ^ |   0 You are Legend bro
•  » » 9 months ago, # ^ | ← Rev. 2 →   +2 can you define coward for me @Omar_Hafez?
•  » » » 9 months ago, # ^ |   0 Cowards means not brave enough to face any situation.
•  » » » » 9 months ago, # ^ |   -8 And he faced the situation !?
 » 9 months ago, # |   -13 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.
•  » » 9 months ago, # ^ |   0 Bad days, you know
 » 9 months ago, # |   +1 Can I use the minimum spanning tree to solve E? Just like this question.
 » 9 months ago, # | ← Rev. 2 →   +3 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?
•  » » 9 months ago, # ^ |   0 I used 4 status to mark the position of chips in current column. then you can do dp transition.
 » 9 months ago, # |   0 any body Can Explantion how to solve problem C ?
 » 9 months ago, # |   0 How to solve C?
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 Is there a way to solve problem C using recursive dynamic programming?
•  » » 9 months ago, # ^ |   0 see my comment above.
 » 9 months ago, # | ← Rev. 2 →   -20 A < B< c ~ E < D
 » 9 months ago, # |   0 How to solve C using DP ?
•  » » 9 months ago, # ^ |   0 You can find a great solution from Aging1986 a little bit earlier in the comments
 » 9 months ago, # |   0 It hurts bad when your code gets accepted by just changing l = 1 to l = 0.
 » 9 months ago, # | ← Rev. 2 →   +8 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for 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. A: Minimums and Maximums B: Robots C: Binary String D: Dog Walking E: Moving Chips F: 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 submission and ticket(s).
 » 9 months ago, # | ← Rev. 2 →   0 Could anybody tell me why 157030318 got AC,but 157022306 got WA?I'm totally confused.╥﹏╥
•  » » 9 months ago, # ^ |   +3 This test case will fail in your code: 1 5 5 LLLLL LLLLL LLLLL LLLLL LLLLRIt 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
•  » » 9 months ago, # ^ |   +2 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.
•  » » » 9 months ago, # ^ |   0 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
•  » » » » 9 months ago, # ^ | ← Rev. 5 →   0 Picture linkIt 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.
•  » » » » » 9 months ago, # ^ |   +11 C style 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.
•  » » » » » 9 months ago, # ^ | ← Rev. 4 →   0 In the picture you mention the code will never reach s[6][6] because the flag is 0if(flag && s[x][y])
•  » » » » » » 9 months ago, # ^ |   0 That’s true. But the fact that it is 6 6 is still the reason the answer returns NO.
 » 9 months ago, # |   0 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!
 » 9 months ago, # | ← Rev. 3 →   0 Hi guys, can any one help me what the second loop is doing, a valid solution for C problem. void run_case() { string S; cin >> S; int N = int(S.size()); int zeros = int(count(S.begin(), S.end(), '0')); int ones = int(count(S.begin(), S.end(), '1')); assert(zeros + ones == N); vector prefix(N + 1, 0); for (int i = 0; i < N; i++) prefix[i + 1] = prefix[i] + (S[i] - '0'); int best = min(zeros, ones); for (int i = 0, j = 0; i < N; i++) { while (j < N && j - i - (prefix[j] - prefix[i]) < ones - (prefix[j] - prefix[i])) j++; best = min(best, max(j - i - (prefix[j] - prefix[i]), ones - (prefix[j] - prefix[i]))); } cout << best << '\n'; } 
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 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('_')
 » 9 months ago, # |   0 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.
 » 9 months ago, # | ← Rev. 3 →   0 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
•  » » 9 months ago, # ^ |   +3 (2, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (2, 4) -> (2, 5) -> (1, 5) -> (1, 6) -> (2, 6)
•  » » 9 months ago, # ^ |   0 My Accepted solution for problem E is here: https://codeforces.com/contest/1680/submission/157075695
•  » » » 9 months ago, # ^ |   0 and how does it answer my query?
 » 9 months ago, # | ← Rev. 3 →   -22 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 left in the string and the number of characters 1s removed from 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 check and finally in total ${O\left(n(logn)^2\right)}$ involving binary search to minimize the net cost.
•  » » 9 months ago, # ^ |   -11 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 :)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 share my solutions along with proper formatting 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
 » 9 months ago, # |   +19 Congrats Xaxixin!
 » 9 months ago, # |   +14 Congrats antOntrygubX_y
 » 9 months ago, # |   0 Well, does anyone have some ideas for the problem D?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +4 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
•  » » » 9 months ago, # ^ |   0 Thanks a lot.
 » 9 months ago, # |   0 Big "thank you" for the streaming after contest, learned alot!
 » 9 months ago, # |   0 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?
•  » » 9 months ago, # ^ |   +2 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.
•  » » » 9 months ago, # ^ |   0 Thanks for help!
•  » » 9 months ago, # ^ |   0 It happens some time.
 » 9 months ago, # |   0 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.
•  » » 9 months ago, # ^ |   0 unlucky
•  » » » 9 months ago, # ^ |   0 :(
 » 9 months ago, # |   0 When rating changes.
 » 9 months ago, # |   0 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.
 » 9 months ago, # | ← Rev. 2 →   -11 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.
 » 9 months ago, # |   0 editorial late op
•  » » 9 months ago, # ^ |   0 rating change late op
 » 9 months ago, # |   0 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
 » 9 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 9 months ago, # |   0 Did any one solve C problem using two pointer ??
 » 9 months ago, # | ← Rev. 2 →   0 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. #include #define ll long long int #define pb push_back #define ff first #define ss second #define rapid ios_base:: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define ld long double #define tc ll test; cin>>test; while(test--) using namespace std; vector> vec( 10000 , vector (10000, -1)); ll dp(ll i,ll j ,ll zero,ll one,string s){ // if(i==j) return max(zero,one); if(zero==one ){ return one; } if(one>zero){ return zero; } if(vec[i][j]!=-1){ return vec[i][j]; } if(s[i]=='1' && s[j]=='1'){ return vec[i][j] = 1+min(dp(i+1,j,zero,one+1,s),dp(i,j-1,zero,one+1,s)); } else if(s[i]=='0'){ return vec[i][j] =dp(i+1,j,zero-1,one,s); } else{ return vec[i][j] = dp(i,j-1,zero-1,one,s); } } void solve(){ string s; cin>>s; ll n =s.size(); ll ans =INT_MAX; ll zero = count(s.begin(),s.end(),'0'); ll one = 0; ans = dp(0,n-1,zero,one,s); if(ans==0){ cout<