Also replying without debugging... My solution seems a bit simpler than
yours.. It seems it's much easier to do when sorting, but sorting messes
with the output. So I create an ID before sorting, and to publish the
results, I use that ID.
I don't have my code right now, but I can get it later and post here.
On Tuesday, 7 April 2020 02:06:12 UTC+1, fayyaz lodhi wrote:
>
> So a couple of quick things without debugging your entire code since i was
> stuck on this for a while in a similar situation and was able to figure out
> the problems and pass eventually.
>
> 1) After sorting activities by start time, your solution should still be
> written maintaining the original order of the input string. You can input
> any valid solution as long as that solution works for the original order
> (not the sorted order). I discovered this after failing the first test set.
> There are many ways to do this. One way is to create a duplicate array
> first before sorting the second one. Once you have the final string,
> reorder it based upon looking through matching indexes in the original
> array.
>
> 2) Does your code account for duplicate intervals? My initial code failed
> for cases like [1, 7] and [1, 10] as well as [1, 3] [1, 3]. It passed once
> i solved for those while maintaining the solution to work for 1) as well.
>
> On Monday, April 6, 2020 at 5:45:39 PM UTC-7, 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/b99bea44-8392-4f2b-9ecf-a0c8ffde39e7%40googlegroups.com.
