Link: http://devskill.com/CodingProblems/ViewProblem/316

Problem Setter: Monikrishna Roy

In this problem, we have to find total number of distinct strings of length L having string S as suffix. Also given that Length L is greater than or equal to length of S ( |S| ).

So, Idea is to find total number of empty index where we can place characters, which will be equal to L-|S| and, in each of such indices, we have total options of 26 characters to insert. So, answer will be 26^(L-|S|) .

Problem B: What a problem!

Link: http://devskill.com/CodingProblems/ViewProblem/237

Problem Setter: Habibur Rahman

About problem: A square grid is given with integers, you have to print the integers in the grid as in the figure.

Solution Approach: Printing solutions one in Downward and another in upward direction. You have to change the Row and Column indicator when it finishes the boundary.

When you are in the downward direction, you have to increase both the row and column indicator by 1. And when in upward direction, you have to decrease both by 1.

Up to diagonal of the square, when you finish the downward direction, you have to increase the column by 1, and then print in upward direction. And when, upward direction finished you have to decrease the row by 1.

But after the diagonal, when downward finished, you have to decrease the row by 1 and when upward finished you have to increase the column by 1.

And finally you have to stop printing at row at 1 and column at n.

So, you will need (n*n) printing for each case and for T test case you will need O(T*n*n) complexity.

Problem C: Sanvi and chocolates

Link: http://devskill.com/CodingProblems/ViewProblem/318

Problem Setter: Bishal Gautam

In this problem, you are given the information that robot will provide some chocolates ( Ci ) to the Sanvi from day-1 to day-D sequentially. And, you have to answer several queries that "how many days does she need to collect total Yi amount of chocolates?".

If collection of Yi chocolates is impossible, you have to print -1.

There was also mentioned a warning in a problem that "Time limit is too tight".

Firstly, you may think of adding summation of chocolates from day 1 to day-D , and stopping when you get equal or greater amount of chocolates that was given on query. In worst case, this approach may go upto O(Q*D) . So, this will not get AC.

The next probable thinking that may come to several's mind is obviously binary search upon cumulative sum for D days.

But, this solution is also too tight to pass the limit. As in worst case this will be O( TC*D*logD*Const ), this will certainly leads to TLE.

The main aim of this problem was to make contestant familiarity with most efficient O(N) approach of two pointers and/or Offline processing .

As limit of Y is only 10^5, we may precalculate the values required days before processing queries. During summation of cumulative summation, you can be certain that to make all the values from ( Cumulative summation of previous index )+1 to ( Cumulative summation of current index ), we need current amount of days. i.e you can not make summation of (Current cummulative sum)+1 using current amount of days.

If we denote cumulative sum of choclates of ith day as Csum(i) , then

- Values from 1 to Csum(1) require 1 day

- Values from Csum(1)+1 to Csum(2) require 2 days

- Values from Csum(2)+1 to Csum(3) require 3 days

So, we may precalculate these values by iterating upto 10^5. And, should break the loop if it crosses 10^5, as there wont be any Y greater than 10^5.

Problem D: Shan and String

Link: http://devskill.com/CodingProblems/ViewProblem/300

Problem Setter: S M Shaheen Sha

Segment tree Solution:

You have to store 4 information in each node:-

1. number of consecutive 1's at the beginning of the segment(prefix).

2. number of consecutive 1's at the end of the segment(suffix).

3. number of 1's block fully inside of the segment , which corner does not touch the right end or left end of the segment(sum).

4. size of the segment(sz). [ *** this can be avoided if you want to]

when merging two nodes, new values of new node will be

case 1 : if left child and right child contain only ones

prefix = suffix = total number elements

sum = 0

case 2 : if left child contain only ones but not left child

prefix = left sz + right prefix

suffix = right suffix

sum = right sum

case 3 : if right child contain only ones but not right child

prefix = left prefix

suffix = left suffix + right sz

sum = left sum

case 4 : left child and right child contain zeros

prefix = left prefix

suffix = right suffix

sum = left sum + right sum + ( if left suffix > 0 Or right prefix > 0 -> add 1 or 0)

when calculating the final result , check whether there is any prefix and suffix also.

So, overall complexity is O( NlogN ).

Problem E: Sanvi and chocolates-2

Link: http://devskill.com/CodingProblems/ViewProblem/315

Problem Setter: Bishal Gautam

In this problem, you are given the wishlists of M+1 peoples and all of them have their list of favorite chocolate box also total summation of these will be at most 200000. Now, for D days, robots will add some amount of chocolate from L to R.

Now, you have to answer Q wishlists.Every wish start with id of friend -X and total number of chocolates he/she wants to collect-Y. You have to find the total number of days required to fulfill his/her wish. He/She always collects chocolates from his/her favorite chocolate boxes.

The naive approach of doing addition action of robot and calculating days require iteratively will not pass here.

You should be familiar with algorithm known as "Persistence segment tree" to solve this problem efficiently.

Persistence segment tree can easily holds the information of previous days and depending upon that day's information, we have to update L to R on current day. so, we have to build a persistence segment tree for each day from 1 to D.

Now, you have to do offline processing as total distinct values of Yi for each Xi will be at most 15, we just need to process these distinct values of Yi from each Xi.

After that, we have to do optimize binary search upon sorted values of wishlists (ie, Y[ i ] will be greater than Y[ i-1] ). In each binary search, instead of updating lower range to 1 , we can update lower range to previous answer , since we need at least previous amount of days to fulfill wish greater than previous Yi.

After fixing mid in binary search, you have to calculate the total summation of chocolates in each of favorite boxes of person Xi on day-mid.

So, combination of persistence segment tree with lazy updates and tricky binary search is enough to get AC for this problem.

Overall complexity is O( Q*logD*logN ).