Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

ch_egor's blog

By ch_egor, 2 years ago, translation, In English

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...
  • Vote: I like it
  • +82
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +108 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

»
2 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

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

»
2 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

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

solution
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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??

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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:

    • If $$$a[i] > a[i+1]$$$, then we would have to decrease the prefix ending at $$$i$$$, and we would require $$$(a[i] - a[i+1])$$$ operations. This would also decrease the height of the array behind $$$i$$$ ($$$curh$$$) by $$$(a[i] - a[i+1])$$$.
    • If $$$a[i] < a[i+1]$$$, then we would have to decrease the suffix ending at $$$i+1$$$, and we would require $$$(a[i+1] - a[i])$$$ operations. Note, this would not affect $$$curh$$$, but would decrease all elements after $$$i+1$$$ as well, so $$$a[k+1]-a[k]$$$ $$$\forall$$$ $$$(i < k < n)$$$ would be preserved.

    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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Exuse me, may I ask a question?

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

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        $$$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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 )$$$.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem no. C Here is my understanding

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

  1. now we want convert this array into such an array where every element is same whether it is 0 or not;
  2. there is one clue here is that while dec or increasing the diff bw elements will remain same.

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

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please add this editorial in the Contest materials.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Let's calculate the final array using prefix and suffix sums for $$$O(n)$$$. Note that it will consist of the same numbers. Add $$$|x|$$$ to the answer, where $$$x$$$ is the resulting number.

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

Thank you.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • If $$$h \le a$$$, you have to decrease the height of all the "old" trees to $$$h$$$( use $$$a - h$$$ operations), and change the value of $$$a$$$ to $$$h$$$.
    • Otherwise you only have to decrease the height of the "new" trees $$$h - a$$$ times, and you don't have to change 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem c

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just solved it thoretically but didnt code it. You find the smallest element and the biggest element to the left and right of it right?

»
18 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

B — Palindromic Numbers — My Solution

»
16 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Alternate solution for problem F:

Note: I will be referring to a series of swaps leading to a "$$$1$$$" initially present at position $$$(x_1, y_1)$$$ to be finally present in $$$(x_2, y_2)$$$ as movement of that "$$$1$$$" from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Firstly, any series of swaps can be viewed as $$$1$$$'s moving from their initial to final position in the matrix. So for each $$$1$$$ located at $$$(x, y)$$$ in the initial matrix, let $$$(x_{final}, y_{final})$$$ be the position it will move to in the final array, when some optimal series of swaps is peformed.

Observation: In atleast one optimal series of swaps, the following holds: If there are two $$$1$$$'s, located at $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, and $$$y_1 < y_2$$$, then $$$y_{1_{final}} < y_{2_{final}}$$$. Simply put, there is no such column boundary that some $$$1$$$ crosses it from left to right, and another from right to left.

Proof

Let's think of an assignment strategy using this observation. Clearly, greedily assigning final position based on column number would work if there was only one row, but here there are two, so we have to somehow take that into account.

Firstly, we can ignore all $$$1$$$'s at whose position there is a $$$1$$$ in the finally wanted matrix.

Proof

Let's call cells which have a $$$1$$$ in the initial array as type-$$$1$$$ cells, and cells which have a $$$1$$$ in the final wanted array as type-$$$2$$$ cells. Now, we essentially have to pair each type-$$$1$$$ cell with a unique type-$$$2$$$ cell such that sum of distances between two cells in a pair of all pairs is minimised.

Assignment strategy Iterate over columns, and within a column iterate over rows, and do the following if the cell is of type $$$1$$$ or type $$$2$$$ (otherwise ignore it):

Let's say current cell is of type-$$$1$$$ (symmetric strategy for type-$$$2$$$)

  1. If there are any unassigned cells of type-$$$2$$$ which we have already visited before current cell, then pair current cell with any of them (give preference to unassigned cells of type-$$$2$$$ with same row if they exist). Mark current cell as assigned.
  2. If there are no such already visited cells, then mark current cell as unassigned.
Proof for optimality

Implementation: link

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please hep me that why my code for problem B is now working

238137702

»
5 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Others have shared solution to C, but I'd also like to give it a shot.
Observation 1: Okay so we have prefix/suffix reduce by 1 operations but the add operation is a global-add. Suppose we found some sequence of moves that use $$$k$$$ global-adds to achieve $$$a[i] = 0$$$ state.
It must be possible to atleast make all $$$a[i]'s$$$ equal to each other without using any global-add operations at all.

So, now the sub problem is to make all $$$a[i]'s$$$ equal using the reduce entire prefix/suffix by $$$1$$$ operations only. There are no global-adds.

Observation 2: Subtraction operations are *assosciative by nature. So, it should make life easier to consider we make all prefix-reduction operations together in first batch of operations and then do all suffix-reductions we may want in the second batch of operations. If any sequence of moves exists, then it can obviously be rearranged to match this format because of *assosciativity.

Observation 3: Assume we are done with the first batch of prefix-reduction operations. Now, we are going to do suffix reductions only. Then each $$$a'[i]$$$ currently should be $$$<=$$$ to $$$sufmin[i \ldots n]$$$.
Why ? Because we don't have any prefix-reductions to use. If somebody in my suffix is smaller than me, then there is no way we can become equal by only using suffix-reductions. (Our difference never reduces no matter what).

Conclusion: The first batch of prefix-reductions should be made in such a way that we don't encounter this $$$a[i] > sufmin[i \ldots n]$$$ problem.
This gives us the notion of mandatory prefix-reduce operations that need to be done at any $$$ith$$$ position.

So, we iterate from right to left.And We maintain $$$dec$$$ for how many prefix-delete operations we have done till now.
Current value of an element is then $$$a'[i] = a[i] - dec$$$.
If this current $$$a'[i] > sufmin[i \ldots n]$$$, we do $$$dec = dec + (a'[i] - sufmin)$$$ (i.e some prefix-reduce positions at the current $$$i'th$$$ position).
Update sufmin agains this $$$aa'[i]$$$ and continue.

Observation 4: At the end of above process for ensuring each $$$a'[i] <= sufmin[i \ldots n]$$$.
We automatically have a non-decreasing sorted array. Now, its trivial to make all elements equal to the first element of array by using only suffix-reduce operations.

We now have an array with all equal elements and are starting subproblem is solved.
Finally, if the first element is negative, we can use the global-add operations now. And, if positive, then we can use a full-prefix or full-suffix reduce operations.

(edit: im dumb and always confused between assosciative and commutative all the time.)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    *Subtraction operations are commutative. NOT at all

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      *assosciative so sorry. Corrected. And thanks for pointing out.