chrome's blog

TopCoder SRM 627
By chrome, 10 years ago, translation, In English

Hello, everyone!

Tomorrow will take place TopCoder SRM 627. Don't miss!

GL & HF

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

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

Can someone give me any ideas about Div2 1000?

Thanks

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

    At first what makes you think that this problem can be solved by DP? Because one can reverse the array with disjoint interval. Ok then what information do i need to solve the problem with DP ?

    At first you need to know, that number of bubble sort swaps for an array is equal to the number of inversions in that array. Search on google if you don't know what is inversion of an array !

    So with dp we need to minimize the inversions.

    So the state will be (index, K) and in the dp body, you will select a range (subarray from the current index) , then for that range count the inversions of normal array and count the inversions after reversing the range. then make a transition to get the minimum.

    BTW you can check my code for better understanding: http://pastie.org/9375371

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

I didn't participate, but can you give more information on UPD2? What happened with problem B and Python?

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

    the return type, char, is not supported by Python. this makes it impossible to solve the problem.

    → Reply