Questions D and E
Aditya Mondal
Specialist @CodeForces(max. 1495) || 4?@CodeChef(max. 1801) || Knight @LeetCode(max. 2083) || Runners-up in Avalanche track @Hack4Bengal3.0 || 2nd Runners-up @HackOasis1.0 || Student at IEM Kolkata
Continuing from the previous post.
Problem D:- Manhattan Circle
Question:- Given an n x m grid consisting of '.' and '#', where a '#' means part of the Manhattan Circle. We are tasked to find the center of this circle.
Approach:- This problem might look tricky but can be solved intuitively and with a greedy approach. We will run 'i' loop(1 to n) to iterate across the rows and 'j' loop(0 to m-1) to iterate across the columns and initialise a check variable to '0'. This variable is meant to find the first occurance of '#' in the grid. This will be top of the circle. After finding top, we change value of check to 1. You can alter it with a 'bool' variable too. After this if we find any occurrence of '#', we will simply take the minimum of these values as left and the maximum as right. Now the y-value for the centre will be (right+left)/2 [Coordinate Geometry basics] and the x-value will be top+(right-left)/2 [Again from coordinate geometry]. It will be easier to understand if you can draw the figure on a rough paper.
This is where the difficult problems start.
Problem E:- Secret Box
领英推荐
Question:- We are given a box B(x*y*z) and also a box S of volume 'k'. Now we are to determine the maximum no. of distinct locations the box can be placed.
Approach:- Here, a considerable amount of mathematics is involved to approach the problem. One thing that we can realise after reading the problem multiple times that since we can only place in locations lesser the (x,y,z) as well as the fact that the volume of S is constant, We can do it by getting the factors of k which are less than or equal to 'x','y' and 'z' respectively. After obtaining 3 vectors consisting the above values for 'x','y' and 'z' we will brute force through each value and check the ones whose product equals k and suppose (a,b,c) is one such set. Now, using a little bit of combinatorial arithmetic we can figure out that no. of distinct solution for this is (x-a+1)(y-b+1)(z-c+1). For each such set, we maintain the tally of maximum among them which is the answer.
Will take some time to simplify the approaches of the remaining problem. So, stay tuned for the next part and also tell me your doubts(if any) in the comments.