11020 - Efficient Solutions

[andresw1]

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

[kalinov]

My accepted solution is N lg N and I use STL set also, so that should work. Make sure that your implemented solution really is N lg N.

[andresw1]

Thanks kalinov,

However, if someone doesn't know STL what should he/she do?
I'm just curious if there is some other O(N lg N) approach.

[aminallam]

I wonder how to make nlogn algorithm for this problem!
Can you explain more? (I know set<> in STL, but I can not get approach to make it nlogn).

[kalinov]

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 x-y 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.

[little joey]

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 red-black 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?

[wook]

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 coordinate-value : 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 RB-Tree, therefore there may be another way for non C++ programmers.

[Abednego]

I don't think this problem is unfair to non-c++ coders. It's not very hard to implement a red-black 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.

[david]

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

[Darko]

Besides, as far as I know, Java programmers also have TreeMap and TreeSet classes.

Well, Java does have those things, but not UVa Java - you can use only Vector and Hashtable with 10-yr old implemetations. Meaning - you are better off writing your own.

Darko

[andresw1]

Hello,

Wook,
Can you explain a bit more about your idea. Where can I find some information for the trees you mentioned?

[mysword]

can anyone give some I/O samples?
keep wa and wa....I can't find what's wrong of my program....

[Gaizka]

Well What I did was this:

After each groom is inserted I looked into the Set and erase all the grooms betwen the groom inserted by lineage and the same groom inserted by charm.

Can you give me cases? I always get WA.

Thanks

[Gaizka]

Nevermind, I solved it. It gave me a lot of trouble but finally I did it!!!!

If anyone needs help, give me a buzz. I'll help you.

[guayoyo]

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:

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

Output:

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