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 |_______| B
Now 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).
I have tried writing editorial for A to D problems as official version is not out yet. Hope it helps someone.
YEAH IT DOES HELP ME AND MANY OTHERS ...THANK YOU
My PLeasure
You wrote every teleport connected to two nearest 2 row wise teleport if some teleport is index i to which which it connected??
You have to sort the teleports according to rows once and thus the original indices will be changed. if your i is in the newly sorted array then you have to add an edge of it with i-1th in the newly sorted teleports and with i+1 th in the newly sorted teleports.
Why with i-1 is it necessary for adding i-1?? Why it will come forward after going to backward is it not optimal to add only I+1th edge??
I mean that adjacent ones have to be added an edge. It may come backward when destination is in opposite direction, not always destination will be having greater row and greater col number to each telports and source, thus to consider all the possible cases I have simply made an edge between adjacent row numbers. and adjacent col ones. whatever be the location.
So if I add for only for one position (I+1) then that will not work??
YOur edge must be undirected then only it will work.
Auto comment: topic has been updated by AM_I_Learning (previous revision, new revision, compare).
Can you explain the ceil part for A again. How do you ensure that D doesn't connect beyond C?
OK cool. in the diagram you may see that I have made the lines AD and BC at 90 degree to line AB . lets say the calculated length for CD comes not an integer. thus I can rotate any of AD and BC to such an extent to fit it into the next integer . Because still I have free space of 90 degree + 90 degree for rotation. like this . if CD comes non integer then take its ceil value to fit something like this.
Isn't the same true for floor as well? You can always rotate D to the right to align CD properly. Isn't that true?
Ya we can!
I solved the problem A using your technique in contest =) AM_I_Learning
A simpler solution to A:
any reason on why it works? (even i did the same , but i don't know why it works)
For any non-degenerate quadrilateral sum of three sides should be greater than the fourth side.
I simply did binary search to find the answer(94671381).
well, proof is simple. Think all the given three sides in a line, but you know that these can't be straight line so you have to tilt two sides upwards and your answer will be (a+b+c-something positive).
that was nice , thanks.
could u tell me why do we have to subtract something from the sum ?
If we don't subtract, then d = a+b+c and it won't be a quadrilateral either(you can find what is a quadrilateral on google)
Btw, why your profile pic is so scary?
guys cant we simply do a+b+c-1.although i loved authors approach.it is an overkill for first problem.
We can even just do "c", "c" being the longest between a,b,c.
That would fail for 1 100 1
I think his c is the maximum value between a, b and c
I meant c when a,b,c are ordered from smallest too largest, sorry.
Edited my comment to make that clear.
nice explanation
I kept trying this formula for AGP to calculate S2, but got no luck. Was constantly getting wrong answer.
For Problem A I just printed the maximum element of input array as the quadrilateral inequality will always hold for this configuration 94661820
Someone please help me in problem B, I have tried the same approach that the author said for the problem i.e , I considered all the 4 values :- mat[i][j],mat[i][m-1-j],mat[n-1-i][j],mat[n-1-i][m-1-j] and tried to make them equal by taking their average and changing every value to the avg. value but somehow ans is not coming right.
How can you prove that given 4 values to make them all equal , we have to change them into one of the values among them and not into their avg ?
My code's link is :- https://codeforces.net/contest/1422/submission/94722871 please help me .
Use the median, not the average.
can you please explain me why should i use median and not the average ?
Eg: 4 matrix values(to be equal for being palindrome) be = 2, 4, 6, 20 =>avg=8, cost = 24, median = 4/5/6, cost=20
I got your point but can you suggest me when to use median and when avg?
When changing some values into a same value , changing them into their median is always the smallest.
It can be proven by maths.
We consider $$$a_1$$$ and $$$a_n$$$. We know that changing them into some value between $$$a_1$$$ and $$$a_n$$$ is the best choice. Now consider $$$a_2$$$ and $$$a_{n-1}$$$ , it's the same as our previous step.
Continue doing this,and we know changing them into their median is always the best choice.
Detailed Explanations
**thanks a ton☺☺☺ ** It helped!!
Every time I see your profile picture, it strikes me as someone's dead photo. The white background, the date under it, all strike together as someone's memorial.
You can try formatting the equations in your editorial
Thanks anyways.
Auto comment: topic has been updated by AM_I_Learning (previous revision, new revision, compare).
FIxed the equations!
Do you mean O(mlogm) i guess in the editorial of Problem D , cause just seen you swap n & m in the code :)
Ya you got correct.
Great effort man ! You did a great job to make an unofficial editorial . I have read the whole and just i thought you missed explaining the important part of optimal thing to connect adjacent neighboring teleportation points in the Problem D . By the way i made a video editorial of the Problem D here : https://www.youtube.com/watch?v=X1nmTo_Gkww Have a great day ahead man , Jai Shri Ram :)
Please,Can someone please tell me where did I go wrong in this solution for C?? I am taking left and right contribution of every digit but it just isn't working.For right contribution I computed the sum of AGP.
UPD: Ignore this comment.
What does AGP mean?
Can someone explain how the final answer for C is S2+S1? Why isn't it S*S1?
in problem B,can't I do binary search to find the optimal value for the 4 values a[i][j],a[i][m-j-1],a[n-i-1][j],a[n-i-1][m-j-1]?
If I got you correctly then .. you are trying to
1.do a binary search in range [0,10^9] .
2.choose the number which gives minimum result.
but how do you decide which element to choose. Let's say you fix an upper_limit =5*10^9 . in the next step you find the mid=(10^9+0)/2. for each set of 4 values in the range [0,10^9] you will always have an answer < upper_limit with this mid value. In this case how do you choose which half to choose in the next step [0,mid] or [mid+1,10^9].
I will check the values which give me the minimum result from the 4 values and half the interval accordingly
Yeah, I did Binary Search but it TLEd for some reason, I was very surprised. Can someone check why this happened?
https://codeforces.net/contest/1422/submission/94685541
"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)."
Here you are considering weight from destination to the teleportation point, why not to consider from teleportation point to the destination?, although intuitively it looks correct to add the edge in the way you added here but I am not able to get the proof why we are considering the former one!
Because destination is not a teleportation point which can be accessed instantly if you reach its row. Hope it makes some sense?
I think in D we don't even need to connect edges from source to each and every teleport since according to analysis 4(edges between transport to transport) we can just connect edges from source to 2 nearest row-wise and 2 nearest column wise teleports and rest all will be handled by the sort function in the same way, won't it be working? AM_I_Learning, I haven't tried proving from the destination point of view, but I think it might be the same as well, if the former one is true!