rahul_1234's blog

Minimum number of swaps
By rahul_1234, history, 7 years ago, In English

I am sharing image of question as link is not working:

Img1

Img2

Please someone help me in his question.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

The basic idea is: For every i, it makes sense either not to swap A[i] and B[i] at all, or to swap them exactly once. So every choice of (non)-swaps for the whole pair of strings can be represented as some n-bit binary number (i-th digit is 1 IFF you want to swap A[i] and B[i]). Since n < 16, it is feasible to try out all 2n possible numbers (i. e. all possible choices of (non)-swaps) and calculate max(n(A'), n(B')) naively (for example, by using two sets of characters, one for A', one for B'). Time complexity of this solution is (possibly n + |Σ| for bigger alphabets).

Hope I've been comprehensible enough.

I also suspect one can solve the task in , but that's slower for our constraints anyway

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Actually if we see:

    (2^16)*16*100 = 104857600 + some few operators ( which is greater than 10^8 computations for 1 s ( time complexity ), won't it time out.

    100 is for test cases

    Am I missing something because for 2s your solution would surely pass but would it pass for 1s?Shouldn't computations be strictly <= 10^8 for 1 s.

    Please helm me in this.

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

      Oh, I forgot about the test cases...

      Well, I'm not too sure about whether my solution would pass the 1s limit, but I think it could, since the actual running time depends a lot on what operations you perform. In this particular case, you just increment some numbers, do bitshifts and keep a 26-sized array (for counting distinct letters) which you can BTW replace with another bitmask (I'm not sure if it is actually faster or not). Since the memory complexity is nearly constant, I would say you are also kind to caches, which could help, too.

      I think you could achive complexity by iterating over the bitmasks in a clever way (so there would be only one bit changed between two iterations), but personally, I would probably code the more naive solution and try to "prove by submit" first :-).

      EDIT: I tried to implement the (more precisely, ) solution, it passed CF's custom invocation with t = 100, n = 16 in about 400 ms.

      EDIT 2: The solution isn't as complicated as I expected. On the same test it runs for about 30 ms.

      → Reply