Obviously, do not discuss problems until after the contest is over. Good luck to everyone competing today, especially to my fellow UVA teams! :D

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

1 | tourist | 3682 |

2 | ecnerwala | 3603 |

3 | Benq | 3549 |

4 | Radewoosh | 3494 |

5 | Petr | 3452 |

6 | ksun48 | 3413 |

7 | maroonrk | 3406 |

8 | Miracle03 | 3314 |

9 | scott_wu | 3313 |

10 | Um_nik | 3299 |

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

1 | 1-gon | 214 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 179 |

7 | Ashishgup | 177 |

8 | maroonrk | 173 |

9 | vovuh | 172 |

9 | antontrygubO_o | 172 |

Obviously, do not discuss problems until after the contest is over. Good luck to everyone competing today, especially to my fellow UVA teams! :D

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2021 10:10:49 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by hu_tao (previous revision, new revision, compare).What was the solution for the bitonic ordering? Min swaps to make first i elements increasing, and min swaps to make the latter elements decreasing wasn't working apparently.

That doesn't work for the case

`4 5 6 7 9 1 10`

since you can just switch the 10 and the 1.The solution is for every number starting from the number with the lowest value, swap it all the way to the left or to the right. You will only swap with the numbers that are greater than it, so you will need store how many numbers are greater than it to the left and how many are greater to the right, which you can do with fenwick tree.

But making the first 5 elements increasing takes 0 swaps, and last 2 elements decreasing takes 1 swap, so my logic also gives 1 as the answer.

A better example is

`2 3 4 1 5 6`

: it's optimal to move the 1 to the very right, but there's no reason to flip the 5/6 to decreasing.Does anyone know what's wrong with the following solution for bitonic ordering? Spent quite a bit trying to debug/identify the flaw b/c I kept getting the wrong answer. I also could not create a test-case that broke my code:

First, I compressed all values to be in the range [0,n-1], where n is the # of elements.

Now, suppose that index i contains the element with value n-1 (aka maximum in array). From here, it suffices to compute the minimum # of swaps needed to make the left part of the array (a[0] --> a[i-1]) monotonically increasing and the right part of the array (a[i+1] --> a[n-1]) monotonically decreasing.

Now, we traverse from left to right and compute the cost of creating the array such that the max is positioned each possible index i, using two Fenwick Trees to accomplish the task. The answer is the minimum of all such costs.

The complexity is O(NlogN).

we started with a similar idea, but came up with this case:

the answer for this case is 2, by swapping the 5 to the right twice. sorting a prefix and a suffix will cause you to move the 5 over but also swap 50 and 60, giving an answer of 3.

Jeez, if only I had come up with such a test case :( thanks a lot!