×

# How do I approach such problems?

 0 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? asked 17 Apr '16, 09:39 144●9 accept rate: 0%

 2 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. answered 20 Apr '16, 04:09 7★ceilks 1.8k●9 accept rate: 36%
 2 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! answered 17 Apr '16, 18:51 2★agnishom 23●3 accept rate: 0%
 1 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). answered 17 Apr '16, 18:27 2★pvkcse 22●3 accept rate: 0%
 1 I faced the same issue of TLE. Link to my solution is https://www.codechef.com/viewsolution/9930974 answered 17 Apr '16, 19:21 1★vinayb21 11●1 accept rate: 0%
 1 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. answered 20 Apr '16, 03:05 4★bhishma 297●7 accept rate: 11%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

question asked: 17 Apr '16, 09:39

question was seen: 727 times

last updated: 20 Apr '16, 04:09