PROBLEM LINK:Setter Stepan Filippov DIFFICULTY:MEDIUM PREREQUISITES:Implementation, 2D prefix sums (check setter's code for its implementation), Geometry (for visualize rectangle intersection part) PROBLEM:Given $2$ $2D$ arrays, of dimensions $h_1*w_1$ and $h_2*w_2$, scale them both upto dimensions of $lcm(h_1,h_2)*lcm(w_1,w_2)$ and find number of equal elements in them. QUICKEXPLANATION:Key to AC The rectangles in this question can intersect in at most $9$ ways. Also, there is symmetry. We dont need to consider all rectangles of other photo intersecting a rectangle in fist photo. Note that by virtue of regularity, there are $9$ ways by which rectangles can intersect. The brute force of task $2$ counts all the rectangles of other within the rectangle of current photo. We can optimise it further by only considering the $9$ types of "representative rectangles", find their area, and multiply it with number of such rectangles. Rest of all is implementing this idea. EXPLANATION:This editorial will have essentially three parts, each dedicated for a subtask. The setter's code is well commented, and a description of idea along with code snippets will be given in editorial to make sure that you grasp the idea as well as how to convert that idea into code. First Subtask I recall someone once said you people dont like stories and want only the formal stuff :( . Ok then, lets skip all the stories and formally state the answer of the first subtask, because everyone likes formal things :D $Ans=\sum_{i=0}^{h11} \sum_{j=0}^{w11} \sum_{k=0}^{h21} \sum_{l=0}^{w21} Intersection(\alpha i,\beta j,\alpha i+\alpha 1, \beta j +\beta 1,\gamma k, \delta l, \gamma k+\gamma 1,\delta l+\delta 1)[p1[i][j]==p2[k][l]]$ where $\alpha=lcm(h1,h2)/h1 $ Just find above and we are done with subtask 1!! :) Subtask 2 This can be crossed by optimising the above approach. Check only the rectangles which actually contribute to answer instead of checking all possible pixels in enlarged version of $P2$. It differs from above brute force in $2$ aspects
Subtask 3 Now, how can we optimize more? We are quite clear that if number of rectangles are not much, then our solution of subtask 2 will work in time. But what if rectangles are too many? Lets try to get an intuition first. What if number of rectangles are possible? One of the scenarios when its possible is that, rectangles of $P1$ are huge and rectangles of $P2$ are very small. Now, try to imagine their intersection and see what subtask 2 algorithm does. For every small rectangle inside the huge rectangle of $P1$ (in scaled version), it will check if it lies inside, and if yes then add its contribution. Do we need to check $all$ the small rectangles, if we know the length of small and large rectangles? Obviously no! And this is where we will optimize now. If we know that $K$ rectangles lie fully and a rectangle lying fully has a contribution of, say $A$ to answer, then we can quickly find contribution of all $K$ rectangles by simple multiplication. Read my next sentence very carefully. We can, "abstract" or generalize the above line as, "The contribution of rectangles of type $i$ is $j$ and there are $k$ such rectangles." (I just replaced the fixed values with variables as placeholders for generalization). This approach can count contribution of all rectangles of a type $i$ at once! Now, ask how many such "types" can exist? Can it be $2$ ? Rectangle completely inside and rectangle partially inside? But "partially inside" sounds a bit vague. How will we actually prove that all those "partially" lying inside rectangles will have equal contribution? Hint: We can't because its false! This means, we need to further subdivide this "partially intersecting" type more and more, until we can get definite values of $j$ and $k$ for all types trivially. Now, multiple such definitions can exist, but the one identified by setter is beautiful. He identified, $9$ such possibilities
Now, with the $9$ identified types, he proceeded to find contribution of each type, and then number of rectangles belonging to each type (looking at his code, we can see that there can be only $1$ rectangle intersecting at corner). Lets see how to elegantly solve this. As usual for clear implementation, we should fist identify the "tools" or functions which we might need to finish the job. Reading the above idea, we get the following requirements
Now, the algorithm followed henceforth is quite simple. First, grab the data needed to check which of the $9$ cases the rectangle lies in. For each pixel in $P1$, find the coordinates of upper left and bottomright coordinates of rectangle in scaled version. Now, use them to find upperleft and bottom right coordinates of rectangle in original (i.e. NOT scaled) array of $P2$. This data is sufficient for us to make cases now. An implementation code for above is below if you want to sync it with explanation Now, start with your case making. If the rectangle intersection is of cornerintersection, then we know that count of such rectangles can only be $1$, and we can find their contribution by $getIntersection()$ function. A pseudocode to deal with one of the cases (one of the four corners) is given below, try to complete the rest for other $3$ directions. (All these snippets are taken from setter's code, so feel free to refer to it for final answer.) Now, for each of the $4$ sides with which rectangles can intersect, we need to find number of such intersections/rectangles AND their contribution. Recall the $2D$ prefix sum done earlier. It will be used to ultimately find number of rectangles. For now, since idea is more on syncing explanation and implementation of the idea, lets use $get_cnt()$ function which "does something" with $2D$ prefix sum and gives count of rectangles. (You are encouraged to explore what that "does something" is, before checking it out in setter's code. Its simple $< 5$ line code. Read my note on $2D$ prefix sum's use for a hint). Try to come up with code for rectangles intersecting at upper side. Then compare it with abstractedimplementation below, and come up with implementation for other $3$ directions. (Beware: Make sure not to over count rectangles in case the dimensions are $1*N$ or $N*1$ types. You must not count same rectangles in "intersecting with upper side" and "intersecting with lower side" etc. Count them only once!) Now what is left is the code for rectangles lying completely in the centre. Feeling upto the challenge? Can you use the tools defined so far to come up with that WITHOUT overcounting? SOLUTIONEditorialist $Time$ $Complexity=O(N*M)$ CHEF VIJJU'S CORNER :D1. Shoutout for Steppan! 2. How to find 2D prefix sum and its use 3. Hall of Fame for Noteworthy Solutions
Can see your code here? Give me a link to check it up and add :) asked 16 Sep '18, 02:56
showing 5 of 8
show all

Is @karolis_kusas tester and @um_nik editorialist of this question ?? xD answered 18 Sep '18, 14:56
I liked karolis' short code. It was clean. And @mgch liked um_nik's code XD
(18 Sep '18, 15:04)
You missed context here xD. Need some help ??
(18 Sep '18, 15:23)
I think yes XD
(18 Sep '18, 15:45)
Hahahaha @aryanc403
(18 Sep '18, 16:19)
Dont be a meanie and tell me the context wtf ._.
(18 Sep '18, 16:37)
That is why I asked for wikifying. xD Ok. Take this.
(18 Sep '18, 16:42)
XD...........
(18 Sep '18, 16:48)
Tester and editorialist's solution arent linked at all. :/
(18 Sep '18, 18:20)
Reread my answer.
(18 Sep '18, 19:47)
May be they felt that author is very nice so there is no need of it..
(18 Sep '18, 20:29)
Let me disclose. @karolis_kusas soln link points to tester soln. And this soln can be opened.
(18 Sep '18, 20:59)
showing 5 of 12
show all

My soln was rather a bit simpler. Just look at lli query(lli lx,lli ly,lli rx,lli ry) fn. It is similar to sum[r]sum[l1] in 1D. xD Upd  My Soln :P answered 18 Sep '18, 15:00

My solution: https://www.codechef.com/viewsolution/20048755 LL solverow( int a, int b, int w1, int w2, int gw ): solves the intersection of 2 intersecting rows. answered 20 Sep '18, 20:32

Please, can anyone help me! My Solution: https://www.codechef.com/viewsolution/20213601 Why I'm getting WA? answered 21 Sep '18, 01:00
I'm not generating 2D arrays. I'm directly comparing the elements of both strings.
(21 Sep '18, 01:03)

My code is too complicated due to wrong answers I got.. can't share xD
Wikify it.
Poor @admin tried so much :( . Perhaps discuss doesnt want my editorials wikified. Not that I have a problem with that >:) XD
XDDDDDDDDD
@taran_1407 is more powerful than @admin xD.
Seems like its a mere coincidence that it worked for me in one go @aryanc403. Poor @vijju123, who wasn't really looking forward to editorials being marked wikified. xD
Edit: Seems like it only shows being wikified. It's actually not.
Yes, this is now common on this forum. Try closing question or sometimes try deleting a question you will see undelete option instead of delete.
Discuss doesnt want my editorials wikified ^_^
GoForDiscuss