Editorial for T29 and T30.
Hello Fellow Programmers ,
Here is the editorial for the problem Skill Input (T29) and Chef and Market (T30).
Skill Input(T29) :Problem Link : Practice Link
Intended Solution : Merge Sort Tree
Note : It can be solve using any of the combination (Segment Tree , Merge Sort Tree , Persistent Segment Tree + Binary Search …etc)
You can Make a simple observation that the function f(x) = 109 - x is a decreasing function and will follow the property [f(x1) > f(x2) where (x1 < x2)] and hence we need to keep the range of element in sorted order to find the f(x)closest to K . For keeping the range of element in sorted order we can simply use Merge sort Tree.
Complexity : O((N+Q)*log N)
Alternate Solution : We can solve it using segment tree ,
visit this Link , we can use the same algorithm with minor changes.
Chef and Market(T30) :Problem Link : Practice Link
Intended Solution : Bitwise Operations
Someone might think to solve this Problem using (Inclusion Exclusion + Fenwick tree) / using (Inclusion Exclusion + Ordered set) or using (mobius inversion after hashing the element of set with a square free number)....umm....okk let's look at the constraints once again , did you notice something , yes i am talking about the complexity , it will take O(2<sup>k</sup> * Q * log N) where k is the size of set[can be <b>10</b>],Q is the number of Query[can be <b>10000</b>] and N is the number of shops[can be <b>100000</b>], and it will fail to pass the time limit. So how to solve this problem ..... okay ,let me explain it, We can approach this problem using some bitwise operations,we can maintain a bitset of size(<b>N</b>) for every possible item of the set.we will be storing the presence of any item at the index of the shops by setting it to <b>1</b>, where <b>1</b> represents that this item is present at the respective index, and for type <b>2</b> queries , we are interested in finding the number of index in range[<b>L</b>,<b>R</b>] where the intersection of a set of items with the existing set is null.
For doing this we can perform the bitwise or operation among the items of the chef’s set and simply count the number of zero’s in the range[L,R] , after performing bitwise or operation the resulting bitset will be showing the status of the intersection,if the status is 0 for any index in range[L,R] then it is showing that the intersection between the chef’s set and existing set at that index is null, and we are exactly looking for it.
For type <b>1</b> query we can simply update the sign of the items for existing set of items with the new set of items. <b>Solution : </b><a href="https://www.codechef.com/viewsolution/19347403" style="color:red;">Link</a> <b>Similar problem :</b> <a href="https://www.codechef.com/problems/GCDCNT" style="color:red;">Link</a> and <a href="https://www.codechef.com/viewsolution/19347908" style="color:red;">solution</a> you can also solve <a href="https://www.codechef.com/problems/CHANOQ">this</a> problem using bitwise operations. <hr> <h4>Note :</h4> <b style="color:green;"> : It might be very confusing while reading the editorial for problem T30,I will suggest you to go through the solution and try to traverse it , it is easly traceable and easy to understand.I hope it will help you for the better understanding of the editorial. </b> <b style="color:red;"> : I am only responsible for the problem T28 , T29 and T30 , please ask the related query . </b> <b style="color:red;"> : This is my first editorial so please give your valuable feedback in the comment so that i can improve myself for the future events. </b> <b style="color:green;"> : Please share your approach for the problems and help the community.It will help us to learn some more ways to attack the similar problems. </b>