MagentaCobra's blog

Unofficial Mid Atlantic ICPC Regionals Discussion
By MagentaCobra, 4 years ago, In English

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

  • Vote: I like it
  • +90
  • Vote: I do not like it

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

Auto comment: topic has been updated by MagentaCobra (previous revision, new revision, compare).

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

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.

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

    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.

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

      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.

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

        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.

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

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

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

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

      11

      10 20 30 40 5 50 60 4 3 2 1

      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.

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

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

        → Reply