## Sets...

Write here if you have problems with your Pascal source code

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

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

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

Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am
Thanks man! Will have a look @ them

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.

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

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

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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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