You are not logged in. Please login at www.codechef.com to post your questions!

×

How do I approach such problems?

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

radeonguy's gravatar image

1★radeonguy
1449
accept rate: 0%


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.

link

answered 20 Apr '16, 04:09

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

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!

link

answered 17 Apr '16, 18:51

agnishom's gravatar image

2★agnishom
233
accept rate: 0%

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).

link

answered 17 Apr '16, 18:27

pvkcse's gravatar image

2★pvkcse
223
accept rate: 0%

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

https://www.codechef.com/viewsolution/9930974

link

answered 17 Apr '16, 19:21

vinayb21's gravatar image

1★vinayb21
111
accept rate: 0%

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.

link

answered 20 Apr '16, 03:05

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×10
×9

question asked: 17 Apr '16, 09:39

question was seen: 727 times

last updated: 20 Apr '16, 04:09