Scaler Topics Fortnightly Contest - 12 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 12
Subsequence Game
Alice and Bob are playing yet another game. They are given a string A of size N which consists of only 'A's and 'B's. Alice's favorite character is 'A' and Bob's favorite character is 'B'. The game is played in turns and Alice goes first. Initially, the score of both players is 0. The rules of the game are as follows:
- The current player has to make a valid move. If the current player can't make a valid move the game ends.
- The current player has to choose a non-empty subsequence of string A which only consists of their favorite characters and remove them from the string. The score of the current player is incremented by the number of favorite characters of the opponent.
- The rest of the string is concatenated and the other player goes for their move.
The winner of the game is the person with the maximum score. Return 1 if Alice can win otherwise return 0, in a game where both players plays optimally, where Alice tries to win and Bob tries to end the game with a win or draw.
Problem Constraints
Input Format
- First argument A, is a string.
Output Format
- Return a single integer.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: The moves are as follows: 1 -> Alice picks subsequence [1] string becomes = "B" Alice score = 1 2 -> Bob picks subsequence [1] string becomes = "" Bob score = 0 3 -> Alice can't choose any subsequence, hence game ends.
Alice score > Bob score, so Alice wins.
Explanation 2: The moves are as follows: 1 -> Alice can't choose any subsequence, hence game ends. Alice score = Bob score = 0
Hint
- Do we really need to consider all possible moves? Can count of 'A's and 'B's help?
Complete Solution
MEX Subarray
Given an array of integers, A. Return the number of subarrays with non-zero MEX. MEX is defined as the smallest non-negative integer not present in an array.
Problem Constraints
Input Format
- The first and only argument is an integer array A.
Output Format
- Return an integer.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: Subarray [0] = 1, [0, 1] = 2, [0, 1, 2] = 3 have non-zero MEX.
Explanation 2: All the subarray's have positive MEX.
Hint
- Which subarrays will have zero MEX?
- How can we find them?
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Similar Subarray
Let's define two arrays to be similar if they are of the same size and on sorting both the array have the same element in the corresponding index. Given two integer arrays, A of size N and B of size M. Find the count of tuple (i,j,k,l) such that subarray A[i...j] and subarray B[k...l] are similar.
Since this number can be large, return the value mod .
Problem Constraints
Input Format
- First argument contains an integer array A.
- Second argument contains an integer array B.
Output Format
- Return an integer denoting the answer.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: first tuple is (2,2,2,2): [3] and [3] are similar second tuple is (3,3,1,1): [2] and [2] are similar third tuple is (2,3,1,2): [3,2] and [2,3] are similar
Explanation 2: There are no valid tuples.
Turn Learning into Career Growth
Hint
- Note that Brute force of O(N^4) can be reduced to O(N^3) by considering the fact that only tuple with property j-i = l-k will be counted.
- Can you optimise it further?
Complete Solution
Edge Path
You are playing a special game on an undirected weighted connected graph without multiple edges. The graph has A nodes and its edges are represented by the matrix B, such that there is an edge between node B[i][1] and B[i][2] of weight B[i][3]. You are initially at node 1, and you have to reach node A, by traveling through edges. You can make two types of moves:
- Go from node u to node v, such that there is an edge between u and v, and add the corresponding weight of the edge to your cost.
- Make a special move from node u to node v and add to your cost. A special move from u to v exists if there are k nodes a1, a2 ..... ak (each node may or may not be unique), such that , and there exist an edge between pairs (u, a1), (a1, a2) ........ (ak - 1, ak) and (ak, v).
Return the minimum cost incurred to reach node A.
Problem Constraints
Input Format
- First argument A, is an integer.
- Second argument B is a matrix of integers.
- Third argumend C, is an array of integers.
- Fourth argument D, is an array of integers.
Output Format
- Return a single value, denoting the minimum cost to reach node A from node 1.
Example
Example Input
Input 1:
Example Input
Input 2:
Example Output
Output 1:
Example Output
Output 2:
Example Explanation
Explanation 1: Optimal path:
- Special move: 1 -> 2 -> 3 Total cost = C[1] + C[3] = 0 There may exist other optimal paths as well.
Example Explanation
Explanation 2: Optimal path:
- Special move: 1 -> 4 -> 2 -> 3 -> 2 cost = C[1] + C[2] = 0
- Normal move: 2 -> 4 cost = 1 Total cost = 0 + 1 = 1 There may exist other optimal paths as well.
Hint
- We are required to find shortest cost path. Can you think of modifying any shortest path algorithm? Dijkstra?
