Sets...

Zyaad Jaunnoo · 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

Zyaad Jaunnoo · 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 · 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.

Zyaad Jaunnoo · 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 · 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.

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

Thanks man! Will have a look @ them

mf · 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 · 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 · 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 · Post by **Eduard** » Fri May 06, 2005 4:23 pm

Yes you are right 10227 is very good Set problem.