Chad Parry
BAN USERThis dynamic computing solution took me an hour to write and 20 minutes with a compiler to debug, plus I had to check the documentation for next_permutation. That's a pretty hard question to encounter in an interview.
This solution would need lots of comments to really be useful. The idea is that it is going to check every possible combination of which guesses could be right and wrong. Suppose a key element is guessed to be "1" in the first round. If we hypothesize that guess is wrong, then that key element must be equal to one of { "2", "3", "4" }. On the other hand, if that guess is right, then the key element must be in { "1" }. We keep sets to show all the possibilities that any part of the key could be. Each round gives us more constraints for each part of the key. For example, based on our guess in the second round, we might believe that same key element to be in { "1", "3", "4" }. We can intersect one of our hypotheses from the first round { "2", "3", "4" } with the information from the second round { "1", "3", "4" } and derive a new constraint that the key must be in { "3", "4" }.
If it ever looks like the key must be in the empty set { }, then that means we should discard that possibility, because it is impossible. If we end up discarding all possibilities from a round, then there is no way the game was valid. The program prints "Yes" or "No" depending on whether a valid game could exist.
There are an exponential number of combinations that need to be tested, because every hypothesis from one round must be tried with every hypothesis of the other rounds. The algorithm does its best to discard false hypotheses as quickly as possible though. On my laptop, it computes most games instantly, although for the largest games, it can run for over a minute. I consider that to be pretty good for this size of problem though. It's much faster than the simple brute-force approach for most games, but comparable in speed for pathological games.
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::inserter;
using std::next_permutation;
using std::set;
using std::set_intersection;
using std::vector;
bool check_possible(vector<set<vector<set<int>>>> const &constraints) {
if (constraints.empty()) {
return true;
}
for (auto choice = constraints.front().begin(); choice != constraints.front().end(); ++choice) {
vector<set<vector<set<int>>>> intersected_constraints;
for (auto cascade = ++constraints.begin(); cascade != constraints.end(); ++cascade) {
set<vector<set<int>>> intersected_round;
for (auto possibility = cascade->begin(); possibility != cascade->end(); ++possibility) {
vector<set<int>> intersected_possibility;
for (size_t elem_idx = 0; elem_idx < possibility->size(); ++elem_idx) {
set<int> intersected;
set_intersection(
(*choice)[elem_idx].begin(), (*choice)[elem_idx].end(),
(*possibility)[elem_idx].begin(), (*possibility)[elem_idx].end(),
inserter(intersected, intersected.begin()));
if (intersected.empty()) {
break;
}
intersected_possibility.push_back(intersected);
}
if (intersected_possibility.size() == possibility->size()) {
intersected_round.insert(intersected_possibility);
}
}
if (intersected_round.empty()) {
break;
}
intersected_constraints.push_back(intersected_round);
}
if (intersected_constraints.size() == constraints.size() - 1) {
if (check_possible(intersected_constraints)) {
return true;
}
}
}
return false;
}
int main(int argc, char const *argv[]) {
int test_case_count;
cin >> test_case_count;
for (int test_case_idx = 0; test_case_idx < test_case_count; ++test_case_idx) {
int n, q, k;
cin >> n >> k >> q;
vector<vector<int>> guesses;
vector<int> scores;
for (int round_idx = 0; round_idx < q; ++round_idx) {
guesses.push_back(vector<int>());
for (int elem_idx = 0; elem_idx < k; ++elem_idx) {
int elem;
cin >> elem;
guesses.back().push_back(elem);
}
int score;
cin >> score;
scores.push_back(score);
}
// There's a utility called iota that could do this block better, but I couldn't remember what it looked like.
set<int> ALL;
for (int n_idx = 0; n_idx < n; ++n_idx) {
ALL.insert(n_idx);
}
vector<set<vector<set<int>>>> constraints;
for (int round_idx = 0; round_idx < q; ++round_idx) {
constraints.push_back(set<vector<set<int>>>());
vector<int> const &guess = guesses[round_idx];
int const &score = scores[round_idx];
// One of the STL helpers could do this block better too.
vector<bool> filter;
for (int i = 0; i < k - score; ++i) {
filter.push_back(false);
}
for (int i = 0; i < score; ++i) {
filter.push_back(true);
}
do {
vector<set<int>> constraint;
for (int elem_idx = 0; elem_idx < k; ++elem_idx) {
if (filter[elem_idx]) {
set<int> possibilities = { guess[elem_idx] };
constraint.push_back(possibilities);
} else {
set<int> possibilities(ALL);
possibilities.erase(guess[elem_idx]);
constraint.push_back(possibilities);
}
}
constraints.back().insert(constraint);
} while (next_permutation(filter.begin(), filter.end()));
}
bool possible = check_possible(constraints);
if (possible) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
Sure, don't put this version into production. :)
Both 6 and 9 are divisible by 3. If n is not divisible by 3, then you can't sum to n with any number of just 6's or 9's. You'll need at least 1 or 2 of the 20-count packages. The first line figures out the minimum number of 20-count packages that will be necessary, so that the remaining sum is divisible by 3. In the second line, the n variable is decreased by the number of McNuggets in the 20-count packages.
At that point we know that the value in n is divisible by 3, (because we carefully chose the number of 20-count packages with just that goal in mind). Sometimes that number may not be divisible by 6 though. In that case, we need a minimum of 1 9-count package. So in the third line, we decide whether we need a 9-count package in order to make the remainder evenly divisible by 6. We'll need 0 or 1 9-count packages, but we'll never need more than 1 to make the remaining sum divisible by 6. In the fourth line, we decrease n by the number of McNuggets in the 9-count package, if there is one.
After that, whatever remains in n is divisible by 6, so we can divide to see how many 6-count packages would be needed.
The calculations above will work for any n, and will quickly find the minimum number of 20- and 9-count packages that are needed to arrive at the correct total. However, suppose that n is less than 40, and yet we calculate that we need a minimum of 2 20-count packages to get an exact sum. Those are the cases where it would be impossible to buy to n exactly. For example, if n is 19, then c will be 2 and b will be 1, and a will end up being -5. We would have to buy a minimum of 49 McNuggets just to turn n into something divisible by 6, but that is more than our original target of 19. The algorithm tries to compensate by buying a negative number of 6-count packages. That's why the final line tests to see if a is negative, because that means it is impossible to buy to that count exactly.
A lot of people try dynamic computing on this problem, because it looks similar to the "subset sum" problem, which is NP-complete. But there is a huge difference here: none of the package sizes are negative. That means that an analytic solution is possible. The first version I wrote runs in O(n) time, and the second in O(1) time.
Now that I've seen someone else's solution, I wish I had iterated over the string from right-to-left.
long parse_roman(string const &roman) {
static map<char, long> values = {
{'I', 1 },
{'V', 5 },
{'X', 10 },
{'L', 50 },
{'C', 100 },
{'D', 500 },
{'M', 1000 },
};
long total = 0;
long lastdigit = 0;
long lastrun = 0;
for (auto i = roman.begin(); i != roman.end(); ++i) {
auto value = values.find(*i);
if (value == values.end()) {
ostringstream message;
message << "Illegal digit: " << *i;
throw runtime_error(message.str());
}
long digit = value->second;
if (digit == lastdigit) {
lastrun += digit;
} else {
if (digit < lastdigit) {
total += lastrun;
} else {
total -= lastrun;
}
lastdigit = lastrun = digit;
}
}
total += lastrun;
return total;
}
def flatten(input):
if isinstance(input, int):
yield input
else:
for elem in input:
for nested in flatten(elem):
yield nested
Here's one solution that aims for simplicity.
def laceStrings(s1, s2):
out = []
for i in xrange(max(len(s1), len(s2))):
out += [s1[i:i+1], s2[i:i+1]]
return ''.join(out)
If you have the itertools documentation handy, then this is more robust.
def laceStrings(*s):
return ''.join(itertools.chain.from_iterable(itertools.izip_longest(fillvalue='', *s)))
Note that there is another elegant solution called "roundrobin" in the itertools documentation.
- Chad Parry November 04, 2012def laceStringsRecur(s1, s2):
"""
s1 and s2 are strings.
Returns a new str with elements of s1 and s2 interlaced,
beginning with s1. If strings are not of same length,
then the extra elements should appear at the end.
"""
def helpLaceStrings(s1, s2, out):
if s1 == '':
return out + s2
if s2 == '':
return out + s1
else:
return helpLaceStrings(s1[1:], s2[1:], out + s1[0] + s2[0])
return helpLaceStrings(s1, s2, '')
# Fast analytical solution using modular arithmetic
def McNuggets(n):
c = -n % 3
n -= c*20
b = n // 3 % 2
n -= b*9
a = n // 6
return a >= 0
# Degenerate solution, since all large numbers are reachable
def McNuggets(n):
return n not in frozenset((1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43))
- Chad Parry November 29, 2012