duckladydinh's blog

0-1 Sequences
By duckladydinh, history, 8 years ago, In English

Hello,

I am working on this problem on Kattis. I have been constantly thinking about it for the last 3 hours, but it seems that I am totally hopeless on this problem. Can someone give me some hints?

(I know 3 hours is too short :(. Normally I would only give up if it lasted for a few days, but I am in my urgent self-training period before an NWERC, so I change my plan to solve problems that I am totally hopeless instead of those that are hard but still somehow solvable and I use all this time just to make sure that it is really impossible for me)

Thank you. Happy Coding

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The answer is sum of the three sub-problems:

  1. No of inversions among known characters
  2. No of inversions among ?
  3. For each ?, no of inversions created against known characters

To give you an example: 01?01?

  1. 0101: 1 inversion x 2^k -> 4
  2. ?? -> 00, 01, 10, 11 -> 1
  3. Number of inversions created by the first ? (consider both 0 and 1 cases) + Number of inversions created by the second ?.
→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thank you I have completed it and also understood it completely :)) You are a big help

    → Reply