Hello everybody. Today, i hope you can help me to solve this problem. I have many ways to solve it if the array has distinct integers. But if the array has repeated elements, i think it is very hard. Can anyone give me some advice ?

# | User | Rating |
---|---|---|

1 | Petr | 3353 |

2 | fateice | 3306 |

3 | Syloviaely | 3274 |

4 | tourist | 3235 |

5 | OO0OOO00O0OOO0O0…O | 3181 |

6 | Um_nik | 3158 |

7 | V--o_o--V | 3148 |

8 | dotorya | 3145 |

9 | LHiC | 3115 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 168 |

3 | Petr | 158 |

3 | csacademy | 158 |

5 | lewin | 150 |

5 | Swistakk | 150 |

7 | Errichto | 140 |

8 | ko_osaga | 139 |

8 | matthew99 | 139 |

10 | adamant | 138 |

Hello everybody. Today, i hope you can help me to solve this problem. I have many ways to solve it if the array has distinct integers. But if the array has repeated elements, i think it is very hard. Can anyone give me some advice ?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2018 19:03:36 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

Haven't put much thought on this, but my guess would be

n-k, wherenis the size of the array andkis the value of longest not decreasing subsequence.for test

2 3 4 ... n 1

you would return 1 instead of n — 1

Sure! Got it wrong. I think the problem it solves is when you are able to change the position of a element instead of swapping two. Any counter examples for this problem?

If you have several equal elements you will never make a swap between them, so you can replace each element with the tuple (

a_{i},i). Notice that now all elements are distinct (and solving this problem is equivalent to solve the previous) and you can do whatever algo you know to solve this.Would it work for the sequence 1 3 2 2?

Of course. You need to sort the array: [(1, 1);(3, 2);(2, 3);(2, 4)]

The sorted version will be: [(1, 1);(2, 3);(2, 4);(3, 2)]

Notice when comparing tuple we first compare first element, and in case they differ we compare the second element.

In this case you only need two swaps. Actually, after you replace each element by a tuple, you can replace each element by a different integer in the range [1, n], assigning each element its final position in the array, and now you need to solve the problem in a permutation. (Notice you need to sort the array first, to find it's final position).

In this case

`(1,1) -> 1 (2,3) -> 2 (2,4) -> 3 (3,2) -> 4`

so the array you need to sort is:

(1, 4, 2, 3)

But you may use one swap only: between the 3 and the last 2.

My bad, I was thinking in the problem:

`Performing swaps between adjacents elements`

Will this work if we allow to swap not only adjacent elements?

Friend of mine was asked the same question in Zalando interview round. Could not solve this too. Swapping any two elements is allowed. Anyone with a solution?

I think you or your friend lied. Because there is currently a problem like this in USACO bronze