Sets...
Moderator: Board moderators

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Sets...
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
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

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Hello Zyaad Jaunnoo.
Try 608 too.
Eduard.
I think so too.I think "false coin  problem 665" is a good example that can be solved using sets...
Try 608 too.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Problems 10583,10608,10685 can be solved using sets but standart set is too small, you must make your own set.
Try them.
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

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

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

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 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..
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..
Yes you are right 10227 is very good Set problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650