https://www.codechef.com/problems/WATSY

Provide the approach for the following problem and please avoid posting direct solution but the strategy to solve such problems?

Also Is it simple problem or need knowledge some other concept like dp?

https://www.codechef.com/problems/WATSY

Provide the approach for the following problem and please avoid posting direct solution but the strategy to solve such problems?

Also Is it simple problem or need knowledge some other concept like dp?

Yes, You need to know some special data structures like Fenwick Trees , Segmentation Trees. This is because of the upper bound and the strict time limit. O([n^2]) algo with n as 10^6 at worst case is not possible with 1s time limit. So, sure you need a nearest log factor algorithm. Hence, these data structures will make both query and update at O(log n).

1 Like

Could you please explain the solution using a segment tree or a fenwick tree?

I believe it can also be done with balanced BSTs, but I am not sure how to implement this solution.

Thanks!

2 Likes

I faced the same issue of TLE. Link to my solution is

1 Like

I solved it using AVL tree in Java check my solution : solution But the easiest way to do it is to use a Binary Indexed Tree.

1 Like

First of all. This problem is a rather bad example for a well posed problem. The constraints are ridiculous. Typically you want only solutions to pass which run in time for *all* inputs satisfying the given constraints. But no solution will pass 1000 testcases with N=10^6 . Even O(N) wouldn’t be enough and the typical runtime for this algorithm is O(nlog(n)).

Concerning your question. If you don’t have the tools to tackle this question you will have a very hard time. There are possible solutions which use self-build datastructures or std::set in C++, but in fact the whole problem is a pretty standard algorithm. Google “inversion counting” and you will see some solutions (using FenwickTree/BIT or MergeSort).

There is absolutely noting wrong with learning these algorithms instead of trying to reinvent the wheel all by yourself. After you’ve assembled your basic toolbox of data structures and algorithms, you can go for problems which are in fact unique and require variations of well-known algorithms.

2 Likes