Google Code Jam is a competitive programming contest where students all over the world compete by solving complex problems for a grand prize of $15,000.
The qualifier for the same was held on Apr 3 2020, 23:00 UTC with a time limit of 27 hours and anyone scoring 30 points or above would qualify for the next round. I started solving the questions when there was around 14 hours for the competition to finish and by that time a lot of contestants had already solved all the questions with a perfect score.
The rank 1 holder had done exactly that in the first hour!
I managed to solve the first 3 questions which was enough for me to qualify so I left it at that. The remaining 2 questions were too tough for me.
1. Vestigium
|1|2|3|
|2|3|1| This is a 3 x 3 natural latin square.
|3|1|2|
In this problem we deal with natural latin squares which is a N x N matrix where each element is a number from 1 to N(inclusive) and each element can only occur once in a single column and row.
What we need to do --
- Calculate the trace of the matrix which is the sum of the elements in the main diagonal which is the diagonal from the top left to bottom right.
- Check if a given matrix is a latin square and also calculate the number of rows and columns with repeated elements.
To read the whole question, click on the link above.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t=0, i=0, j=0, k=0, n=0;
cin>>t;
for(i=0;i<t;i++){
cin>>n;
int arr[n][n],arr1[n][n];
int trace=0, r=0, c=0;
bool flag=false, flag1=false;
for(j=0;j<n;j++){
for(k=0;k<n;k++){
cin>>arr[j][k];
if(j==k){
trace+=arr[j][k];
}
}
}
for(j=0;j<n;j++) {
for(k=0;k<n;k++) {
arr1[k][j] = arr[j][k];
}
}
for (int x = 0 ; x < n; x++){
sort(arr[x], arr[x] + n);
sort(arr1[x], arr1[x] + n);
}
for(j=0;j<n;j++){
flag=false;
flag1=false;
for(k=1;k<n;k++){
if(arr[j][k]==arr[j][k-1]){
flag=true;
}
if(arr1[j][k]==arr1[j][k-1]){
flag1=true;
}
if(k==n-1 && flag==true){
r++;
}
if(k==n-1 && flag1==true){
c++;
}
}
}
cout<<"Case #"<<i+1<<": "<<trace<<" "<<r<<" "<<c<<endl;
}
return 0;
}
Here trace is the trace of the matrix, r and c are the number of rows and columns with repeated digits.
Calculating the trace was pretty easy. While taking the input, I put an if statement to check if the index of the element being inserted is of the form aij where i==j and added the elements.
I now realise that this algorithm is flawed because it is in O(N2) time while the same operation can be done in O(N) time by using a single for loop as follows:
for(int i=0; i<N;i++){
trace+=arr[i][i];
}
Next what I did is I created a copy of the original array and obtained the transpose of the matrix. This was done to calculate the columns.
Next I sorted the 2 arrays by row which takes O(Nlog(N)) time. After sorting the arrays, any duplicate elements come together. So I iterated over the arrays and checked if any 2 adjacent are equal and incremented r or c accordingly.
This is the required solution.
2. Nesting Depth
Given a string of digits S, insert a minimum number of opening and closing parentheses into it such that the resulting string is balanced and each digit d is inside exactly d pairs of matching parentheses.
For example, if we have a string '121', we need to convert it to '(1(2)1)'. As you can see, each digit is enclosed in the minimum number of parenthesis according to the digit. A string like '(1)((2))(1)' which is balanced would not be a correct answer because it is not the minimum number of parenthesis.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int x=0; x<t;x++){
string s;
cin>>s;
string ans = "";
int id=0, fd=0, j, fdd, idd;
for(int i=0; i<s.length();i++){
fd=s[i]-48;
if(fd-id==0){
ans+= s[i];
}
else if(fd-id>0)
{
for(j=id; j<fd;j++){
ans+="(";
id++;
}
ans+=s[i];
}
else if(fd-id<0){
fdd=fd;
idd=id;
for(int k=fdd; k<idd;k++){
ans+=")";
id--;
}
ans+=s[i];
}
if(i==s.length()-1 && s[i]!='0'){
for(int z=0; z<fd;z++){
ans+=")";
}
}
}
cout<<"Case #"<<x+1<<": "<<ans<<endl;
}
return 0;
}
Here, s is the input string and ans is the output string which is initialised to be empty in the beginning.
My code works in O(N2) time in the worst case scenario.
What I did is initialised 2 variables id which is the initial depth and fd which is the final depth. Both of them are initialised to 0 at the beginning. The depth here is the level of nesting required for a digit to be balanced. A digit with a depth of 2 will need 2 braces and so on.
The first loop iterates over the input string. During the iteration, the character is then converted to an integer which I did by subtracting 48 from its ASCII value which where the digits start from in the ASCII notation and stored it into the fd variable.
If the value of fd-id which is the depth for that digit is 0, we directly concatenate that digit to the output string ans.
If the depth is positive it means we need to add opening parenthesis "(" which would be equal to the value of fd-id and if the depth is negative, we need to add closing parenthisis ")" in the same manner.
After adding the braces, the digit is then concatenated to the output string.
This goes on till the last digit in the string. After adding the last digit, we need to assume that there is an additional 0 at the end because otherwise the string would not be balanced. This is done by the last if statement in the code.
After that, our answer can be output to the screen.
3. Parenting Partnering Returns
This question is a little trickier that the first 2.
We have a couple, Jamie and Cameron who have have a 3 year old kid and they have scheduled a number of activites for the kid. The condition is that the same person cannot perform 2 activities that overlap.
An example of such a schedule is --
Suppose that Jamie and Cameron need to cover 3 activities: one running from 18:00 to 20:00, another from 19:00 to 21:00 and another from 22:00 to 23:00.
One possibility would be for Jamie to cover the activity running from 19:00 to 21:00, with Cameron covering the other two. Another valid schedule would be for Cameron to cover the activity from 18:00 to 20:00 and Jamie to cover the other two.
Notice that the first two activities overlap in the time between 19:00 and 20:00, so it is impossible to assign both of those activities to the same partner.
We are given the starting and ending time of each activity and we need to schedule the activities as per the above constraints. If it is not possible to form a schedule like that, we need to output "IMPOSSIBLE" otherwise we need to output the order in which Jamie and Cameron performs their activities.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000 + 5;
struct work {
int l, r, id;
};
int TC, N;
work arr[MAX_N];
bool cmp (work a, work b) { // sort based on starting time
if (a.l == b.l) return a.r < b.r;
return a.l < b.l;
}
int main() {
cin.tie(0); cout.tie(0);
cin >> TC;
for (int t = 1; t <= TC; t++) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i].l >> arr[i].r;
arr[i].id = i;
}
sort(arr, arr + N, cmp);
int C_end = -1, J_end = -1;
char ans[N];
bool valid = true;
for (int i = 0; i < N; i++) {
if (C_end <= arr[i].l) {
ans[arr[i].id] = 'C';
C_end = arr[i].r;
}
else if (J_end <= arr[i].l) {
ans[arr[i].id] = 'J';
J_end = arr[i].r;
}
else {
valid = false;
break;
}
}
cout << "Case #" << t << ": ";
if (valid) {
for (int i = 0; i < N; i++) cout << ans[i];
}
else cout << "IMPOSSIBLE";
cout << "\n";
}
return 0;
}
Writing this piece of code was such a pain in the ass. I tried numerous other data structures like set, pairs and vector and finally went back to good ol' struct.
I stored the start time, end time and the id which is a number assigned to each activity in the struct work.
cmp is a comparator function to help sort the array of type work.
After sorting the array which is again an O(Nlog(N)) operation, we iterate over the array and check if the end of Cameron's activity overlaps with the next activity, if it does not, we append "C" into our character array ans[N] with the index arr[i].id.
If Cameron's activity overlaps, we assign the next activity to Jamie in the similar manner as above.
If both of them overlap, we the flag valid=false which will trigger our ending if-else statement to output "IMPOSSIBLE".
Otherwise, we output the contents of our character array ans.
This is the reqired solution.
That is how I qualified in Google Code Jam 2020 and I am looking forward to the next round which is 4 days from now.
If you enjoyed reading this post please share in the comments below. If you have any doubts regarding the code, let me know and I'll try to clear it out.
My Portfolio: https://rahul-thapa.github.io
Read my previous posts:
- CodeAcademy Is Giving Away 10,000 Pro Subscriptions To Students For Free
- Building A FullStack Website With MERN #4 | Deployed To Heroku
- Building A FullStack Website With MERN #3 | Connecting The Backend And Frontend Together
- Building A FullStack Website With MERN #2 | Moving Data To Application State
- Building A FullStack Website With MERN #1 | Introduction cum Redux Rant