# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Name |
---|
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
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
Please helm me in this.
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.
Could you share both of those solutions?
Okay (hope they are actually correct):
O(2^n)
O(2^n n)