allcoding1_official

11Q) Ans

11Q) Bob was walking his dog in the village. Unfortunately he got lost in an orange grove and wants to reach the exit. The grove can be represented as a 2D grid consisting of N rows and M columns such that • The rows are number from 1 to N from top to down. The columns are numbered from 1 to M from left to right. Each cell (i, j) of the grid has either of the following • An orange tree with A[i][j] oranges. • An infinite number of lanterns. It is given that cells with lanterns will be have value 0. the beginning, Bob is at cell (1, 1) and he wants to reach the exit at cell (N, M). He can move either right or down in the grove. As Bob reaches a cell (i, j), he will eat some amount of oranges from the tree in that cell (at most A[i][j]). In case this cell has lanterns, he will not be able to eat any oranges. Bob wants to mark the path he's following with lanterns, so when he reaches a cell he will send his dog to some cell which has lanterns then the dog will pick up a lantern and comeback to Bob to put the lantern in that cell The dog can move up, down, left and right in the grid, and the dog travels 1 kilo meter when moving from one cell to another. When Bob moves from one cell to another, his dog will follow him as well. Bob defines the profit of a path that leads him to the exit as the difference between the total amount of oranges he could eat along that path and theof oranges he could eat along that path and the total distance in kilo meters his dog traveled along that path Find the maximum profit of a path that leads Bob to the exit of the grove The distance the dog travels with Bob when Bob moves from cell to another is not included (only the distance of getting lanterns is calculated for the dog) • Bob will put lanterns in every cell of the path, including the starting and ending cells. He can also move to a cell which has lanterns, but this will not affect the amount of oranges. It is guaranteed that there is at least one cell with lanterns. Input Format The first line contains an integer, N, denoting the number of rows in Grid. The next line contains an integer, M, denoting the number of columns in Grid. Each line i of the N subsequent lines (where 0≤i< N) contains M space separated integers each describing the row Grid[i]. Constraints 1 <= N <= 10^5 1 <= M <= 10^5 0 <= Grid[i][j] <= 10^9 Sample Test Cases Case 1 Input: 1 1 0 Output: 0 Explanation: N=1, M-1, Grid=0 Bob is already at the ending cell, bob will not eat oranges and the dog will not travel anywhere since this cell has lanterns. So the answer is 0. Output: 2 Explanation: N-2, M-2, Grid-[[3,0], [5,2]] In the beginning, Bob will eat 3 oranges at cell (1, 1) then he will send his dog to cell (1, 2) to get a lantern, the dog will travel 2kms back and forth. Then Bob will move with dog to cell (2, 1), eat 5 oranges and send his dog to cell (1, 2) again, the dog will travel 4kms (2kms for going and 2 for returning). Finally Bob will move with the dog to the exit cell (2, 2), eat 2 oranges and send his dog to cell (1, 2), the dog will travel 2kms to get the lantern. The final answer is 3-2 + 5-4 + 2-2 = 2. Output: 3 Explanation: N-3, M-3, Grid=[[5,4,0], [1,1,1], [6,5,0]] Bob will take the path (1, 1), (1, 2), (2, 2), (3, 2), (3, 3) with profit: 5-4 + 4-2 + 1-4 + 5-2 +0 = 3 In cells (1, 1), (1, 2) Bob will send his dog to cell (1, 3) to get the lanterns. In the remaining cells he will send the dog to cell (3, 3).

10Q) Ans

10Q) You are given a tree with N nodes numbered from 1 to N You are also given an array A of length N where A[i] denotes the value of node 1. It is given that the MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set. For instance: The MEX of "(2, 1)" is "0", because "0" does not belong to the set. The MEX of "(3, 1, 0)" is "2", because "0" and "1" belong to the set, but "2" does not. Let's define the beauty of a tree as the MEX of the values assigned to the nodes of that tree. Case 1 Your need to choose exactly one edge from the given tree and then divide the tree into two parts (two trees) such that The sum of the beauties of the two resulting trees is the maximum possible. Return this sum. Input Format The first line contains an integer, N, denoting the number of elements in A. The next line contains an integer, M, denoting the number of rows in edges. The next line contains an integer, C, denoting the number of columns in edges. Each line i of the M subsequent lines (where 0 <= i < M) contains C space separated integers each describing the row edges[i]. Each line i of the N subsequent lines. (where 1 <= i \le N) contains an integer describing A[i]. Constraints 2 <= N <= 10 ^ 6 N - 1 <= M <= N - 1 2 <= C <= 2 1 <= edges[i][j] <= N 0<= A[i]<= N P Sample Test Cases Case 1 Questions Input: 3 2 2 12 13 0 1 2 Output: 2 Explanation: Here, N-3, M-2, C-2, edges-[[1,2], [1,3]] and A- [0, 1, 2] In this sample, if we cut the edge between node "1" and node "3", one of the resulting subtree will has a beauty of "2" and the other a beauty zero. So the answer is "2 + 0 = 2". Case 2 Input: 4 3 2 12 13 24 0 2 1 0 Case 3 Input: 6 5 2 12 23 34 45 56 1 0 2 021 1 Output: 6 Explanation: Here, N=6, M=5, C=2, edges=[[1,2], [2,3], [3,4], [4,5], [5,6]] and A=[1,, 2, 0, 2, 1] In this sample, if we cut the edge between node "3" and, node "4", one of the resulting subtree will has a beauty of "3" and the other a beauty of "3". So, the answer is "3 + 3 = 6". Output: 4 Explanation: Here, N = 4 , M = 3 , C = 2 , edges=[[1,2], [1,3], [2, 4] ] and A = [0, 2, 1, 0] In this sample, if we cut the edge between node "2" and node "4", one of the resulting subtree will has a beauty of "3" and the other a beauty of "1". So, the answer is 3 + 1 =4^ prime prime .

9Q) Ans

9Q) There is a flower shop contains n flowers in a row each cover can be followed with one of the following colours that will red green white or yellow You are given a string S of length N where S[i] is either "R", "G", "B", or "Y", representing the color of the ith flower. Each flower has a beauty associated with it, which is given in an array flower. B of length N, where B[i] is the beauty of the ith A range of flowers [L, R] is called good if the following is true: • The number of red flowers in that range equals the number of green flowers. • The number of blue flowers equals the number of yellow flowers. Your task is to choose zero or more non-intersecting good ranges of flowers such that the sum of the beauty of all the flowers in all the ranges is as maximum as possible. The first line contains an integer, N, denoting the number of elements in B. The next line contains a string, S, denoting the given string. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing b[j] 1 <= N <= 10 ^ 5 N <= len(S) <= N 1 <= B[i] <= 10 ^ 4 Case 1 Input 4 RGBY 1 1 1 1 Output: 4 Given N = 4, S = "RGBY", B = [1, 1, 1, 1]. In this sample sum equals to 4. we choose the interval [1, 4] with beauty Sum equals to 4 Input 5 BYRRG 2 2 2 2 2 Output: 8 Explanation Given N = 5, S = "BYRRG", B = [2, 2, 2, 2, 2]. In this sample we will choose two intervals , 5]. With sum beauty equals to 4 in each interval. [1,2], [4 ,5] With sum beauty equals to 4 in each interval Input: 12 13 BYRYRGBY 4 2 5 14 15 16 17 10 4 2 1 9 18 19 20 21 Output: 22 23 23 Explanation: Given N = 8, S = "BYRYRGBY", B = [4, 2, 5, 10, 4, 2, 1, 9]. Case 1 In this sample the intervals are [1, 2], [4,7] Input The final beauty sum is 6 + 17 = 23. import java.io.*; import java.util.*; import java.lang.Math; public class Solution { public static int GetMaximumSum(int N, String S, List<Integer> B) { // Write your code here } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = Integer.parseInt(scan.nextLine().trim()); String S = scan.nextLine(); List<Integer> B = new ArrayList<>(N); for(int j=0; j<N; j++) { B.add(Integer.parseInt(scan.nextLine().trim())); } int result = GetMaximumSum (N, S, B); System.out.println(result); } }

Send ur Questions on group

8Q) You are given an integer N and a number K. Let's defind the cost of a string consisting of lowercase latin letters as the cyclic distance between any two consecutive characters in string For example the cost of the string "abzv" can be calculated as follow: MinimumCyclicDistance(a,b)+ MinimumCyclicDistance(b,z)+ MinimumCyclicDistance(z,v)= 1+2+4=7 It is given that two strings of length N are different if their character differ at least one position from 1 to N Find the number of the distinct string S which satisfies the following two conditions: The length of S is exactly equal to N The code of S is divisible by K Since the answer can be very large print it modulo 10 to the power 9 + 7 Input format The first line contains an integer N denoting the length of the requires string. The next line contains an integer K denoting the given number K Constraints 2<=N <= 10^5 1<=K<=100 Sample test case Case 1 Input 2 2 Output 338 Explanation: In this case, one of the possible strings is "ac", also "ce". We can show that there Re exactly*338" strings that satisfy the conditions So the answer is 338. Case 2; Input: 3 1 Output 17576 Explanation: Given N =3, K= 1 In this sample, since every number is divisible by "1", then any string of length "3" is "26 * 26 * 26= 17576". Case 3: Input : 2 13 Output 52 Explanation: In this case, one of the possible strings is"an", also "cp" We can show that there are exactly "52" strings that satisfy the conditions

7Q) Ans

7Q) you are given a string S with N characters a string T with M characters and an integer K you can perform the following operation on s atmost K times change a character at some index in the string to any other character find the count of maximum number of subsegments in the S that have T as subsequence after applying the operation Sample input 3 1 1 abc d sample output 1 explanation Given N=3 M=1 K=1 S=abc T=d we can change s[1] to d and the ans will be 1 give a code such that output for the given input is 1 sample input 2 3 1 1 abc b sample output 2 2

6Q ans

6Q) You are given an integer N and a number Let's define the cost of a string consisting of lowercase Latin letters as the cyelle distance between any two consecutive characters in that string, Vadlaa = Questions For example, the cost of the string "abzy" can be calculated as follows: Minimum Cyclic Distance(a, b) + Minimum Cyclic Distance(b, z) + Minimum CyclicDistance(z, v) = 1 + 2 + 4 = 7. It is given that two strings of length N are different if their characters differ in at least one position from 1 to N. Find the number of the distinct strings $ which satisfies the following two conditions • The length of S is exactly equal to N. • The cost of S is divisible by • The length of S is exactly equal to N. The cost of S is divisible by K. vadlaa Since the answer can be very large, print it modulo 109+7. Input Format The first line contains an N. denoting integ N the length of the required string. The next line contains an integer, K. denoting the given number K. Error Constraints 2 <= N <= 10^5 .1 <= K <= 100 Sample Test Cases Case 1 Input: 2 2 Output: 338 Explanation: Given N= 2, K=2 In this case, one of the possible strings is "ac", also "ce". We can show that there are exactly "338" strings that satisfy the conditions. So, answer is 338.

5Q) string trimmetris Int get ans // write your code here 18 11 J 13 14 16 30 int meint) ( Insyrm with stateles cin.tiele); cout 10 (8) string inutise Test case HandsOnSquares Beauty Summary Questions You me quen a square grid A of You want to choose two non intersecting apuate sob-grids with no common row or column such that the sum of both sub grids is maximized. Return the maximum possible sum Input Format The next line contains an integer. 4. denoting the number of columns in A Each line i of the N subsequent lines (where N) contains N space separated integers each describing the row Ali Constraints 1N500 -100 <= A[i][j] <= 100

4Q Ans

import java.util.*; import java.lang.*; class Solution { public int coveredRanges(int[] A, int[][] Queries) { int N = A.length; int Q = Queries.length; int MOD = 1000000007; // Create a map to store the last occurrence of each element in A Map<Integer, Integer> lastOccurrence = new HashMap<>(); for (int i = 0; i < N; i++) { lastOccurrence.put(A[i], i); } // Calculate the number of covered ranges for each query long sum = 0; for (int[] query : Queries) { int L = query[0] - 1; int R = query[1] - 1; // Initialize the number of covered ranges for this query int coveredRanges = 0; // Iterate through the elements in the subarray for (int i = L; i <= R; i++) { // If the last occurrence of the current element is within the subarray if (lastOccurrence.get(A[i]) <= R) { // Increment the number of covered ranges coveredRanges++; // Skip to the last occurrence of this element i = lastOccurrence.get(A[i]); } } // Add the number of covered ranges to the sum sum = (sum + coveredRanges) % MOD; } // Return the sum of all covered ranges modulo 109+7 return (int) sum; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Read the number of elements in A int N = scanner.nextInt(); // Read the elements of A int[] A = new int[N]; for (int i = 0; i < N; i++) { A[i] = scanner.nextInt(); } // Read the number of queries int Q = scanner.nextInt(); // Read the number of columns in Queries int two = scanner.nextInt(); // Read the queries int[][] Queries = new int[Q][two]; for (int i = 0; i < Q; i++) { for (int j = 0; j < two; j++) { Queries[i][j] = scanner.nextInt(); } } // Create an instance of the Solution class Solution solution = new Solution(); // Call the coveredRanges method and print the result System.out.println(solution.coveredRanges(A, Queries)); } }

4Q) Handson 1: Array Covered Ranges You are given an array A of length N. It is given that the number of covered ranges in the subarray from L to R is defined as the minimum number of ranges, such that the following is true • All the elements of each range appear as elements of the subarray. • Each element of the subarray appears in exactly one range where 0 < L, R < N+1. You have to process Q queries given in a 2D array Queries, where each query contains two integers L and R. For each query, you have to find the number of covered ranges in the subarray from L to R in A. Find the sum of answers to all queries. Since the answer can be very large, return it modulo 109+7 Input Format The first line contains an integer, N, denoting the number of elements in A. Each line i of the N subsequent lines (where 0 ≤ i< N) contains an integer describing Ali) The next line contains an integer, Q, denoting the number of rows in queries. The next line contains an integer, two, denoting the number of columns in queries. Each line i of the Q subsequent lines (where 0 ≤ i < Q) contains two space separated integers each describing the row queries[i]. Constraints 1 <= N <= 10 ^ 6 1 <= A[i] <= 10 ^ 6 1 <= Q <= 10 ^ 6 2 <= two <= 2 1 <= queries[i][j] <= N Sample Test Cases Case 1 Input: 1 1 1 2 11 P Output: 1 Explanation: Given N = 1 A = [1] Q = 1 two = 2, Queries - [[1, 1]] . The number of covered ranges in (1) is 1 (the range is [1, 1]). Hence, the sum of answer of queries is equal to 1. Case 2 Input: 2 1 3 2 2 11 12 Output: 3 Explanation: Given N = 2 A = [1, 3] Q = 2 two 2, Queries [[1, 1], [1, 2]]. The number of covered ranges in (1) is 1 in range [1, 1], while the number of covered ranges in (1, 3} is 2 in range [1, 2]. Hence, the sum of answer of queries is equal to 3. Case 3 Input: 2 1 2 2 2 11 12 Output: 2 Explanation: Given N = 2 A = [1, 2] Q = 2 two. 2, Queries [ [1, 1] [1, 2]]. The number of covered ranges in both (1) and (1, 2} is 1 in range [1, 1] and [1, 2] respectively. Hence, the sum of answer of queries is equal to 2.

3Q Ans

3Q) General Ali has devised a strategic game to reduce an enemy army of N soldiers to just 1sdier The game allows the following three types of moves: 1. Reduce the enemy army by 1 soldier. 2. Reduce the enemy army by half of its current soldiers, rounding down to the nearest integer 3. Reduce the enemy army by two-thirds of its current soldiers, rounding down to the nearest integer Each move must ensure that the resulting number of soldiers is an integer Find the minimum number of moves required to reduce enemy army to just 1 soldier Input Format The first line contains an integer, N, denoting the number of enemy soldiers. Constraints 1 <= N <= 10^9 Sample Test Cases Case 1 Input: 5 Output: 3 Explanation: Given N 5. Move 1: Reduce by 1 soldier (5 -> 4) Move 2: Reduce by half (4-> 2) Move 3: Reduce by half (21) Hence, the answer for this case is equal to 3. Case 2 Input: 1 Output: e Explanation: Given N 1. There is only 1 soldier already, so to moves are required to reduce the umeny soldiers to Therefore, the minimum number of noves needed is 8.