#1. STRING MATCHING
PROBLEM LINK
Editorialist- Abhishek Pandey
PROBLEM DESCRIPTION:
Given a main string, you need to find if there are strings with atleast K matches in the input strings. While matching, we only care for presence of character, and not of the ordering etc. If no such strings are present, we simply print a "No" , else we have to print "Yes" and the corresponding strings in order of input.
QUICK EXPLANATION:
Since we have to print in order of input, its better to either check the strings while taking input or store the strings in an array and then check of matching. For matching, we use the concept of frequency arrays since only the presence of character matters.
EXPLANATION:
This was the cakewalk problem but we decided to make it lean a bit on implementation side. Cakewalk shouldn’t mean an effortless AC after all.
We preferred to check for matching while taking input string by string, and if a string has at least K matches, we add it to the array (or any other appropriate data structure like vector etc.). To check for matching, note that only presence of characters matter. This allows us to use the frequency array concept. Since the strings are all in lowercase, then they will only have letters ‘a’ to ‘z’, i.e. 26 such alphabets.
Now, we declare 2 frequency arrays, one for main string and other for query string. We first iterate through main string and store the frequency of each alphabet in frequency[s[i]-'a'] (Read: Character at i’th index of string -‘a’. Using concepts of char to int conversion, we can see that s[i]-‘a’ evaluates to a value between [0,25] , each of which corresponds to an alphabet (eg- 0=‘a’, 1=‘b’…25=‘z’).
The implementation goes on like this-
for(i=0;i<s.length();i++)
{
frequency[s[i]-'a']+=1;
}
We store frequency of all alphabets/characters in both strings in this manner. Now all thats left is to iterate through all 26 values of our frequency array and check for matching. Since only presence is required, we check if frequency of that character in both string is more than 0.
for(i=0;i<26;i++)
{
if(frequencyMain[i]==frequencyQuery[i])
{
matchFound++;
}
}
if(matchFound>=k)
{
..//Add string to array.
}
Now all thats left is keeping a count of how many strings you have stored in answer array (i.e. strings which matched >=K) and printing them in correct order. Please refer to author and tester’s solution for implementation details
SOLUTIONS:
Tester’s Solution
Editorialist’s Solution
#2 DISPARITY CHECK:
PROBLEM LINK:
Editorialist- Mahir Shah
PROBLEM DESCRIPTION:
Given an array, we had to answer two type of queries. Type 1 query increased an element by some value. Type 2 wanted sum of all odd or even numbers depending on pairty.
EXPLANATION:
We can solve this question using fenwick tree.
Maintain two fenwick trees -one for even elements and one for odd elements for range sum query.
In the even fenwick tree insert all even elements according to their position in array and same for the odd one.
Thus we can answer the queries of type 2 by using range sum query(logN complexity) in the appropriate fenwick tree according to parity.
For queries of type 1 we consider two cases-
1.The value given is even.Then the parity of the element at the specified position does not change and we simply update the appropriate fenwick tree and the original array.
2.The value given is odd then the parity of the element changes.For this we remove the element from the fenwick tree which it belonged to and increase the array element by given value and insert this element in the appropriate(opposite from initial) fenwick tree according to its position.
Thus the complexity of the program is QlogN.
REFERENCE CODE:
#3. THE BIRTHDAY PARTY:
PROBLEM LINK
Contest
Practice
Editorialist- Asish Gupta
DIFFICULTY:
MEDIUM
PROBLEM:
We have to calculate the minimum time after which every kid will have the ball he originally had at the beginning of game.
EXPLANATION:
A key observation here is that there will always be a moment in time when every kid has the ball which he originally had at the beginning of the game.
We find the length of the time-period required for this to be achieved for each person individually. That is, find the length of all the cycles.
The minimum total time needed is the LCM of these lengths.
To find the LCM, we can prime-factorise the lengths, store the maximum power of all the prime numbers that appear, and calculate the LCM from there.
TESTER’S SOLUTION
#4. OFFICE PLAY:
PROBLEM LINK:
Editorialist- Mahir Shah, Ashish Gupta
PROBLEM:
Find the K-th ancestor of a node u and then find the closest node from the K-th ancestor which is of the same department as u.
EXPLANATION:
Consider the type of departments as colors of the nodes.
This question can be solved using lca + persistent segment tree too.
You create a persistent segment tree in dfs order of colors where the leaf nodes represent colors and will have the values of last node encountered of that color while travelling in dfs order to that node.Note intially the leaf nodes will contain -1.And initial build complexity is MlogM
For each node there will be one update which is setting the value of the leaf which corresponds to node’s color to to the value of node.So NlogM time complexity and NlogM space complexity will be required for this.
So for answering the queries we find the v’th ancestor in log N complexity and then find the value in the required leaf node(depending on the color of query node) of the persistent segment tree at the v’th ancestor in log M complexity.
Therfore total complexity for answering the queries is Q(log N+log M).
ANOTHER APPROACH:
An alternative way of accomplishing the task is to:
-
Build the LCA Table where we store the department-wise parent of each node.
-
Store the levels of each node with a simple DFS
-
Binary search on the department-wise parent, with lo=0 and hi = log2(N). For checking whether the current node satisfies the given condition, we check if the level difference of current node and u is >=v. If yes, lo = mid, or hi = mid - 1.
#5. ARCADEYA BAE
We regret to inform you that the editorial is delayed. The editorialist has suffered shoulder injury while going back home and hence, is unable to write it up currently. We will update it as soon as he recovers. Thanks for your patience! 
