Pls help me with this problem

general
, , ,
1

I am able to get only 30 pts. I used sets to store the values. Isn’t using sets the best way???

Inserting an element takes logarithmic time and so does finding an element.

how can I optimise??

Contest Page | CodeChef question

here’s my algorithm

take input and insert it into the set

find the element in the set and return its position.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> myset;
	int arr[45001];
	set<int>::iterator it;
	int n,p;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> p;
		myset.insert(p);
		it = myset.find(p);
		arr[i] = i-distance(myset.begin(),it);
	}
	for(int i=1;i<=n;i++)
		cout << arr[i] << endl;
}
2

Actually you can’t use sets because I don’t know why it is giving TLE(please show your code) but it should give WA because elements can repeat here. The optimal answer to this problem is actually fenwick trees. That is pretty advanced although here an O(n^2) solution works as well. It is just a variation of insertion sort with reduced constant factors.

3

Your solution would be an \mathcal{O}(n\;log\;n) solution, which is very fast, if distance(myset.begin(),it) was \mathcal{O}(log\;n) just like insert() and find() are. However as it turns out, it takes \mathcal{O}(n) for the distance function. Refer here, here and here.

So, the complexity of your solution remains \mathcal{O}(n^2), with additional overheads for set functions. A simpler and more raw way is to use insertion sort to maintain a sorted array at all times. Whenever a merchant enters, linearly find his correct position in the array of merchants who have arrived earlier, and insert him there after shifting some merchants to their new positions (that’s how insertion sort works, see here if you’re not clear about it yet).

So the final solution is to maintain a array sorted in descending order (preferably, you can use ascending too), and repeatedly inserting each merchant into the array when they arrive, and printing their position at the same time. This is also \mathcal{O}(n^2), but with very little overhead, and manages to run within the time limit of 3 secs.

Here’s my accepted solution as described.
Hope this helps :slight_smile:

UPDATE
Here’s an \mathcal{O}(n\;log\;n) solution using AVL Tree. By using a balanced binary search tree (like AVL Tree) we can achieve \mathcal{O}(log\;n) time insertion, just as in your solution using sets. The difference here is that every node stores the size of the subtree rooted at that node as additional data. By modifying the standard BST search function and using this information, we can also determine in \mathcal{O}(log\;n) exactly how many values in the set are greater than a given value. Pay attention to the greaterThan function, apart from that it is a standard AVL Tree. The logic is as follows.

In a BST, the key in each node must be greater than all keys stored in the left subtree, and smaller than all keys in the right subtree. So, while searching for a particular key, we encounter three cases
  Case 1: the key is smaller than the key of the current node
            Then the current node's key and all the keys in the right subtree of the
            current node MUST be greater than the key. Add these to total.
          search in left subtree
  Case 2: the key is equal to the key of the current node
            Then all the keys in the right subtree of the current node MUST greater
            than the key. Add these to total.
          stop search
  Case 3: the key is greater than the key of the current node
          search in right subtree

Hope this will be of help :slight_smile:

1 Like
4

The distance statement makes the algo n^2 log n. And hence doesn’t pass. N^2 shouldn’t pass but possibly test cases are weaker. The problem can be interpreted in a nice way if you know inversion sequences( Which could be found in nlogn)
I won’t spoil the joy of working with the exact solution. But since you are solving iarcs questions do check out this problem again after working with the following iarcs questio where you will require nlogn soln.
Contest Page | CodeChef

5

It says in the problem that the inputs are unique

You may assume N ≤ 45000 and that no two merchants have the same wealth. Further you may also assume that in 30% of of the inputs N ≤ 8000.

6

You sure ? N can be as large as 45000 N^2 might not be optimal in my opinion.

7

Thanks a lot!!! I didn’t think distance would take O(n) time.

8

It’s not optimal but it works. Worked for me.

9

No problem! And yes, apparently the type of iterator passed to distance matters. Distance works in constant time only for random-access iterators whereas the set iterators are bidirectional iterators.

10

I believe that an nlogn solution should exist otherwise there is no point in specifying the limit of 45000. Insertion sort passses does imply that the data is a bit sorted. Try sorting the other way(change dsc to asc or vice versa in your algo) and i believe it shouldn’t pass.