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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/94c09016-4dbd-4149-be15-75f697b064a2%40googlegroups.com.