Round G 2020 Google Kick Start Combination Lock, Maximum Coins and Kick_Start Problem | Java

Kick_Start

Ksenia is very fond of reading so she kicks off each day by reading a fragment from her favourite book before starting with the rest of her morning routine. A fragment is simply a substring of the text. Ksenia is somewhat superstitious and believes that her day will be lucky if the fragment she reads starts with the string KICK, then goes on with 0 or more characters, and eventually ends with the string START, even if the overall fragment makes little sense.

Given the text of the book, count the number of different lucky fragments that Ksenia can read before the book gets old and she needs to buy another one. Two fragments are considered to be different if they start or end at different positions in the text, even if the fragments read the same. Also note that different lucky fragments may overlap.

Input

The first line of the input gives the number of test cases T. T lines follow, each containing a single string S consisting of upper case English letters only.

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 number of different lucky fragments in the text of this test case.

There are three lucky fragments in the first test case, namely, KICKSTARTPROBLEMNAMEDKICKSTART and two occurrences of KICKSTART. The text in the second test case has no lucky fragments at all.

Java Code

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t =sc.nextInt(); for(int i=0; i<t; i++) { String s = sc.next(); int count =0; int favourite =0; for(int j=0; j<s.length(); j++) { try { if(s.charAt(j)=='K' && s.charAt(j+1)=='I' && s.charAt(j+2)=='C' && s.charAt(j+3) == 'K') { count ++; } else if(s.charAt(j)=='S' && s.charAt(j+1)=='T' && s.charAt(j+2)=='A' && s.charAt(j+3) == 'R' && s.charAt(j+2)=='A' && s.charAt(j+4) == 'T') { favourite += count; } } catch(Exception e) { break; } } System.out.printf("Case #%d: %d\n",i+1,favourite); } } }

Maximum Coins

Mike has a square matrix with N rows and N columns. Cell (i,j) denotes the cell present at row i and column j. Cell (1,1) denotes the top left corner of the matrix. Each cell has some amount of coins associated with it and Mike can collect them only if he visits that cell. Ci,j represents the number of coins in cell with row i and column j. From a cell (i,j), Mike can decide to go to cell (i+1,j+1) or cell (i-1,j-1), as long as the cell lies within the boundaries of the matrix and has not been visited yet. He can choose to start the journey from any cell and choose to stop at any point. Mike wants to maximize the number of coins he can collect. Please help him determine the maximum number of coins he can collect.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The next N lines contain N integers each. The j-th integer in the i-th line represents the number of coins Ci,j in cell (i,j).

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 number of coins Mike can collect.

In Sample Case #1, the maximum number of coins collected can be 14, if Mike follows this path: (1,1) -> (2,2) -> (3,3)

In Sample Case #2, the maximum number of coins collected can be 9, if Mike follows this path: (2,3) -> (3,4).

Java Code

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i=0; i<t; i++) { int n = sc.nextInt(); int a[][] = new int[n][n]; for(int j=0; j<n; j++) { for(int k=0; k<n; k++) { a[j][k] = sc.nextInt(); } } System.out.printf("Case #%d: %d\n",i+1,max(a,n)); } } private static long max(int[][] a, int n) { long temp_left=0; for(int i=0; i<n; i++) { int temp = i; long temp_add=0; for(int j=0; j<n-i; j++) { temp_add += a[temp][j]; temp++; } if(temp_left < temp_add) temp_left = temp_add; } long temp_right=0; for(int i=0; i<n; i++) { int temp = i; long temp_add=0; for(int j=0; j<n-i; j++) { temp_add += a[j][temp]; temp++; } if(temp_right < temp_add) temp_right = temp_add; } return Math.max(temp_left, temp_right); } }

Combination Lock

A combination lock has W wheels, each of which has the integer values 1 through N on it, in ascending order.

At any moment, each wheel shows a specific value on it. Xi is the initial value shown on the i-th wheel.

To save time, every house owner always takes their trash out to the trash bin that is closest to their houses. If there are two trash bins that are both the closest to a house, then the house owner can walk to any of them.

You can use a single move to change a wheel from showing the value X to showing either X+1 or X-1, wrapping around between 1 and N. For example, if a wheel currently shows the value 1, in one move you can change its value to 2 or N.

Given all wheels' initial values, what is the minimum number of moves to get all wheels to show the same value?

Input

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case contains the two integers W and N.

The second line contains W integers. The i-th integer is Xi.

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 moves to get all wheels to show the same value.

In Sample Case #1, the best solution is to get all wheels to show value 3, which would take a total of 2 moves: the first wheel would move once (from value 2 to value 3), the second wheel would not move (it already shows value 3), and the third wheel would move once (from value 4 to value 3).

For reference, it would take 5 moves to get all wheels to show value 1, 3 moves to get all wheels to show value 2, 3 moves to get all wheels to show value 4, and 5 moves to get all wheels to show value 5.

In Sample Case #2, the best solutions are to get all wheels to show either value 1, 2, 9 or 10, which would take a total of 8 moves.

Java Code

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i=0; i<t; i++) { long w = sc.nextLong(); long n = sc.nextLong(); long a[] = new long[(int) (w)]; for(int j=0; j<w; j++ ) { a[j] = sc.nextLong(); } Arrays.sort(a); long c[] = new long[(int) (3*w)]; System.arraycopy(a, 0, c, 0, a.length); for(long j=0; j<w; j++) { c[(int) (j+w)] = c[(int) j]; c[(int) (j+w+w)] = c[(int) j]+n; c[(int) j]-=n; } long minscroll = Long.MAX_VALUE; long b[] = new long[(int) (3*w)]; b[0] = c[0]; for(long j=1; j<3*w; j++) { b[(int) j] = b[(int) (j-1)]+c[(int) j]; } for(long j=w; j<2*w; j++) { long k = j-(w+1)/2; long temp = (b[(int) (k+w)]-b[(int) (j-1)])- c[(int) j]*(k+w-(j-1)); temp += c[(int) j]*(j-1-k)-(b[(int) (j-1)]-b[(int) k]); minscroll = Math.min(minscroll, temp); } System.out.printf("Case #%d: %d\n",i+1,minscroll); } } }

Here is the link for Google KickStart Round F 2021 Trash Bins Problem.