Google Code Jam just got over today. As usual there were 5 problems, out of which first 3 were pretty easy and rest 2 were little difficult. But with a little good brute force approach, even first subtask of 5th problem was pretty easy.
Only thing difficult was to get full point in 4th and 5th problem. Here are the editorials of first 3 problems :
His exact same solution was uploaded on github at 8:30 AM by a guy on github and since then 1000-2000 people copied his code and submitted the same for the contest.
Also, that tmwilliam-lin guy from codeforces, uploaded the solution video for all problems from A to D in morning. What a shame , why to fuck with a contest just for few more subscribers .
And now you have a screwed up rank list where everyone solved from A to D and this guy who solved all the questions, he has definitely copied.
Hi I have made solution in O(n) and working for sample cases but not accepted in result. Please help me in getting solution.’ #include #include <bits/stdc++.h>
using namespace std;
class job
{
public:
int index, arr, dep;
};
this is my solution to parenting partnering returns it is giving WA i am not able to understand why it is wrong.
#include <bits/stdc++.h>
using namespace std;
long long int M= 1000000007;
int fun(vector& v,int start,int end)
{
for (int i = start; i < end; i++)
{ if (v[i]!=1)
{return -1;}
}
for (int i = start; i < end; i++)
{ v[i]=0; }
return 1;
}
int main()
{ int t,z;
cin >> t;
z=t;
while (t–)
{
int n,x,k, ans,ctr=0,flag=0,ele1,ele2;
cin>>n;
string str;
vector cv(200000,1),jv(200000,1),s,e;
for (int i = 0; i < n; i++)
{ cin>>ele1>>ele2;
s.push_back(ele1);
e.push_back(ele2);
}
for ( int i = 0; i < n; i++)
{int temp=0;
temp=fun(cv,s[i],e[i]);
if(temp==1)
{str=str+‘C’;}
else if(temp==-1)
{int temp2=0;
temp2=fun(jv,s[i],e[i]);
if(temp2==1)
{str=str+‘J’;}
else if(temp2==-1)
{flag=-1;break;}
}
}
if(flag==-1)
{cout<<“Case #”<<z-t<<": IMPOSSIBLE"<<endl;}
else
{cout<<“Case #”<<z-t<<": "<<str<<endl;}
Yes, there is. Make a list of event times, there are discrete point of times from 0 to 24x60.
In each of those point of time, you can list the ins and outs activities. For instance, if there’s an activity starting at 5 ending at 10, then insert an “in” event at time slot 5, and and “out” event at time slot 10.
You just need start with empty assignment, and go thru each time t, and see if there are ins or outs events there.
Process the outs first, so you can free C or J who’s assigned. Then proceed to see if there are ins events at the same time and start assigning C or J. If both are already assigned, then this is impossible.
That’s it. Your processing time would only amount to the maximum number of events (ins and outs). Should count as O(n).