RedBlackTrees's blog

Why is my approach to Parity Shuffle Sorting wrong?
By RedBlackTrees, history, 19 months ago, In English

Hi! I was upsolving a question CodeForces Round Div2 #821 C. https://codeforces.com/problemset/problem/1733/C.

My approach is pretty simple. Just make all the elements of the array equal. To accomplish this...

1) The consecutive index sum is always odd as (even + odd = odd). So, just print out n-1 operations as we don't have to find the minimum and run the loop from the last index till the first index and make all the elements of the array equal to the last element.

So, for example for an array [4, 3, 2, 1], the answer from my approach should be:

3

(3, 4) (2, 3) (1, 2)

which will give you an array [1,1,1,1] which is non decreasing.

This is my submission https://codeforces.com/contest/1733/submission/173866286

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
19 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

$$$[3,1,3,2]$$$ is a counterexample to your approach.

UPD: actually my counterexample is invalid, but actually the second example case poses a counterexample to your approach. See $$$[1,1000000000,3,0,5]$$$.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    With my approach the final array would be [2, 2, 2, 2].

    The operations done to reach this array are...

    3

    3 4

    2 3

    1 2

    → Reply