Saturday, May 30, 2020

Google Code Jam 2020 Qualification Round: Parenting Partnering Returns Solution

Problem Statement

Problem

Cameron and Jamie's kid is almost 3 years old! However, even though the child is more independent now, scheduling kid activities and domestic necessities is still a challenge for the couple.

Cameron and Jamie have a list of N activities to take care of during the day. Each activity happens during a specified interval during the day. They need to assign each activity to one of them, so that neither of them is responsible for two activities that overlap. An activity that ends at time t is not considered to overlap with another activity that starts at time t.

For example, 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.

Given the starting and ending times of each activity, find any schedule that does not require the same person to cover overlapping activities, or say that it is impossible.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of activities to assign. Then, N more lines follow. The i-th of these lines (counting starting from 1) contains two integers Si and Ei. The i-th activity starts exactly Si minutes after midnight and ends exactly Ei minutes after midnight.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no valid schedule according to the above rules, or a string of exactly N characters otherwise. The i-th character in y must be C if the i-th activity is assigned to Cameron in your proposed schedule, and J if it is assigned to Jamie.

If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2020 contest.)

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ Si < Ei ≤ 24 × 60.

Test set 1 (Visible Verdict)

2 ≤ N ≤ 10.

Test set 2 (Visible Verdict)

2 ≤ N ≤ 1000.

Sample


Input
 

Output
 
4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440

  
Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC

  

Sample Case #1 is the one described in the problem statement. As mentioned above, there are other valid solutions, like JCJ and JCC.

In Sample Case #2, all three activities overlap with each other. Assigning them all would mean someone would end up with at least two overlapping activities, so there is no valid schedule.

In Sample Case #3, notice that Cameron ends an activity and starts another one at minute 100.

In Sample Case #4, any schedule would be valid. Specifically, it is OK for one partner to do all activities.


Problem link
 

Video Tutorial

You can find the detailed video tutorial here
 

Thought Process

If you remember the leetcode "merge interval" question, this is quite similar. Baozi Training "Merge Interval"
Model the time range in internal, sort the intervals in ascending order based on the start time, then schedule either "C" or "J" as long as they are available. Update the end time with the assigned task.
The only caveat is we have to remember the original task index for output purpose because we sort the interval using the start time. 

An alternate solution is a "bipartite graph coloring" problem. In essence, model the interval into an interval graph. Each interval is a vertex in the graph, and if it overlaps with another interval, there would be an edge. Now the problem becomes starting with one node, if we could color the nodes in two colors without any conflicts. Note the graph doesn't need to be fully connected, a simple BFS with a visited hash map should do the trick. https://www.geeksforgeeks.org/bipartite-graph/
The time complexity of "bipartite graph coloring" is O(V+E)



Solutions

Greedy solution

Time Complexity: O(lgN) since we sort
Space Complexity: O(N) since we used extra list for the intervals

References

Saturday, May 23, 2020

Google Code Jam 2020 Qualification Round: Nesting Depth Solution

Problem Statement

Problem

tl;dr: 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.

Let the nesting of two parentheses within a string be the substring that occurs strictly between them. An opening parenthesis and a closing parenthesis that is further to its right are said to match if their nesting is empty, or if every parenthesis in their nesting matches with another parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching parentheses m such that p is included in the nesting of m.

For example, in the following strings, all digits match their nesting depth: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). The first three strings have minimum length among those that have the same digits in the same order, but the last one does not since ((22)1) also has the digits 221 and is shorter.

Given a string of digits S, find another string S', comprised of parentheses and digits, such that:

  • all parentheses in S' match some other parenthesis,
  • removing any and all parentheses from S' results in S,
  • each digit in S' is equal to its nesting depth, and
  • S' is of minimum length.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case and contains only the string S.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the string S' defined above.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 100.

Test set 1 (Visible Verdict)

Each character in S is either 0 or 1.

Test set 2 (Visible Verdict)

Each character in S is a decimal digit between 0 and 9, inclusive.

Sample


Input
 

Output
 
4
0000
101
111000
1

  
Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

  

The strings ()0000(), (1)0(((()))1) and (1)(11)000 are not valid solutions to Sample Cases #1, #2 and #3, respectively, only because they are not of minimum length. In addition, 1)( and )(1 are not valid solutions to Sample Case #4 because they contain unmatched parentheses and the nesting depth is 0 at the position where there is a 1.

You can create sample inputs that are valid only for Test Set 2 by removing the parentheses from the example strings mentioned in the problem statement.


Problem link
 

Video Tutorial

You can find the detailed video tutorial here
 

Thought Process

Simple simulation. Key points
  • An integer could be used for depth to record how many parentheses we need to append. (I used a stack in the code during the competition)
  • We could use a dummy node as the depth is 0 instead of starting from index 1.


Solutions

Simulation solution

Time Complexity: O(N)
Space Complexity: O(N) since we used extra extra space to store the output

References

Saturday, May 16, 2020

Google Code Jam 2020 Qualification Round: Vestigium Solution

Problem Statement

Problem

Vestigium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.

The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).

An N-by-N square matrix is a Latin square if each cell contains one of N different values, and no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the N values are the integers between 1 and N.

Given a matrix that contains only integers between 1 and N, we want to compute its trace and check whether it is a natural Latin square. To give some additional information, instead of simply telling us whether the matrix is a natural Latin square or not, please compute the number of rows and the number of columns that contain repeated values.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each starts with a line containing a single integer N: the size of the matrix to explore. Then, N lines follow. The i-th of these lines contains N integers Mi,1, Mi,2 ..., Mi,N. Mi,j is the integer in the i-th row and j-th column of the matrix.

Output

For each test case, output one line containing Case #x: k r c, where x is the test case number (starting from 1), k is the trace of the matrix, r is the number of rows of the matrix that contain repeated elements, and c is the number of columns of the matrix that contain repeated elements.

Limits

Test set 1 (Visible Verdict)

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ Mi,j  N, for all i, j.

Sample


Input
 

Output
 
3
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3

  
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2

  

In Sample Case #1, the input is a natural Latin square, which means no row or column has repeated elements. All four values in the main diagonal are 1, and so the trace (their sum) is 4.

In Sample Case #2, all rows and columns have repeated elements. Notice that each row or column with repeated elements is counted only once regardless of the number of elements that are repeated or how often they are repeated within the row or column. In addition, notice that some integers in the range 1 through N may be absent from the input.

In Sample Case #3, the leftmost and rightmost columns have repeated elements.


Problem link
 

Video Tutorial

You can find the detailed video tutorial here

 

Thought Process

The first problem in those Competitive Programming (CP) is generally easy. Just a simple simulation to count the sum of diagonal, and keep two sets to track duplication for row and col. This could also be a good 10 mins interview warm up questions just to see if candidate knows how to write code or not.

Solutions

Simulation solution

Time Complexity: O(N^2)
Space Complexity: O(N) since we used extra sets

References

Saturday, May 2, 2020

Google Kickstart 2019 Round A: Training Solution

Problem Statement 

Problem

As the football coach at your local school, you have been tasked with picking a team of exactly P students to represent your school. There are N students for you to pick from. The i-th student has a skill rating Si, which is a positive integer indicating how skilled they are.
You have decided that a team is fair if it has exactly P students on it and they all have the same skill rating. That way, everyone plays as a team. Initially, it might not be possible to pick a fair team, so you will give some of the students one-on-one coaching. It takes one hour of coaching to increase the skill rating of any student by 1.
The competition season is starting very soon (in fact, the first match has already started!), so you'd like to find the minimum number of hours of coaching you need to give before you are able to pick a fair team.

Input

The first line of the input gives the number of test cases, TT test cases follow. Each test case starts with a line containing the two integers N and P, the number of students and the number of students you need to pick, respectively. Then, another line follows containing N integers Si; the i-th of these is the skill of the i-th student.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of hours of coaching needed, before you can pick a fair team of P students.

Limits

Time limit: 15 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Si ≤ 10000, for all i.
2 ≤ P ≤ N.

Test set 1 (Visible)

2 ≤ N ≤ 1000.

Test set 2 (Hidden)

2 ≤ N ≤ 105.

Sample


Input

Output
3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

  
Case #1: 14
Case #2: 0
Case #3: 6

  
In Sample Case #1, you can spend a total of 6 hours training the first student and 8 hours training the second one. This gives the first, second and third students a skill level of 9. This is the minimum time you can spend, so the answer is 14.
In Sample Case #2, you can already pick a fair team (the first and second student) without having to do any coaching, so the answer is 0.
In Sample Case #3, P = N, so every student will be on your team. You have to spend 6 hours training the third student, so that they have a skill of 7, like everyone else. This is the minimum time you can spend, so the answer is 6.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

 

Thought Process

Start with brute force approach, get all different combos of picking P students over N. O(Cn^p), which is factorial.

Sort definitely comes into mind. After sort,we have to go through the sorted array once, assuming if the highest score element is picked, the rest elements should be close to it. We can keep a rolling sum to avoid computing the sum over and over again.

Solutions

Sort and rolling sum solution

Time Complexity: O(N)
Space Complexity: O(N)

References

Saturday, April 25, 2020

Google Kickstart 2020 Round A: Plates Solution

Problem Statement 

Problem

Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.
Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.
Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.

Input

The first line of the input gives the number of test cases, TT test cases follow. Each test case begins with a line containing the three integers NK and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.

Test set 1

1 ≤ N ≤ 3.

Test set 2

1 ≤ N ≤ 50.

Sample


Input

Output
2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

  
Case #1: 250
Case #2: 180

  
In Sample Case #1, Dr. Patel needs to pick P = 5 plates:
  • He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
  • He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In total, the sum of beauty values is 250.
In Sample Case #2, Dr. Patel needs to pick P = 3 plates:
  • He can pick the top 2 plates from the first stack (80 + 80 = 160).
  • He can pick no plates from the second stack.
  • He can pick the top plate from the third stack (20).
In total, the sum of beauty values is 180.
Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

 

 Thought Process

First thought is similar to merging multiple lists, this won't work since the lists are not sorted and we are not allowed to sort due to the order constraint.

Second thought is keep a max heap, and always merge the largest value from all the top elements in the lists. This is wrong since greedy won't work here. E.g., below if we want to pick 3 plates, using max heap will pick 2, 2, 2, instead of 1, 1, 100
2, 2, 2, 2, 2
1, 1, 100, 100, 100

Third thought seems we have to brute force, for all the combos of P, we check what's the maximum value. Quote from the analysis, it's exponential time complexity
For example, if N = 3 and for any given values of K and P, generate all possible triples (S1, S2, S3) such that S1+S2+S3 = P and 0 ≤ Si ≤ K. Note: Si is the number of plates picked from the i-th stack.
This can be done via recursion and the total time complexity is O(KN) which abides by the time limits.
Forth and final solution to optimize this is using dynamic programming. It's very common in those coding competitions.
Quote from the analysis

First, let's consider an intermediate state dp[i][j] which denotes the maximum sum that can be obtained using the first i stacks when we need to pick j plates in total.
Next, we iterate over the stacks and try to answer the question: What is the maximum sum if we had to pick j plates in total using the i stacks we've seen so far? This would give us dp[i][j]. However, we need to also decide, among those j plates, how many come from the i-th stack? i.e., Let's say we pick x plates from the i-th stack, then dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x]). Therefore, in order to pick j plates in total from i stacks, we can pick anywhere between [0, 1, ..., j] plates from the i-th stack and [j, j-1, ..., 0] plates from the previous i-1 stacks respectively. Also, we need to do this for all values of 1 ≤ j ≤ P.
The flow would look like:
for i [1, N]:
 for j [0, P]:
  dp[i][j] := 0
   for x [0, min(j, K)]:
    dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x])
If we observe closely, this is similar to the 0-1 Knapsack Problem with some added complexity. To conclude, the overall time complexity would be O(N*P*K).

Solutions

DP solution

Time Complexity: O(N*P*K)
Space Complexity: O(N*max(P, K))

References