This problem says we need to find 4th side length of the quadrilateral given 3 lengths. There are various approaches to solve this problem. WHat I thought was that align one line parallel to OY axis and aling one line parallel to x axis and in the middle align the other line. So we get a structure something like this.
|
D |
| | C
| |
A |_______| BNow I got 4 coordinates with three lines so 4th line is obviously. CD if AB=a , BC =b , AD =c , and assume A to be origin. Coordinate of C={a,b} , D={ 0,c}. Thus length of CD =
. By euclids formula. Why ceil? because to make float to integer as our quadrilateral can have sides which are aligned at angle to origin thus ceil works fine here.
In this problem we were required to make all rows and columns of the matrix palindromic. ROws=n , Cols=m , mat= given matrix. For a sequence of length n to be a palindrome the element at index i must be equal to n-1-i th element index. Consider that for making ith row palindromic. element
Where j is an index among m columns.
Simialrly for making jth column palinfromic.
Equation 1 and 2 says that.
So all we were required is to make these 4 values equal to any one of them. So I brute forces over all rows from 0 to (n-1)/2 and all columns. from 0 to(m-1)/2. and find those 4 values lets say these 4 values are x,y,w,z. try making all of them equal to x or y or w or z. And take the minimum operations needed.. to make all of them equal.
This problem deep dives into properties of substrings and numbers. so we need to remove all possible n*(n+1)/2 substrings from the string and sum up the decimal value of remaining shrinked string. For example remove 0 from 107 it becomes "17"==1*10 +7*1=17. Cool.
Calculate contribution of each digit in the possible sum is one way to solve to this problem there may be some ther approach which you may enter in comments. But let me explain simple one.
lets say you want to calculate the contribution of ith digit. let this digit be d[i].
If we remove any substring from the front of the digit d[i]. then total substrings to remove ==(i*(i+1))/2. and for this substrings removal place value for d[i] still remains same as place value is counted from backwards. thus place value =n-1-i. thus total contribution if I remove substrings from front is
where d[i] is the digit.
Now removing substrings from back of i. lets say total digits at back of i is k=(n-1-i). Now if I remove all k numbers then ith digit comes at 0th place value if I remove k-1 length substring from back then d[i] comes at 1st place value. If I remove k-2 length substring then d[i] comes at second position. thus it is building an AGP. Also notice k length substring at back=1, k-1 =2 , k-2 =3; thus this sequence goes like .
so contribution of removal from back is S2= (S*d[i]).So overall contribution of d[i] is S1+S2 . Sum up this for all i digits . precompute this AGP sequence and for each i get answer in O(1).
Thus time complexity is O(N)
Given source S(x1,y1) and Destination D(x2, y2). And some teleportation points which are instantly accessible if you are in same row or same column. for example if some teleportaion point is x,y . If we are in a coordinate which have same x or same y coordinate then we can jump the teleportation point in no time. We need to find minimum time to travel S to D smells something of Dijskarts. but will depend on the type of edges.
How to add an edge.
Source to Teleport edges :-At first if you are at S(x1,y1) then we can go to any teleportation point(x,y) in time min(abs(x1-x),abs(y1-y)). SO we got some weight for edges from source to teleportation points.
Source to Destination edges:- Also S to D edge weight =abs(x1-x2)+abs(y1-y2).
Teleport to Destination edges :- Similarly from each teleportation point (x,y) the edge weight to reach destination D(x2,y2) is abs(x-x2)+abs(y-y2).
Teleportation to teleportation edges. :-
This was the trickiest part of the problem for inter teleportation edges. If we go from each teleport to other teleport and add the edge then it will take n^2 time and space. Which is not optimal. So. what you can do . Think a minute before proceeding further.
WHat if I sort the teleportation coordinates first according to their row coordinates. and next according to their column coordinates. and pair up the edges for adjacent teleportations.
After sorting teleportations according to their row numbers. take 3 teleports $$$i$$$, i+1, i+2. you may check it is not optimal to go to teleport i+2 from i and then come back at i+1. Hope you got the intuition from here. Now it may seem possible to add the edge weight between teleport i and i+1. as the absolute difference of their rows.
Similarly we can sort according to their column numbers and proceed the same way, Thus a teleport is linked to 6 memebers one is source. other is destination , and 2 nearest row wise teleports and 2 nearest column wise teleports. THus our graph contains at most 6*N edges.
What is vertext number . lets say inputted teleport i have vertex i . SOurce have vertex number 0 and Destination have vertex n+1.
Thus what to wait for we have vertex and edges of the graph. Build it and apply dijskarts.
TIme complexity O(nlogn).
