Coding Contest-15 Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

Coding Contest-15 Editorial

by BishalG » Fri Apr 28, 2017 8:34 pm

Problem A: Names
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". :cry: :cry:
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. :roll: :(
The main aim of this problem was to make contestant familiarity with most efficient O(N) approach of two pointers and/or Offline processing . :) :P
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. 8-)

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
and so on......
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. :oops:
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. :ugeek:
Overall complexity is O( Q*logD*logN ). :)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sat Apr 29, 2017 4:38 pm

Problem E:
The problem distribution "DCP-315" says that :
total summation of favorite chocolate count will be at most 200000.
But This value at Editorial is 20000.
Which one is wrong?
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sat Apr 29, 2017 5:03 pm

Problem E:
What do you do in each binary search?
Assume that you set the day=mid and you want to check it.
Do you get the sum of number of chocolates in each of favorite boxes of person Xi on day-mid?
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Sun Apr 30, 2017 12:57 am

@seyedssz, the actual value is 200000. There was typing mistake in editorial. Thanks for correction.
And , of course 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.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sun Apr 30, 2017 11:19 am

So The time can be :
O( 15 * max_Ti * log(D) * log(N) ).
log(N) for segment, log(D) for BS , 15*max_Ti is the number of elements you should check for a person Xi
that can't get AC as max_Ti can be about 10^5 and so your binary search trick can't change the time complexity and optimize it just a little.
So if you want a single element of your array from segment, it doesn't need lazy propagation.
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Sun Apr 30, 2017 6:55 pm

@seyedssz, Thank you for curiosity regarding complexity. Notice that N,M,D are limited to 50000 and on every BS of 15*max_t, range is reduce by some constant factor so after all (15*max_t*logD) will be ( max_t*logD*constant ) . Also, there are lots of optimization that can be performed to pass within limits as time limit was too tight.
For your convenience, we increased time limit to 4 sec. Hoping to see you in leader-board of ranking :)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Tue May 02, 2017 10:44 am

So,a nice problem thanks to setter. :)
It can solved with a BIT and Parallel binary search too.
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Wed May 03, 2017 11:11 am

@seyedssz , Nice to see you in leader-board of the problem-E.Also, Nice to know you solved the problem with different logic. :)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm


Who is online
Users browsing this forum: No registered users and 1 guest
cron