allcoding1_official

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.

2Q Ans

def count_swaps(P): """ Calculates the number of swaps that maximize the longest path in the permutation graph. Args: P: The permutation of length N. Returns: The count of valid swaps modulo 10^9 + 7. """ N = len(P) mod = 10*9 + 7 # Find the cycles in the permutation cycles = [] visited = [False] * N for i in range(N): if not visited[i]: cycle = [] j = i while not visited[j]: visited[j] = True cycle.append(j) j = P[j] - 1 cycles.append(cycle) # Calculate the number of valid swaps count = 0 for i in range(len(cycles)): for j in range(i + 1, len(cycles)): count += len(cycles[i]) * len(cycles[j]) return count % mod # Example Usage P = [2, 3, 1, 5, 4, 7, 6] # Example from Case 3 result = count_swaps(P) print(result) # Output: 12 Explanation: 1. Finding Cycles: - The code uses a depth-first search (DFS) approach to identify cycles in the permutation graph. - The visited array keeps track of nodes already included in a cycle. - The cycles list stores the cycles as lists of node indices. 2. Counting Valid Swaps: - The key observation is that swapping an element from one cycle with an element from a different cycle will merge those two cycles. This will lead to a longer path in the graph. - The code iterates through the pairs of cycles and calculates the number of possible swaps between elements of those cycles. - For each pair of cycles, the number of swaps is the product of the number of elements in each cycle. 3. Modulo Operation: - The count % mod operation ensures that the final result is within the range of the required modulo value (10^9 + 7). Why This Works: - Longest Path: A permutation graph's longest path is determined by the longest cycle within the graph. - Merging Cycles: By swapping elements from different cycles, you effectively merge those cycles, potentially creating a longer cycle and hence a longer path. Example (Case 3): - P = [2, 3, 1, 5, 4, 7, 6] - Cycles: [[0, 1, 2], [3, 4, 5, 6]] - Swaps: Any element from the first cycle can be swapped with any element from the second cycle. This results in 3 * 4 = 12 valid swaps. Let me know if you have any further questions!

def count_swaps(P): """ Calculates the number of swaps that maximize the longest path in the permutation graph. Args: P: The permutation of length N. Returns: The count of valid swaps modulo 10^9 + 7. """ N = len(P) mod = 10*9 + 7 # Find the cycles in the permutation cycles = [] visited = [False] * N for i in range(N): if not visited[i]: cycle = [] j = i while not visited[j]: visited[j] = True cycle.append(j) j = P[j] - 1 cycles.append(cycle) # Calculate the number of valid swaps count = 0 for i in range(len(cycles)): for j in range(i + 1, len(cycles)): count += len(cycles[i]) * len(cycles[j]) return count % mod # Example Usage P = [2, 3, 1, 5, 4, 7, 6] # Example from Case 3 result = count_swaps(P) print(result) # Output: 12

2Q) You are given a permutation P of length N. This permutation represents a graph of N nodes where for each node i from 1 to N there is an ongoing edge from that node to node P[i]. A permutation is an array of length N, consisting of each of the integers from 1 to N in some order. The longest path in the graph is the path that satisfies the following conditions: تھا •⁠ ⁠It starts at some node U and ends at some node V. It visits each node no more than once. •⁠ ⁠Among all the possible paths, it's the longest one. Find the total number of possible pairs of indices of the permutation (i, j), such that: •⁠ ⁠If P[i] and P[j] are swapped, then the resulting graph has the maximum possible longest path among all the possible swaps. Since the answer is very large, print it modulo 109+7. Input Format The first line contains an integer, N, denoting the number of elements in P. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing P[i]. Sample Test Cases Case 1 Input: 3 1 2 3 Output: 3 Explanation: Given N 3, P= [1, 2, 3]. Here, if we swap "P[1]" and "P[2]" we will get P = [2, 1, 3]", node "1" can go to node "2" and we can consider that the longest path, and also node "2" can go to node "1", we also can generate the following two permutations: Case 2 Input: 6 2 3 1 S 6 4 Output: 9 Explanation: Given N 6, P [2, 3, 1, 5, 6, 4]. Here, we have two cycles, the nodes in the first cycle are "[1, 2, 3]" and the nodes in the second cycle are "[4, 5, 6]". We can show that if we swap any of the first three elements in the permutation with any element from the last three elements, the cycles will be merged, so the answer is "339". Case 3 Input: 7 2 3 1 5 4 7 6 Output: 12 Explanation: Given N 7, P [2, 3, 1, 5, 4, 7, 6]. Here, if we swap any element from the first three elements with any element from the last four elements we'll get a longest path of length "6", and from that the number of swaps to obtain that length (the maximum possible reachable length of the graph) is "3 * 4 = 12".