@Olena Lizina
I also did it in C++ and passed all test cases have a look on my approach
its straight forward hope you can find your solution in this if possible:).
#include<bits/stdc++.h>
using namespace std;
struct person
{
int arri;
int depart;
int val;
};
bool cmp(person a,person b)
{
return a.arri<b.arri;
}
int main(){
int t;
cin>>t;
int g=1;
while(t--)
{
int n,p=0;
cin>>n;
string res,s;
set<int>c;
set<int>j;
struct person tr[n];
for(int i=0;i<n;i++){
cin>>tr[i].arri;
cin>>tr[i].depart;
tr[i].val = i;
}
sort(tr,tr+n,cmp);
c.insert(tr[0].depart);
int l=0;
res.push_back('C');
for(int i=1;i<n;i++){
if(tr[i-1].depart>tr[i].arri){
if(l==1){
l=0;
}else{
l=1;
}
}
if(l==1){
res.push_back('J');
if(j.empty()){
j.insert(tr[i].depart);
}else{
if(*--j.end()>tr[i].arri){
p=1;
break;
}else{
j.insert(tr[i].depart);
}
}
}else{
res.push_back('C');
if(*--c.end()>tr[i].arri){
p=1;
break;
}else{
c.insert(tr[i].depart);
}
}
if(p==1){
break;
}
}
if(p!=1){
vector< pair <int,char> > vect;
for(int i=0;i<n;i++){
vect.push_back(make_pair(tr[i].val,res[i]));
}
sort(vect.begin(),vect.end());
for(int i=0;i<n;i++){
s.push_back(vect[i].second);
}
cout<<"Case #"<<g++<<": "<<s<<endl;
}else{
cout<<"Case #"<<g++<<": "<<"IMPOSSIBLE"<<endl;
}
}
return 0;
}
On Tuesday, April 7, 2020 at 9:26:14 PM UTC+5:30, Olena Lizina wrote:
>
> I tried to submit 2 different solutions: sorted by start time and not
> sorted.
> Both solutions failed.
> Sorted by start time -> I didn't print them in the original order. So
> simple tests failed because of that. Thank you.
>
> But for the original order -> which corner cases did you test for your
> solution?
>
> вторник, 7 апреля 2020 г., 4:05:53 UTC+3 пользователь Leandro Coutinho
> написал:
>>
>> Does your code print the answer in the original order?
>>
>> On Monday, April 6, 2020 at 9:45:39 PM UTC-3, 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/c6344225-4524-4207-88f9-78c143912015%40googlegroups.com.
