I would like to ask for some help for the recent Code Jam problem Parenting
Partnering Returns. I wrote my solution in C++11.
My solution returns Sample Failed: WA - though I cannot figure out an
example test case that makes my code fail.
My solution is close to what was described in the analysis for Test Set 2 I
believe.
I use a priority queue to have the earliest start time (in case of equality
the earlier end time).
I keep a list of scheduled activities; those should never exceed 2 (or
equivalently one parent must be available) when scheduling a new activity,
otherwise it is impossible.
I am thinking of edge cases, but cannot figure out in which case this
fails. I would appreciate if someone could review my code and share any
feedback. Thank you in advance.
Below my code formatted using clang-format. I hope it is ok so.
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <string>
#include <utility>
int main() {
int T;
std::cin >> T;
for (size_t t = 1; t <= T; t++) {
int N;
std::cin >> N;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int,
int>>,
std::greater<std::pair<int, int>>>
q;
for (size_t n = 0; n < N; n++) {
std::pair<int, int> activity;
std::cin >> activity.first >> activity.second;
q.push(activity);
}
std::set<char> parents;
parents.insert('C');
parents.insert('J');
std::string output;
std::list<std::pair<std::pair<int, int>, char>> schedule;
bool impossible = false;
while (!q.empty()) {
std::pair<int, int> activity = q.top();
schedule.remove_if(
[&activity, &parents](const std::pair<std::pair<int, int>, char>
&scheduled_activity) mutable {
if (scheduled_activity.first.second <= activity.first) {
parents.insert(scheduled_activity.second);
return true;
}
return false;
});
if (parents.empty()) {
impossible = true;
break;
} else {
auto parent = parents.begin();
output.append(1, *parent);
schedule.push_back(std::make_pair(activity, *parent));
parents.erase(*parent);
}
q.pop();
}
if (impossible) {
std::cout << "Case #" << t << ": IMPOSSIBLE" << std::endl;
} else {
std::cout << "Case #" << t << ": " << output << std::endl;
}
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/94c09016-4dbd-4149-be15-75f697b064a2%40googlegroups.com.
