Google Code Jam 2020 Qualification Round Video Solutions

Hello guys,

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 :

  1. Problem 1 and Problem 2 :- Nested Depth
  2. Problem 3 :- Parenting Partnering Returns

Stay tuned as I will be posting solutions of other problems also.

Thank you and happy coding

8 Likes

Thanks for making tutorials.

1 Like

Here is a link to my solutions. Still, 5th one is not complete.

Thank You for sharing tutorials

1 Like

can you tell me whats wrong with my solution for problem C??
it gives correct answer. still WA!!!
using namespace std;
int main(){
int test,t;
scanf("%d",&test);
for(t=0;t<test;t++){
int n,j,start,end,jfree[2000]={0},cfree[2000]={0},k=0,cnt=0;
bool jok=true,cok=true;
char s[10005];
scanf("%d",&n);
for(j=0;j<n;j++){
jok=true;cok=true;
scanf("%d %d",&start,&end);
cnt=0;
for(int i=start;i<=end;i++){
if(jfree[i]!=0)cnt++;
if(cnt>1){jok=false;i=end;}
}
if(jok){
for(int i=start;i<=end;i++)jfree[i]=1;
s[j]=‘J’;
}
else{cnt=0;
for(int i=start;i<=end;i++){
if(cfree[i]!=0)cnt++;
if(cnt>1){
cok=false;i=end;
}
}
if(cok) {
for(int i=start;i<=end;i++)cfree[i]=1;
s[j]=‘C’;
}
else k=-1;
}
}
s[j]=’\0’;
if(k==-1)printf(“Case #%d: IMPOSSIBLE\n”,t+1);
else printf(“Case #%d: %s\n”,t+1,s);
}
}

Unfortunately I have seen this exact solution in someone else’s profile, who in LinkedIn claims to solve all the questions. Is this coincidence, as that guy and you are from different college?
Edit: His LinkedIn post: Siddharth K. on LinkedIn: #google #codejam #competitivecoding #coding | 61 comments

3 Likes

Is there O(n) solution for problem 3?

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.

2 Likes

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;
};

bool compare(job j1, job j2)
{
if(j1.dep == j2.dep)
return j1.arr < j2.arr;

return j1.dep < j2.dep;

}
int main()
{
int tc;
cin >> tc;
for(int t = 1; t <= tc; t++)
{
int n;
cin >> n;

    job jobs[n];
    
    for(int i = 0; i < n; i++)
    {
        cin >> jobs[i].arr >> jobs[i].dep;
        jobs[i].index = i;
    }
    
    sort(jobs, jobs+n, compare);

    job cJob;
    cJob.arr = -1;
    cJob.dep = -1;
    //= jobs[0];
    string result;
    for(int i = 0; i < n; i++)
    {
        result = result + " ";
    }
    //result[jobs[0].index] = 'C';
    job jJob;
    jJob.arr = -1;
    jJob.dep = -1;
    for(int i = 0; i < n; i++)
    {
        if(jobs[i].arr >= cJob.dep)
        {
            result[jobs[i].index] = 'C';
            cJob = jobs[i];
        }
        else if(jobs[i].arr >= jJob.dep)
        {
            result[jobs[i].index] = 'J';
            jJob = jobs[i];
        }
        else
        {
            result = "IMPOSSIBLE";
            break;
        }
    }
    
    cout << "Case #"<< t <<": " << result << endl;
}
return 0;

}
If anyone find error. Please connect mail: sunain99@gmail.com

Here is my nlogn solution
(#include<bits/stdc++.h>using namespace std;struct triple{ int first, - Pastebin.com)

1 Like

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;}

}
return 0;

}

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).

1 Like

Here is a link to my submissions.

Yeah for sorting one can use counting sort too. That will be O(24 * 60).

I think u cheated this solution from @anon55659401 ‘s solution ? isn’ it ?

how do you know, that he copied the solutions?

bro know some facts :slight_smile:

1 Like

nope,but it seems so bad that a 6 star coder have done this!

1 Like