After reading the posts of others in this group I came to realize that the
output of the result must be in order of the input.
I will try to explain with the example test data from the problem
statement, one of the schedules is:
3
360 480
420 540
600 660
And a possible output is:
Case #1: CJC
If you change that sample to:
3
360 480
600 660
420 540
Then the output must not be:
Case #1: CJC
Rather, it should be:
Case #1: CCJ
I ran into that because my algorithm sorted the activities and I output the
sorted activities, but that was wrong.
I corrected my solution and now it passes fine, for your reference:
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
enum class parent
{
JAMIE,
CAMERON
};
struct activity
{
size_t order;
std::pair<int, int> time;
parent p;
activity(size_t o, int s, int e) : order{o}, time{s, e}
{
}
bool operator>(const activity &other) const
{
return time > other.time;
}
int start() const
{
return time.first;
}
int end() const
{
return time.second;
}
};
int main()
{
int T;
std::cin >> T;
for (size_t t = 1; t <= T; t++)
{
int N;
std::cin >> N;
std::vector<activity> result;
result.reserve(N);
std::priority_queue<activity, std::vector<activity>,
std::greater<activity>> q;
for (size_t n = 0; n < N; n++)
{
int start, end;
std::cin >> start >> end;
activity activity{n, start, end};
q.push(activity);
}
std::set<parent> parents;
parents.insert(parent::CAMERON);
parents.insert(parent::JAMIE);
std::list<activity> schedule;
bool impossible = false;
while (!q.empty())
{
activity current_acitivty = q.top();
q.pop();
schedule.remove_if(
[¤t_acitivty, &parents](const activity &scheduled_activity)
mutable {
if (scheduled_activity.end() <= current_acitivty.start())
{
parents.insert(scheduled_activity.p);
return true;
}
return false;
});
if (parents.empty())
{
impossible = true;
break;
}
else
{
auto parent = parents.begin();
current_acitivty.p = *parent;
schedule.push_back(current_acitivty);
parents.erase(*parent);
result.push_back(current_acitivty);
}
}
if (impossible)
{
std::cout << "Case #" << t << ": IMPOSSIBLE" << std::endl;
}
else
{
std::sort(result.begin(), result.end(), [](const activity &first,
const activity &second) {
return first.order < second.order;
});
std::string output;
output.reserve(N);
for (auto activity : result)
{
if (activity.p == parent::CAMERON)
output.push_back('C');
else
output.push_back('J');
}
std::cout << "Case #" << t << ": " << output << std::endl;
}
}
return 0;
}
Am Dienstag, 7. April 2020 03:04:14 UTC+2 schrieb Elyasin Shaladi:
>
> 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/ec4068de-861d-4c1e-9af4-d04ae1d9e278%40googlegroups.com.
