Thanks for the participation!

1700A - Optimal Path was authored and prepared by 74TrAkToR

1700B - Palindromic Numbers was authored by fedoseev.timofey and prepared by _overrated_

1700C - Helping the Nature was authored and prepared by Igorbunov

1700D - River Locks was authored and prepared by Ziware

1700E - Serega the Pirate was authored by fedoseev.timofey and prepared by talant

1700F - Puzzle was authored and prepared by Olerinskiy

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

D is solvable without binary search.

If $$$t_j<max(⌈pref_i/i⌉)$$$ then there is no solution.

Otherwise the answer is $$$⌈sum(v)/t_j⌉$$$.

There is my solution 161288493

Yes exactly. This works because you can assume that for a prefix, each pipe provides $$$t$$$ units of water(because if any water is "wasted" then all tanks in front of that pipe are filled). Since adding more pipes in front of a pipe does not contribute to tanks before it, if $$$t$$$ is greater than the minimum time required to fill the entire thing then that assumption is valid.

To add, if the first assumption is true, then the answer is $$$⌈sum(v)/tj⌉$$$ because you can simply put pipes on the first $$$⌈sum(v)/tj⌉$$$ indices. This is optimal: any more is clearly unnecessary, and any less wouldn't work because the water produced would be less than the sum.

I solved C without prefix or suffix, but the starting idea is the same.

Solution with explanation why it works: just store the difference between 2 consecutive elements in an array, a1[2] shows the difference between the 1st and the 2nd element, (note: a1[1] is equal to the 1st element).

in a1[1] we keep the number to which all the other elements will be equal to at some point(initially it is the 1st element) and after that I can make all equal to 0 by just a1[1] moves, now let's see how do we keep it. Let's have a look on 2 different cases.

1st case: we have something like 3, 4, 5 etc. In this cases the difference is positive. So I can just simply do ans += a1[i], so at 1st ans will be 1 because I need 1 move to make 4 equal to 3 and also 1 move to make 5 equal to 4, so in total 2 moves to 1st make 5 equal to 4 and then both 4 and 4 equal to 3 in just 1 move that's why this solution is optimal.

2nd case: etc we have something like 5, 4, 3 where we have a1[i] < 0, in this case we can make ans = ans — a1[i], so ans is again going to be positive, but the difference is that now we have to make a1[1] += a1[i], because since we found out that there is a smaller number then we have to make them all equal to a1[1] + a1[i] which makes a1[1] smaller since a1[i] is negative so we still get the number a1[1] which is what we make all the elements equal to.

Code link — 161258270

This is a nice problem. What I did is similar to yours, but a little bit easier, what I did is first we add up sum += abs(a[i]-a[i-1)) and then we keep track of the change so that we can add one to all the numbers, which is simply the case when a[i] > a[i-1] and we do change += abs(a[i]-a[i — 1], then the final number that makes the array the same is the last number in the array — change and then the number of times we can add is abs(last number — change) and for whole program we only need one for loop!! https://codeforces.com/contest/1700/submission/167360800

Nice Round! Finally became Specialist!

my solution for problem C but I am not able give some formal proof for this

solutionwe are iterating from left to right , suppose we are at position i all 0 to i-1 position will be equal to some minimum value let it be mn . suppose we have used suffix operation s times before reaching it so current value will be arr[i]-s

if current value is less than minimum element mn then we will use prefix operation to make prefix equal to current value . if current value is greater than mn then we will use suffix operation to make it equal to mn and we will repeat this operation for whole array

our final ans will be total prefix operation used + suffix operation + no operation to convert mn to 0 .

code c++Problem C. I understand why the given method works, but what is the proof/intuition behind the solution that the given method is minimum number of steps??

My intuition: You can alter the "height" of the entire array (either decrease or increase it), so instead of trying to make the heights of all trees $$$0$$$, I tried making them equal to the first element of the array (say $$$curh$$$), and then performing operations on the entire array at the end.

If $$$a[i] \neq a[i+1]$$$, then we would have to perform some operations to make them equal:

So, basically adding $$$abs(a[i] - a[i+1])$$$ $$$\forall$$$ $$$i$$$ to $$$ans$$$, and decreasing the $$$curh$$$ by the same amount when $$$a[i] > a[i+1]$$$, and the final answer would be $$$(ans + abs(curh))$$$.

Code — 161312307

Exuse me, may I ask a question?

Does $$$curh$$$ mean the final leval that is equal all the height of the trees

$$$curh$$$ is the current height of the prefix of trees at $$$i$$$, that we have made equal in height as we move from $$$1$$$ to $$$n$$$, but yeah at $$$n$$$ it would be equal to the height of all trees.

Thank you very much. Your solution is very helpful to me.

excellent solution man!

How is this pref[i]/i coming, I understand that if all i-1 are filled, then each second i unit of water falls into ith one. But the the i-1 vessels would not be filled simultaneously, may be (i-1) gets filled first and some amount falls from that to ith one, I mean it's vaguely clear how it's coming but i dont feel any strong maths , can anyone please explain

My approach is a bit different from the editorial (greedy), but it involved $$$(pref[i]/i)$$$.

So basically, $$$ \forall$$$ $$$i$$$ from $$$1$$$ to $$$k$$$ where $$$k$$$ is the number of taps you would open, we would need $$$(time \times i) \geq pre[i]$$$ so that the $$$i^{th}$$$ lock can be filled, where $$$(time \times i)$$$ is the volume that first $$$i$$$ taps would fill, and $$$pre[i]$$$ is the total volume of first $$$i$$$ locks. Which is equivalent to $$$time \geq \lceil pre[i]/i \rceil$$$. Instead of iterating through first $$$k$$$ elements of $$$pre[i]$$$ every query, we can store prefix max of $$$\lceil pre[i]/i \rceil$$$ and check if $$$time \geq max(\lceil pre[i]/i \rceil )$$$.

See, keep it simple.

pref[i] is the total volume capacity to be filled if we only consider the 1st i vessels. To get the minimum time to fill all i vessels, we open all the i taps. Each tap ejects 1 unit/sec. So minimum time required to fill all i vessels is at least pref[i] / i. ( I am not saying that min time = pref[i]/i, but it is lower bounded by pref[i]/i. )

I didn't understand why above method works in problem no. C Can anyone please explain me what is the intuition behind the solution why it works?

my solution is kind of similar to the one explained above, I explained why the solution works with example in this comment — https://codeforces.com/blog/entry/103978?#comment-924743

thanks

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.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).In problem no. C Here is my understanding

lets take a example a = [1, -2, 3, -4, 5]

so lets prepare an array of diff b where b[i] = a[i] — a[i-1]; b = [1, -3, 5, -7, 9]

lets initialize our res = 0;

now for a[0], a[1] we want to make this 2 element equal. how can we do that ? if -> 1st element is less than 2nd element we will perform dec operation on right side of the array else -> we will perform dec operation on left side of the array

so for a[0], a[1] diff is b[1] = -3 (a[0] < a[1]); so we have to dec left side of array by 3 units ( res += 3 units); now a[0] and a[1] will be equal to -2 so we will update b[0] = -2 because in the end we have to make every element to 0;

and for a[1] and a[2] diff = 5 a[2] > a[1] so we have to dec right side of array by 5 units since diff will remain same bw elements so we don't have to bother for actual number (res += 5 units) since right side will dec so no need to update b[0]

now after perfoming all the operation every element will be equal to updated b[0]; and at last we will do (res += abs(b[0]);

This is My Solution — 161315402

but how can you say that this will give min operations

Thank you for your solution!

Please add this editorial in the Contest materials.

Could someone figure out why my submission to E is getting TLE on test case 48? I suspect that it has something to do with the sets I'm using inside my loop, but I'm not sure. I've tried pruning it for a while, but to no avail. Help would be appreciated! Submission to E

Nevermind, I figured out why. :')

Problem E.

Example #2:

2 3

1 6 4

3 2 5

$$$6>4$$$ and $$$5>4$$$ , so "4" is bad cell. But if we choose 4 , there isn't any valid way to make the puzzle solvable.Then we will get wrong answer "2" .

Did I get it wrong ? Thx.

We can choose not only the bad cell itself, but also its neighbour to make it not bad. In this example, we can choose 4's neighbour 6 and swap it with 2, then we find a way only swap once.

I see . I forgot its neigbour . Thx :)

Hello sir, To be honest, I cheated in this contest (#802) by copy pasting code from Telegram, why I didn't get booked for plagiarism? Is the Codeforces Plagiarism checker down? Or the ratings yet to be updated? I politely request you to please reduce my rating in my other account for my crimes. Kindly look into this.

Hello sir, To be honest, I cheated in this contest (#802) by copy pasting code from Telegram, why I didn't get booked for plagiarism? Is the Codeforces Plagiarism checker down? Or the ratings yet to be updated? I politely request you to please reduce my rating in my other account for my crimes. Kindly look into this.

Hello sir, To be honest, I cheated in this contest (#802) by copy pasting code from Telegram, why I didn't get booked for plagiarism? Is the Codeforces Plagiarism checker down? Or the ratings yet to be updated? I politely request you to please reduce my rating in my other account for my crimes. Kindly look into this.

Bit confused by this statement in the editorial for question div2 C:

How are the prefix and suffix sums used to compute the final array? And what is $$$|x|$$$?

Thank you.

In my opinion, you can solve the problem in this way.

Use an integer $$$a$$$ to save the minium number of operations to "cut" the trees

in the same height. Consider that when you meet a "new" tree which has a height of $$$h$$$. There are two conditions.don't have tochange the value of $$$a$$$We can find that in both situations, you have to operate $$$|h - a|$$$ times (This is the reason to add $$$|h - a|$$$ to the answer, $$$|h - a|$$$ is the $$$x$$$ in the official solution.

In the end, you should add |a| operations to decrease / increase all the height to 0.

This is my code:161360992

Thanks to user AAK who told me this method.

I'm sorry that I am not good at using English to write articals. I hope this message will help you.

Ah, I think I understand! Thank you!

.

In C prblm , how did ch_egor come up with Difference Array ? What's the intuition behind it ?

I understand the solution that the editorial proposes for C, but why is that optimal? Is there some sort of semi-formal proof one can create? I'm having a hard time understanding why it's optimal.

For C, here is how I understand the proof for optimality.

We know that in the final state of (0,0..,0,0), the sum of all |d_i| = |a_{1}-a_{0}| + ... + |a_{n}-a_{n-1}| equals 0.

Now for each step of the operation, any of the 3 operations allowed can only change 1 of the n |a_{i+1}-a_{i}|. For example, given (a_{1},a_{2}...,a_{d-1},a_{d}, a_{d+1}, ...a_{n}), if we decrement (a_{d},...a{n}) by 1, then only |d_{d}|=|a_{d}-a{d-1}-1| changes, while the rest of |d{i}| stays the same.

Since the solution is designed in such a way to decrease each of the |d_{i}| to 0 sequentially, (ie |a_{1}-a_{0}| + ... + |a_{n}-a_{n-1}| is a decreasing sequence), it is clearly optimal.

For completeness, here is how the path in question A is optimal.

For any other path selected, there must be an instance of (i,j) -> (i+1,j) -> (i+1,j+1), of which cost could be reduced if we had opted for (i,j) -> (i,j+1) -> (i+1,j+1) instead,

If we replaces all such instances to reduce the cost of any given path, we will end up with the optimal for which there is no more such instances, and so the cost is minimised.

how to solve problem c

can anybody please help me to find why my code is giving RE for Problem : B

Your text to link here...

Problem C, here's my code that follows the editorial idea.

Was here anybody who didn't think about the solution of Problem C and solved it with segment tree?