Solution with explanation for parenting partnering here:-
https://www.golibrary.co/google-codejam-2020-parenting-partnering-returns-solution/?fbclid=IwAR2SJfghu5n0yU1eTueA8SjGZ9Gcc5yIGj6i-pLCV5l-DJR_YJIUuwQBam8
On Tuesday, 7 April 2020 10:45:39 UTC+10, Olena Lizina wrote:
>
> Hi all,
>
> I didn't pass the Qualification Round 2020 because stuck with Parenting
> Partnering Returns.
> My solution passes the Sample test cases, but failed on the first Test Set.
>
> I wrote unit tests and tried different data sets to test my code, but the
> Google System didn't accept it.
> Today I checked solutions of others. Found an interesting solution and
> tried to find out what did I miss.
> Found nothing :-(
>
> Can anybody help my to find some corner cases that I missed?
> Please!
>
> #include <iostream>
> #include <vector>
> #include <algorithm>
>
> using namespace std;
>
> class Activity
> {
> public:
> Activity(const int startTime, const int endTime)
> : m_startTime{startTime}
> , m_endTime{endTime}
> {
> }
>
> bool overlaps(const Activity& other) const
> {
> bool result {true};
> if (m_startTime > other.m_startTime)
> {
> result = m_startTime < other.m_endTime;
> }
> else
> {
> result = other.m_startTime < m_endTime;
> }
> return result;
> }
>
> int m_startTime;
> int m_endTime;
> };
>
> class Schedule
> {
> public:
> void addActivity(const Activity& activity)
> {
> m_activities.push_back(activity);
> }
>
> void sortActivities()
> {
> std::sort(m_activities.begin(), m_activities.end(), [](Activity lhs,
> Activity rhs)
> {
> return lhs.m_startTime < rhs.m_startTime;
> });
> }
>
> std::string getSchedule()
> {
> std::string res;
>
> std::vector<Activity> Jamies;
> std::vector<Activity> Camerons;
>
> for (size_t i = 0; i < m_activities.size(); ++i)
> {
> auto& currActivity = m_activities.at(i);
> if (Jamies.cend() == std::find_if(Jamies.cbegin(), Jamies.cend(),
> [&currActivity](const Activity& activity)
> {
> return activity.overlaps(
> currActivity);
> }))
> {
> Jamies.push_back(currActivity);
> res += "J";
> }
> else if (Camerons.cend() == std::find_if(Camerons.cbegin(),
> Camerons.cend(), [&currActivity](const Activity& activity)
> {
> return activity.
> overlaps(currActivity);
> }))
> {
> Camerons.push_back(currActivity);
> res += "C";
> }
> else
> {
> res = "IMPOSSIBLE";
> break;
> }
> }
> return res;
> }
> private:
> std::vector<Activity> m_activities;
> };
>
> void assert(const std::string& func, const bool validate)
> {
> if (validate)
> {
> std::cout << func << ": OK" << std::endl;
> }
> else
> {
> std::cout << func << ": NOK" << std::endl;
> }
> }
>
> void testActivity()
> {
> {
> Activity lhs(0, 1);
> Activity rhs(0, 1);
> assert(__FUNCTION__, lhs.overlaps(rhs));
> assert(__FUNCTION__, rhs.overlaps(lhs));
> }
> {
> Activity lhs(0, 10);
> Activity rhs(0, 1);
> assert(__FUNCTION__, lhs.overlaps(rhs));
> assert(__FUNCTION__, rhs.overlaps(lhs));
> }
> {
> Activity lhs(0, 10);
> Activity rhs(3, 10);
> assert(__FUNCTION__, lhs.overlaps(rhs));
> assert(__FUNCTION__, rhs.overlaps(lhs));
> }
> {
> Activity lhs(0, 10);
> Activity rhs(10, 15);
> assert(__FUNCTION__, !lhs.overlaps(rhs));
> assert(__FUNCTION__, !rhs.overlaps(lhs));
> }
> {
> Activity lhs(0, 10);
> Activity rhs(11, 15);
> assert(__FUNCTION__, !lhs.overlaps(rhs));
> assert(__FUNCTION__, !rhs.overlaps(lhs));
> }
> {
> Activity lhs(15, 20);
> Activity rhs(10, 15);
> assert(__FUNCTION__, !lhs.overlaps(rhs));
> assert(__FUNCTION__, !rhs.overlaps(lhs));
> }
> }
>
> void testSchedule()
> {
> {
> Schedule today;
> today.addActivity(Activity{360, 480});
> today.addActivity(Activity{420, 540});
> today.addActivity(Activity{600, 660});
> assert(__FUNCTION__, (today.getSchedule() == "JCJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 1440});
> today.addActivity(Activity{1, 3});
> today.addActivity(Activity{2, 4});
> assert(__FUNCTION__, (today.getSchedule() == "IMPOSSIBLE"));
> }
> {
> Schedule today;
> today.addActivity(Activity{99, 150});
> today.addActivity(Activity{1, 100});
> today.addActivity(Activity{100, 301});
> today.addActivity(Activity{2, 5});
> today.addActivity(Activity{150, 250});
> assert(__FUNCTION__, (today.getSchedule() == "JCCJJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{720, 1440});
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{0, 720});
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{0, 500});
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{300, 720});
> today.addActivity(Activity{500, 720});
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{721, 1440});
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{720, 900});
> today.addActivity(Activity{900, 1440});
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> }
>
> void testSortedSchedule()
> {
> {
> Schedule today;
> today.addActivity(Activity{360, 480});
> today.addActivity(Activity{420, 540});
> today.addActivity(Activity{600, 660});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JCJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 1440});
> today.addActivity(Activity{1, 3});
> today.addActivity(Activity{2, 4});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "IMPOSSIBLE"));
> }
> {
> Schedule today;
> today.addActivity(Activity{99, 150});
> today.addActivity(Activity{1, 100});
> today.addActivity(Activity{100, 301});
> today.addActivity(Activity{2, 5});
> today.addActivity(Activity{150, 250});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JCCJC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{720, 1440});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{0, 720});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{0, 500});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{300, 720});
> today.addActivity(Activity{500, 720});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JC"));
> }
> {
> Schedule today;
> today.addActivity(Activity{0, 720});
> today.addActivity(Activity{721, 1440});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> {
> Schedule today;
> today.addActivity(Activity{720, 900});
> today.addActivity(Activity{900, 1440});
> today.sortActivities();
> assert(__FUNCTION__, (today.getSchedule() == "JJ"));
> }
> }
>
> int main()
> {
> // testActivity();
> // testSchedule();
> // testSortedSchedule();
>
> size_t tests {0};
> std::cin >> tests;
>
> for (size_t test = 1; test <= tests; ++test)
> {
> size_t numActivities {0};
> std::cin >> numActivities;
>
> Schedule today;
> for (size_t i = 0; i < numActivities; ++i)
> {
> int start {0};
> int end {0};
> std::cin >> start >> end;
> today.addActivity(Activity{start, end});
> }
> // today.sortActivities();
> std::cout << "Case #" << test << ": " << today.getSchedule() << std
> ::endl;
> }
> return 0;
> }
>
> Also, when I sorted the activities by Start Time the Google System didn't
> let to pass even Sample Test cases.
> I checked the Output requirements and found that any valid result can be
> outputted.
>
> Please point me the reason!
>
--
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/234771dd-a654-4c9f-9d75-fd12cbbc86ac%40googlegroups.com.
