Sets...

Write here if you have problems with your Pascal source code

Moderator: Board moderators

Post Reply
Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Sets...

Post by Zyaad Jaunnoo » Fri Apr 01, 2005 3:19 pm

Are there problems that deal with sets theory on the UVA?
Do C or C++ have structures dealing with sets directly as pascal provides?

P.S: Sorry for talking about C and C++ in this forum :wink:

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Thu May 05, 2005 1:03 pm

I think "false coin - problem 665" is a good example that can be solved using sets...

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu May 05, 2005 3:12 pm

Hello Zyaad Jaunnoo.
I think "false coin - problem 665" is a good example that can be solved using sets...
I think so too.
Try 608 too.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Thu May 05, 2005 5:07 pm

Thanks. It is quite the same problem description as 665.
Are there other problems from other volumes?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu May 05, 2005 5:14 pm

Problems 10583,10608,10685 can be solved using sets but standart set is too small, you must make your own set.
Try them.
Last edited by Eduard on Thu May 05, 2005 8:46 pm, edited 2 times in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Thu May 05, 2005 5:34 pm

Thanks man! Will have a look @ them

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu May 05, 2005 7:15 pm

Could somebody enlighten me, how sets can be used in 608/665?
My solution was just a brute force - to test every possibility, and I'd like to learn if there's a more elegant solution.

The problem 496 "Simply Subsets" is also a quite nice problem on set theory.

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Fri May 06, 2005 9:15 am

What about 10227 - Forests?

But i cant get AC.. may be am making some errors while taking input :(

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Fri May 06, 2005 10:13 am

I just got 10227 (Forests) Accepted using C++ :( Anyway here's the algorithm to solve False coin problem (665)

Define 2 sets, lets say, Less and More holding the possible coins which are fake.
At first Less := [1..n] and More := [1..n]
Then, read the 2 sets of coins contained in the 2 pans. Store them in 2 separate sets, namely Left and Right.

If the weight of both pans are equal then the coins are definitely not fake.. meaning that we can eliminate those coins from our previous sets Less and More
Less := Less - Left - Right
More := More - Left - Right

If the left pan weighs less, that means that the fake coin is either on the left pan or the right pan, which leads to:
Less := Less * Left
More := More * Right

If the left pan weighs more, that means the false coin is either on the left or the right pan, which leads this time to:
Less := Less * Right
More := More * Left

Finally, the false coin can be found by Remaining := Less + More, where Remaining is another set

If the number of elements in Remaining[] is only 1 then this is the false coin.

* means intersection, + means union and minus (-) means difference of the 2 sets.

Hope that helps..

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Fri May 06, 2005 4:23 pm

Yes you are right 10227 is very good Set problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Post Reply

Return to “Pascal”