awoo's blog

Educational Codeforces Round 99 Editorial
By awoo, history, 4 years ago, translation, In English

1455A - Strange Functions

Idea: BledDest

Tutorial
Solution (Ne0n25)

1455B - Jumps

Idea: adedalic

Tutorial
Solution (adedalic)

1455C - Ping-pong

Idea: Neon

Tutorial
Solution (Ne0n25)

1455D - Sequence and Swaps

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (adedalic)

1455E - Four Points

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1455F - String and Operations

Idea: Neon

Tutorial
Solution (Ne0n25)

1455G - Forbidden Value

Idea: MrPaul_TUser и BledDest

Tutorial
Solution (pikmike)
  • Vote: I like it
  • +66
  • Vote: I do not like it

Comments Comments (52)
| Write comment?
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

When was the last time problem ratings were updated ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain those function proof in a simple way in C ques.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It looks too complicated. My thinking was slightly different. Since A has to start and make the first turn, she doesn't have options. B decides in this case if he wants to hit or miss. And since B wants to maximize his score, the maximum what he could get is if he misses everything from A and then with A having 0, he would able to get y points (it's impossible to get more) and A will have x points. But also as they want to minimize their enemy's scope as a second parameter, there is no need for B to miss everything, he could hit the last ball from A (A will have 0 energy already) so she will waste this point and B will get it. And in this case A will have (x — 1) and B will have y points. There is no better option for B because if he hits any ball except the last one A should respond not to loose her point. In this case B won't have maximum possible score.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +117 Vote: I do not like it

I have an interesting solution (100067011) to problem E, involving minimum cost circulation. It might not be the best solution, but it involves no casework or geometric insight, and it might be educational in helping you approach other problems.

First, I iterate over all permutations of the points, so let's assume $$$p_1$$$ will end up as the bottom left point of the square, $$$p_2$$$ the bottom right, $$$p_3$$$ the top left, $$$p_4$$$ the top right.

For each point, let's create two variables $$$dx_i$$$ and $$$dy_i$$$, so that point $$$i$$$ should end up at position $$$(x_i+dx_i, y_i+dy_i)$$$. Then the objective is to minimize $$$\sum_i |dx_i|+|dy_i|$$$.

Now, we need to set up the constraints so that the points will make a square. To make sure it's a rectangle, we need

$$$x_1+dx_1=x_3+dx_3\tag{A}$$$
$$$x_2+dx_2=x_4+dx_4\tag{B}$$$
$$$y_1+dy_1=y_2+dy_2\tag{C}$$$
$$$y_3+dy_3=y_4+dy_4\tag{D}$$$

To make sure it's a square, we need the side lengths to be equal. That is,

$$$(x_2+dx_2)-(x_1+dx_1)=(y_3+dy_3)-(y_1+dy_1)\tag{E}$$$

At this point, I noticed that each variable appears in at most 2 constraints, which reminds me of the constraints of a flow problem. I also notice that we can add a new (redundant) constraint to make each variable appear in exactly two constraints:

$$$(x_4+dx_4)-(x_3+dx_3)=(y_4+dy_4)-(y_2+dy_2)\tag{F}$$$

The equations can be interpreted as

$$$\mathrm{flow\_in}_u=\mathrm{flow\_out}_u+\mathrm{demand}_u, \quad u\in \{A,B,C,D,E,F\}$$$

$where our variables $$$dx_i$$$ and $$$dy_i$$$ are undirected edges. And the cost of this flow is exactly what we seek to minimize.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +54 Vote: I do not like it

    I really want to understand this solution to the full extent. I understood up to (F) but am not sure 1) why two constraints should remind someone of a flow problem, 2) how to go from the equations to the flow graph, and 3) (the hardest/crucial part) why this graph solves the problem correctly. I am not the strongest in flow problems so understanding this unique solution in detail may prove very beneficial to me and hopefully others!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +80 Vote: I do not like it

      1) why two constraints should remind someone of a flow problem

      The constraints of a flow problem are that for each node, the incoming flow equals the outgoing flow. So each edge $$$(u, v)$$$ is involved in $$$u$$$'s constraint as the outgoing flow, and in $$$v$$$'s constraint as the incoming flow. So if each variable appears in at most two constraints, it's a strong indicator of a flow problem.

      2) how to go from the equations to the flow graph

      The nodes represent the constraints, so $$$A,\ldots, F$$$ are the nodes. To force it into the $$$\mathrm{flow\_in}_u=\mathrm{flow\_out}_u+\mathrm{demand}_u$$$ framing, we need the following:

      1. $$$\mathrm{flow\_in}_u$$$ and $$$\mathrm{flow\_out}_u$$$ should be sums of variables $$$dx_i$$$, $$$dy_i$$$.
      2. $$$\mathrm{demand}_u$$$ should be an exact value from the input of the problem, involving $$$x_i$$$, $$$y_i$$$.
      3. Each variable $$$dx_i$$$ and $$$dy_i$$$ should appear once as $$$\mathrm{flow\_in}$$$ and once as $$$\mathrm{flow\_out}$$$.

      So I will rewrite the equations like this.

      $$$(dx_1) = (dx_3) + (x_3 - x_1)\tag{A}$$$
      $$$(dx_4) = (dx_2) + (x_2 - x_4)\tag{B}$$$
      $$$(dy_2) = (dy_1) + (y_1 - y_2)\tag{C}$$$
      $$$(dy_3) = (dy_4) + (y_4 - y_3)\tag{D}$$$
      $$$(dx_2+dy_1) = (dx_1+dy_3) + (x_1+y_3-x_2-y_1)\tag{E}$$$
      $$$(dx_3+dy_4) = (dx_4+dy_2) + (x_4 + y_2 - x_3 - y_4)\tag{F}$$$

      From here, the graph and demand values follow. An edge connects the two letters that involve it in the constraints. Now, $$$dx_i$$$ and $$$dy_i$$$ can be positive or negative, so they are actually undirected edges in the flow graph, but we still needed to set the equations up as incoming/outgoing flows. This ensures the sign of the demands are correct, and that the constraints really do correspond exactly to a flow graph.

      flow.jpg

      3) (the hardest/crucial part) why this graph solves the problem correctly

      1. The constraints we set up are satisfied if and only if the points end up in an axis-aligned square.
      2. Our objective is exactly the cost of moving the points, and exactly the cost of a circulation in our flow.
      3. We know there is an optimal circulation where all values are integers.
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Thanks for such a detailed explanation! After doing some research does this problem relate to linear programming at all? Because the way I understand flow problems (max flow min cut) is that you have a source and sink node with predetermined constant capacities on each edge. Maybe I am misunderstanding the graph that you created but I do not see any source/sink or how one could use flows to support unknown capacity on each edge? Or how a node represents an equation?

        If you/anyone has resources for problems very similar to this with solutions (I could not find any but maybe I am searching the wrong thing) that would also be helpful. Thanks!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          It relates to linear programming in that I approached the problem by setting it up as LP, then noticed it's a special case and can be solved with flow.

          You're right that I didn't mention a source or sink. That's because it's a circulation graph. You should read about circulation and how it reduces easily to min cost max flow, with an added source and sink.

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

            I can understand your solution. However, I use Dinic instead of MCMF and still get correct answer(see my 167564314), which means that I even not take care of cost! I don't know why it is correct, it is amazing!

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

              Dinic's algorithm works by always selecting the augmenting path with the fewest edges. It turns out that a path of min number of edges happens to be equivalent to min sum of weights for this particular example, so Dinic's will work here.

              (You can see that all edges are weight $$$1$$$ except the edges from source and to sink, but we have to take exactly $$$2$$$ of those anyway. That's why min edges = min cost here.)

              → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

I thought that $$$O(tn^2)$$$ would not pass for problem F so I have a $$$O(tnk)$$$ solution. It is basically the editorial solution except we only keep the last 3 characters of our string, ensuring that all characters before that is of the optimal solution.

code (very ugly): 100144988

I think this can possibly be improved to $$$O(tn)$$$.

Edit: 100146367. Yea there is a $$$O(tn)$$$ solution.

→ Reply
»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

On Problem E

The first approach is to note that

  • either both x1 and x2 coincide with some (pi.x)-s and y1 coincide with one of (pi.y)
  • or both y1 and y2 coincide with some (pi.y)-s and x1 coincide with one (pi.x).

WHY??????

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +38 Vote: I do not like it

    The way I came to that conclusion is the following. First, we have to fix something. Let's start by proving there is some $$$x$$$ in the input such that it's one of the optimal lines. For the simplicity, let's fix the permutation of points beforehand and prove for it.

    Let the square side be some length $$$a$$$. So we have found some optimal square such that neither of the original $$$x$$$ are in there. If it is entirely to the left or to the right of all points then you surely can move it closer and the cost decreases. Otherwise, what's the cost of moving the square one to the left or one to the right? It's basically some linear function on (number of points to the left of each $$$x$$$) and (number of points to the right of each $$$x$$$). Also, that cost is constant until we reach any of the original points while we move it. Moreover, moving to the left costs exactly the same as moving to the right but negated. So if the cost is non-zero, then we can at least move the square to the side where the function is negative and obtain a smaller cost. If it's zero then you can still move to any side and the cost won't change. So move until you hit some $$$x$$$. Thus, there always exists a square of side length $$$a$$$ such that it costs less than or equal than our assumed answer.

    Same proof goes for some $$$y$$$. You can notice that this proof relies only on one coordinate, so you can move any square of any side length independently on each coordinate. Thus, we've proven that there is some $$$x$$$ and some $$$y$$$ in the original input that is optimal for any side $$$a$$$.

    Now, let's fix some $$$x$$$, some $$$y$$$ and some permutation of points. Let $$$(x, y)$$$ be the lower left corner of the square. Cut the grid by all $$$x$$$-s of the input and all $$$y$$$-s of the input. Let the upper right corner of the square be between some $$$x_1$$$ and $$$x_2$$$ and between some $$$y_1$$$ and $$$y_2$$$. Notice that the cost to move the upper right corner by one by both $$$x$$$ and $$$y$$$ simultaneously is constant inside the entire rectangle between $$$x_1$$$ and $$$x_2$$$ and between $$$y_1$$$ and $$$y_2$$$ (basically, the same as in the first proof). Shrinking the square costs a negated price of expanding it. Thus, we can keep shrinking or expanding (choose the one that's non-positive) until we hit a border of the rectangle $$$x_1$$$/$$$x_2$$$, $$$y_1$$$/$$$y_2$$$. So we hit it and the cost has been decreasing (or staying the same) all the way to some $$$x$$$ or $$$y$$$ on the border of the rectangle. Thus, we came up to the conclusion that there's also some $$$x$$$ or $$$y$$$ besides the original $$$x$$$ and $$$y$$$ we fixed that is optimal. Apply the same proof to $$$(x, y)$$$ being any corner of the square and you got yourself a full proof.

    hujc, Whistleroosh, here you go.

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

      I understand this explanation!!

      Thank you very mach!!!

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

      Thank you for explanation

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

      wow, that's a really nice proof.

      I really like how this proof is similar to the proof of the fact that the cost of moving all points (in one dimension) to a common point is minimum when the common point is the median of all the points. But this is of course in two dimensions. Cool!

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

      thank you so much, nice explanation!!

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

My solution for Problem D is simpler, check it out: 100115447

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

    can you explain it a bit here? I am not able to understand the editorial completely.

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

      My solution for problem D is next: First because you only have n numbers and 1 x variable if you add them all to one array and sort it you will have n+1-element sorted array. And you know that if a solution exists for the problem when you do it you will get a n-element sorted array(if you have 1 2 3 5 4 and x = 0 you know that when you do the least possible switches you will get one of the following: 0 1 2 3 4, 0 1 2 3 5, 0 1 2 4 5, 0 1 3 4 5, 0 2 3 4 5, 1 2 3 4 5, and you can see that our n+1-element sorted array is 0 1 2 3 4 5 so those possible answers are nothing more than this array without one of its elements).So we can try to match the starting array 1 2 3 5 4 to any of those arrays created from our n+1-element array and save the minimum switches you needed to make for each try.So how to calculate the number of switches for each try? just look at each one of the elements from left to right and if they dont match then you need to switch your current x with that element(if you dont you wont be able to do it later because all the other numbers are bigger or equal to that one) so if x < current number that needs to be switched with x we switch them and we do that until we end with iteration(that means we equalised the arrays so we found number of switches for that array) or until we need to switch the number that is greater than x(that means, in this iteration, we cant sort it in which case the answer is -1).Here is a solution if you dont get what im saying 100264317

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

    Isn't your solution O(n^2)?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The proof of C is really interesting but I just can't accept the fact that the solution is one line.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I thought of it this way. Since Bob can atmost hit y shots, the maximum score he can have is y. Then I formulated the strategy for how Bob can always achieve that maximum score. I too was really surprised on finding a O(1) solution.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Nice way to look at it. I saw that Bob can always score y but at first I thought that Alice can also always get x until I saw the samples.

      Oh, and I it was crucial that they don't want to win but to maximize their score and after that minimize the opponent's score.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question...!

in problem E. Four Points,

it is noted that a square with side 0 is allowed

so for the 2nd test case in the example, why not making four points as (2,0), (2,0), (4,0), (4,0), which makes the output 3 ?

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

    This is a line segment with length 2, not a square.

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

      I thought a square with side 0 means the side with the length 0, so then what's the difference between a square with side 0 and a line ?

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

        The length of the line from a square must be the same. So we can assume that a square with side 0 has four line whose length is 0, which actually is just a single point.

        However, we can assume that a segment with length 2 not only has side 2, but also has side 0.So it isn't a square.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        According to Wiki (and all dictionaries I saw), a square "has four equal sides". If a square has a side equal to 0 then all his sides are equal to 0, i. e. it's a point — not a segment.

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In fact, (2,0),(2,0),(4,0),(4,0) cannot form a square with side 0.

    Four points which can form a square with side 0 must be the same with each other completely.

    For example, (2,0),(2,0),(2,0),(2,0) can form a square with side 0.

    Hopefully, my answer will help you.(Sorry for my poor English.)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone elaborate the DP solution for problem D??

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

    Because of the observations mentioned in the editorial, we can go in increasing order of indices, and keep taking decisions on whether to make the switch or not.

    Let $$$dp(i, prev, cx)$$$ represent answer for $$$a[1...i]$$$ sorted prefix where number put on the $$$i^{th}$$$ index was $$$prev$$$ and now we are deciding what to do on the next index with value of $$$x$$$ equals $$$cx$$$.

    1. Now we can either let the value of $$$a[i+1]$$$ stay the same (possible only when $$$prev <= a[i+1]$$$ ): $$$dp(i+1, a[i+1], cx) := min(self, dp(i, prev, cx))$$$

    2. Or we can actually swap $$$a[i+1]$$$ with $$$cx$$$ (when $$$prev <= cx$$$ and $$$cx < a[i+1]$$$ ) with the following transition: $$$dp(i+1, cx, a[i+1]) := min(self, dp(i, prev, self) + 1)$$$

    To optimise space complexity, dont store dp table for all the indices. Store them only for the current and the immediate-next index.

    My Code: 100219452

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    100731689 Here is a simpler version of code. Thanks iprakhar22, for idea.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E what is the proof for the statement that:
- either both x1 and x2 coincide with some (pi.x)-s and y1 coincide with one of (pi.y)
- or both y1 and y2 coincide with some (pi.y)-s and x1 coincide with one (pi.x)?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D with $$$O(n^2)$$$ DP?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why am i wrong ? :'< https://codeforces.net/contest/1455/submission/100029658

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

    Yeah i had same problem, consider the following portion of test 4 for which you have done computation for previous input and while iterating through 42 42 43 46 44 45 46 48 48 48 62 51 51 you will have x=46 while iterating you are counting 48 three times while you require only one swap so that accounts for 2 extra moves in your answer.You can refer to my code on same logic in O(n) https://codeforces.net/contest/1455/submission/100248902

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

      Omg thank you so much, i get it! >.<, I hope u can reach high rate in next contest, people like you deserve it ^^

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For 1455E - Four Points I want to describe other solutions. In my opinion they are easier to understand.

Yet another wall of text
→ Reply
»
4 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Hello everyone, I meet a very very strange problem when i am trying to solve 'Problem G'. ⁣At first, I commited this code 100780041, and the result was 'Wrong answer on test 11'. The reason to lead the WA is I used the erase(x) method of multiset to delete one item, but obviously I deleted all the items valued x. ⁣So I replaced this wrong applying with multiset.erase(multiset.find(x)) which only will delete one item valued x. But I got the TLE!!! on test 5!!! 100780082 ⁣In theory, these two ways have the same time complexity. So I am so confused that having to ask someone else to help me have a look. ⁣Thanks. The differents of two code:

28c28
< 			s.erase(m[k]);
---
> 			s.erase(s.find(m[k]));
39c39
< 		s.erase(m[k]);
---
> 		s.erase(s.find(m[k]));
69c69
< 		costset[x].s.erase(xv - xoff);
---
> 		costset[x].s.erase(costset[x].s.find(xv - xoff));
136a137
> // s.erase(s.find(x));
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And because the contest is finished for a little long time, I probably knows maybe little people focus on this. So, may I please ask you for help? awoo

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

    OK，I got it! In line 113 costset[rt[End[i]]].remove(y[i]);, I will erase a item valued x that can not exist. So when I use multiset.erase(multiset.find(x)), the inner return of find method will return multiset.end() that can cause the TLE when I erase it.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B can be solved in $$$O(t)$$$ time. (100963724)

(Editorial solution is $$$O(\sqrt{x}\cdot t)$$$ I believe)

For each test case, we can calculate the lower bound of $$$n$$$ as

n = int( 1 + floor(sqrt(1+8*x) ) // 2 - 1

You arrive to this by solving for $$$n$$$ in Baby Gauss' formula.

$$$x=\frac{n(n+1)}{2}$$$
$$$n=\sqrt{2x+\frac{1}{4}}-\frac{1}{2}$$$

The code is a little different, in that I multiply and divide the square root by 4 in order to deal with integers and not worry about floating point errors. And of course we take the floor to get the lower bound.

This implies that our input $x$ is between $$$x_1$$$ and $$$x_2$$$.

x1 = (n * (n+1)) // 2
x2 = ((n+1) * (n+2)) // 2

Finally, by the same logic as explained in the editorial.

if(x == x1):
    print(n)
elif(x2 == x+1):
    print(n+2)
else:
    print(n)

If our $$$x$$$ is the lower bound, we output the $$$n$$$ of the lower bound.

In all the other cases, we can account for the difference between the lower bound and our input by taking one more number and changing another one for $$$-1$$$.

The only exception being when the difference is $$$1$$$, in which case we have to take 2 more numbers, subtract one of them and add the other.

I hope it's clear enough. It's my first time commenting. The only difference is that we remove the inner while loop.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everybody, this is my first question here so wish me luck xD

I submitted code for D problem here https://codeforces.net/contest/1455/submission/100985682 and the result was "Wrong answer on test 3". When i test with the same test case i get 3 as output, but when i submit it gives the 74 as output! Can anyone explain me how did it come about throwing out 74 or any other number greater than 3 instead of 3?

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

    I also wrote the same wrong code as yours.

    In fact, in this method you need to check everytime if the suffix array is already sorted. It is only when the array is still not sorted that you need to do the swapping. (checking everytime can be done in O(1) or O(n), both will pass)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand asymptotics of my D solution. It has passed and it is none of authors solutions. https://codeforces.net/contest/1455/submission/102979769

If someone can hack it or prove some good asymptotics, you're welcome.

→ Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

When I saw this blog in Recent Actions, I initially thought "Who the hell is this awoo guy and why does he copy-paste our editorial blogs?"

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

for the problem D,

if all elements before it are smaller and elements after it are greater then the element is in sorted position.

if an array is unsorted then x has to be there in the array. this observation will be used.

cnt =0.

for i from 1 to n,

check every element a[i] for the following criteria:

1) if array is now sorted then return cnt.

2) if a[i] and x are candidate for position i then we have conditions:

  • A) if swap can be done, swap them make add 1 to cnt and move to next element.

(swap is done because subarray after i is not sorted and if greater element is assigned this position( which is arr[i] ) then x will be there in the subarray after i(the fact stated above) which will make array unsorted as a whole.)

  • B) if swap cant be done then just move to next element. if a[i] is candidate for the position but x is not the candidate for the position: then just move to the next element.

3) if a[i] is candidate for the position but x is not the candidate for the position: then just move to the next element.

4) if a[i] is not the candidate for the position but x is the candidate for the position: we have only one choice to swap them and add 1 to cnt and move to next element. if any other situation is encountered then say it is impossible.

print cnt

(BEING A CANDIDATE FOR A POSITION means all elements before it are smaller and all elements after it are greater.)

→ Reply