11020 - Efficient Solutions

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

11020 - Efficient Solutions

Post by 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
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by 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
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by 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
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by 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
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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?
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by 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.
Sorry For My Poor English.. :)

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by 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.
If only I had as much free time as I did in college...

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by andresw1 »

Hello,

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

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword »

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

Gaizka
New poster
Posts: 7
Joined: Wed May 24, 2006 12:37 am

Post by 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
New poster
Posts: 7
Joined: Wed May 24, 2006 12:37 am

Post by 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
New poster
Posts: 11
Joined: Wed Aug 17, 2005 5:59 pm
Location: Caracas, Venezuela

Need Help, always WA

Post by 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
10024 - Guayoyo has Curled Up the Cube!

Post Reply

Return to “Volume 110 (11000-11099)”