Can anybody help me with this problem Perfect Cakes.This problem was asked in Directi recruitment challenge.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Can anybody help me with this problem Perfect Cakes.This problem was asked in Directi recruitment challenge.
Name |
---|
This is the same problem as UVA 665 which by the way is a problem from NEERC 1998 (tests there aren't really that strong, though model solution is correct).
Since the sample cake has different mass than the others, imagine first that it has lower mass. Then perform all checks and mark the possibility for the cakes (for instance, if you have a < comparison, you mark the cakes on the left side as possible ones to be the different one in case you know nothing about them, and all the others, including those not in the comparison, as surely not being the sample cake).
Do the same if it had bigger mass and compare the solutions, either they point to the same cake or one gives an invalid solution and the other a unique solution. This is necessary since we only knew the cake had different mass than the others.