Yesterday during starters I solved this question and I was pretty sure my logic of sorting by number of 1’s in each binary string and then counting inversions was correct. But I got WA and later when I changed every integer in my program to long long it worked. I tried it again in practise and it happened. Can someone please find which int is the one thats overflowing for me because going by the constraints none of them should.
Solution with integer: CodeChef: Practical coding for everyone
Solution with all integers changed to long long: CodeChef: Practical coding for everyone
Consider this kind of input.
1
100000 2
10 10 10 10 10 .... (1e5 times)
For this, the answer is just the concatenation of strings (in any manner). Note that, for this test case, the answer (number of inversions) is 100000 + 99999 + \dots + 2 + 1 = 5000050000 which will obviously not fit in an int.
1 Like
Oh so its just the variable in which the number of inversions is stored that has to be long long right?
Yes