11020  Efficient Solutions
Moderator: Board moderators
11020  Efficient Solutions
Hello,
I spend a lot of time on this problem but all I came up with was a set, using whichever of the bounds to keep the order. However this was a TLE. Can you tell me if I'm thinking in the right direction (O(N*logN)) or there is something fundamentaly simplier (O(N)).
I spend a lot of time on this problem but all I came up with was a set, using whichever of the bounds to keep the order. However this was a TLE. Can you tell me if I'm thinking in the right direction (O(N*logN)) or there is something fundamentaly simplier (O(N)).
It's necessary to notice that if you, at any time, sort the list of efficient grooms decreasingly by L, the list will also be sorted increasingly by C (because of its nature).
To get better percepcion, think of grooms as points in xy plane.
Now think what points are to be deleted from the list if we add new point, and how does the fact that list is sorted by both parameters help us to find those points.
To get better percepcion, think of grooms as points in xy plane.
Now think what points are to be deleted from the list if we add new point, and how does the fact that list is sorted by both parameters help us to find those points.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I think this problem is virtually undoable for non C++programmers that have no STL. The best thing I can think of is writing a redblack tree, but that takes hours to implement and debug (at least for me, I don't have one lying on the shelf). Or am I overlooking something?
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
I think there is an another approach of this problem.
Its complexity is surely O(NlgC), where C is the upper bound of input scores, or coordinatevalue : 10^9
Although balanced binary search tree (or, RB Tree) is virtually the most simple solution to this problem, I think, but there may be an another approach  one using a data structure named "Index Tree".
Yet I haven't implemented it and this is from my brief thoughts, so I cannot ensure its correctness, but I think it will do.
Its implementation is much easier than that of RBTree, therefore there may be another way for non C++ programmers.
Its complexity is surely O(NlgC), where C is the upper bound of input scores, or coordinatevalue : 10^9
Although balanced binary search tree (or, RB Tree) is virtually the most simple solution to this problem, I think, but there may be an another approach  one using a data structure named "Index Tree".
Yet I haven't implemented it and this is from my brief thoughts, so I cannot ensure its correctness, but I think it will do.
Its implementation is much easier than that of RBTree, therefore there may be another way for non C++ programmers.
Sorry For My Poor English..

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
I don't think this problem is unfair to nonc++ coders. It's not very hard to implement a redblack tree or an AVL tree. I have an implementation here: http://shygypsy.com/tools/bst.cpp. The code is not very long, and it does a lot more than this problem requires.
If only I had as much free time as I did in college...
I think this is a good problem. Binary search trees are an ubiquitous idea in computer science, and I don't think C++ programmers have such a great advantage here, since we cannot directly manipulate a balanced tree, but are limited to use the interface for a set (whose underlying implementation is a redblack tree). Besides, as far as I know, Java programmers also have TreeMap and TreeSet classes.
When I first read this problem, I thought it required writing my own balanced tree code, which I didn't feel like doing. Only later did I realise that I could use a dirty hack to make STL set work here (basically, keep a boolean to select which comparison function to use).
When I first read this problem, I thought it required writing my own balanced tree code, which I didn't feel like doing. Only later did I realise that I could use a dirty hack to make STL set work here (basically, keep a boolean to select which comparison function to use).
Need Help, always WA
Hi Everybody. I'm trying to solve this problem and I always get WA. This is my algorithm:
I have a set with Person, where each Person have L, C and a counter, that says how many persons are equal to him (this is to avoid using multisets). The set is ordered descendent by L and after that by C.
For every person, I try to insert it. If it cannot be inserted, it is because there is another person with the same Lineage and Charm, so I increment the counter and return.
If the person was inserted, I get the C value of the previous node and sweep the rest of the set, erasing every node until I found one with lower Charm. I suposse this works because every node after the inserted should have equal or higher Lineage, so the dominance is determined by the Charm.
I proved many test cases, but I cannot find one to broke my algorithm, and judge keep saying WA. Can you help me?
Thanks for your consideration.

Don't worry, I solved it. The following case can occur:
L: 10 20 20
C: 20 10 11
The new person is 20 10.
I move the iterator back to 10 20 and check, 10 20 dominates 20 10? No, so I stop and said there are 3 persons, but it's false, because 20 10 dominates the 20 11 person.
The solution I applied was to first check if the previous person dominates the new person. If that happens, eliminate and discount it. If not, start beggining in the new person and go forward eliminating until the first person with lower charm.
I hope this helps. If not, here are some test cases:
Input:
Output:
I have a set with Person, where each Person have L, C and a counter, that says how many persons are equal to him (this is to avoid using multisets). The set is ordered descendent by L and after that by C.
For every person, I try to insert it. If it cannot be inserted, it is because there is another person with the same Lineage and Charm, so I increment the counter and return.
If the person was inserted, I get the C value of the previous node and sweep the rest of the set, erasing every node until I found one with lower Charm. I suposse this works because every node after the inserted should have equal or higher Lineage, so the dominance is determined by the Charm.
I proved many test cases, but I cannot find one to broke my algorithm, and judge keep saying WA. Can you help me?
Thanks for your consideration.

Don't worry, I solved it. The following case can occur:
L: 10 20 20
C: 20 10 11
The new person is 20 10.
I move the iterator back to 10 20 and check, 10 20 dominates 20 10? No, so I stop and said there are 3 persons, but it's false, because 20 10 dominates the 20 11 person.
The solution I applied was to first check if the previous person dominates the new person. If that happens, eliminate and discount it. If not, start beggining in the new person and go forward eliminating until the first person with lower charm.
I hope this helps. If not, here are some test cases:
Input:
Code: Select all
7
1
100 200
2
100 200
101 202
2
100 200
200 100
5
11 20
20 10
20 10
100 20
1 1
11
1000 1
999 2
998 3
997 4
996 5
995 6
994 7
993 8
992 9
991 10
2 1
8
2 2
2 2
2 2
2 1
1 3
1 3
1 2
1 1
10
10 10
10 9
9 10
8 10
10 8
7 7
6 6
5 7
7 5
100 100
Code: Select all
Case #1:
1
Case #2:
1
1
Case #3:
1
2
Case #4:
1
2
3
3
1
Case #5:
1
2
3
4
5
6
7
8
9
10
1
Case #6:
1
2
3
1
2
3
2
1
Case #7:
1
1
2
2
2
1
1
2
3
3
10024  Guayoyo has Curled Up the Cube!