Привет, Codeforces!
В 13.05.2022 17:35 (Московское время) состоится Educational Codeforces Round 128 (рейтинговый для Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Harbour.Space берет верх над SWERC, выиграв золото и серебро впервые в своей истории, и примет участие в Финале ICPC. Поздравляем всех наших участников и тренеров, которые сделали это реальностью!
Это очень важный момент в многолетнем сотрудничестве Harbour.Space и Codeforces: организовано 127 образовательных раундов и большой Harbour.Space Scholarship Contest, прошедший 22 июля прошлого года. Мы выбрали победителей того соревнования (early-morning-dreams, Meijer и amanbol), чтобы сформировать наши нынешние команды.
С момента своего создания одной из целей Harbour.Space было выиграть SWERC и конкурировать на высоком уровне в ICPC в целом. 24 апреля эта цель была достигнута, когда команда RAW POTS из Harbour.Space (читай наоборот!) выиграла золотую медаль и в общем зачете у лучших соперников из Западной Европы.
Команда Raw Pots — золотой медалист:
Maksym Oboznyi (MaksymOboznyi), Marco Meijer (Meijer), и Danil Zashikhin(early-morning-dreams)
Команда Kempirqosaq — серебряный медалист:
Temirlan Baibolov (bthero), Dinmukhamed Tursynbay (DimmyT), и Amanbol Kanatuly (amanbol).
Команда Harbour.Backspace — заняли 27е место:
Anier Velasco (aniervs), Fadi Younes, и Ekaterina Podruzhko.
Преподаватели, нынешние студенты, выпускники и все, кто связан с Harbour.Space, хотели бы поздравить победителей и участников SWERC 2021-2022 с прекрасным выступлением и поблагодарить за всю проделанную работу.
Как обычно, мы всегда рады видеть участников Codeforces в качестве наших студентов здесь, в Harbour.Space. Вот почему мы рекомендуем вам подать заявку на участие в нашей программе обучения в партнерстве с Hansgrohe в качестве Kotlin-разработчика до 31 мая 2022 года.
Команда университета Harbour.Space
UPD: Разбор опубликован
Wish i will solve problem ABCDE and go orange this time!!!
Me too
Best wishes!
nice try
nvm
good luck to every one :)
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
Do your best guys and never give up
GOOD LUCK!
Только A B C и все!!! Ты должен постараться и решить все задачи раунда.
Wishing everyone luck to overcome the curse of Friday the 13th.
Привет всем и удачи в сегодняшнем раунде вы все всё сможете постарайтесь решить как можно больше задач
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 luck to 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 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.
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 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.
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". :)
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.
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.
what was the idea for DP ? I have solved with binary and greedy
You have the answer above ^
I did it using Binary search
We 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!
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 sharing
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
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
monotonicandcontinuousfunction? 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
Xbetween[low, hi]that can be generated by removing some prefix and suffix, reducing the original string to stringS'.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 toX+1, orX-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 costhi. All values betweenX -> hiwill 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.me/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 :(
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
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...
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.
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 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
You are Legend bro
can you define coward for me @Omar_Hafez?
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.
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/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.
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).
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.
C style strings need a terminating null character
\0at 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.me/contest/1680/submission/157075695
Congrats early-morning-dreams!
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.
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.
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
:(
If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking
If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking
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
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).