Editorial for problem T29 and T30 of Innerve summer code challenge.

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)

Explanation :

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

Explanation :

  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;">[1] : 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;">[2] : I am only responsible for the problem T28 , T29 and T30 , please ask the related query .
  </b>

  <b style="color:red;">[3] : 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;">[4] : 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>
3 Likes

@dk30390 what is the time complexity of the solution using the bitsets?

I managed to solve T29 using square root decomposition and binary search. Just sharing that here, because it felt good after solving it lol.

My solution

Is that the intended solution for T30? I know bitsets are fast, but this feels too fast.

@abdullah768 “but this feels too fast” , that’s why i set the constraints too high , also T30 was the last problem of the problem-set so i make the bitset soln intended(as it was less explored before the contest).
i am not sure that this is implemented in most of the languages so it was a little tougher for them because they had to design their own hash-function which support basic bitwise operations.

“C++ standard doesn’t specify how bitset is internally implemented. However, most implementations (or, more precisely, at least the gcc implementation) are very efficient and will perform things like comparisons and bit counting as fast as they can.”

source credit : thecodingforums.com

That’s why i don’t mentioned the complexity of the code.
But we can fairly say that it must be something like O(K) where K is
some constant factor but slower than O(1).
Also if someone have some better information about the complexity of bitset plz share.

ya it can be solved using sqrt decomposition + binary search , thanks for sharing ,but can u plz share some ideone link or something … as this link is blocked by the organiser of the contest.

Oh, I see. I’ve changed it to Ideone.