You are not logged in. Please login at www.codechef.com to post your questions!

×

PHOTOCOM - Editorial

2
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Stepan Filippov
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Implementation, 2-D prefix sums (check setter's code for its implementation), Geometry (for visualize rectangle intersection part)

PROBLEM:

Given $2$ $2-D$ 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.

QUICK-EXPLANATION:

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}^{h1-1} \sum_{j=0}^{w1-1} \sum_{k=0}^{h2-1} \sum_{l=0}^{w2-1} 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 $
$\beta=lcm(w1,w2)/w1$
$\gamma =lcm(h1,h2)/h2$
$\delta=lcm(w1,w2)/w2$
$Intersection$ is a function which takes corner of $2$ rectangles and returns their intersection area.

Just find above and we are done with subtask 1!! :)

View Content

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-

  1. It deals with entire contribution of rectangle at once instead of individual pixels
  2. Only count rectangles which actually contribute! For a fixed $(i,j)$, if the rectangle contributes, we have constraints on $k$ and $l$ as $\lfloor \frac {\alpha i} {\gamma} \rfloor \le k \le \lfloor \frac{\alpha i +\alpha -1}{\gamma} \rfloor$ and $\lfloor \frac {\beta j} {\delta} \rfloor \le l \le \lfloor \frac{\beta i +\beta -1}{\delta} \rfloor$. This reduces complexity to $O((h1+h2) \times (w1+w2))$. For more info, you can refer to attached file in bonus corner. Interested ones can refer to tab below for more details
View Content

Subtask 3-

Now, how can we optimize more?

We are quite clear that if number of rectangles are not much, then our solution of sub-task 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 sub-divide 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-

  • $4$ types for rectangles intersecting at the $4$ corners.
  • $4$ types for rectangles intersecting at the $4$ sides.
  • $1$ type for all rectangles lying completely inside.

alt text

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-

  • A function to tell if rectangles intersect or not. Or even better, given the area of intersection of the rectangles. This is $getIntersection()$ function in setter's solution, which takes the upper left and bottom right co-ordinates of the two rectangles and gives the area of intersection.
  • A function to get a count of how many rectangles of each type are there. Setter used $2-D$ prefix sum to find this. Basically, $Prefix[i][j]$ would give the number of pixels which are $1$ in ORIGINAL (not the scaled!!) photo of $P2$, and by this we can determine number of pixels which are $0$ as well (as sum of '0' and '1' pixels = Area of rectangle defined by indexes $(i,j)$ and $(0,0)$). A brief explanation of how to calculate this is in my corner, or you can look at setter's code as well.

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 co-ordinates of upper left and bottom-right co-ordinates of rectangle in scaled version. Now, use them to find upper-left and bottom right co-ordinates 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-

View Content

Now, start with your case making.

If the rectangle intersection is of corner-intersection, 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.)

View Content

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 $2-D$ 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 $2-D$ 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 $2-D$ prefix sum's use for a hint).

Try to come up with code for rectangles intersecting at upper side. Then compare it with abstracted-implementation below, and come up with implementation for other $3$ directions.

View Content

(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?

View Content

SOLUTION

Setter

View Content

Tester

View Content

Editorialist

$Time$ $Complexity=O(N*M)$
$Space$ $Complexity=O(N*M)$

CHEF VIJJU'S CORNER :D

1. Shoutout for Steppan!

View Content

2. How to find 2-D prefix sum and its use-

View Content

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

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

wikified 20 Sep '18, 14:29

taran_1407's gravatar image

6★taran_1407
4.0k31104

1

My code is too complicated due to wrong answers I got.. can't share xD

(18 Sep '18, 13:51) l_returns5★

Wikify it.

(18 Sep '18, 15:51) aryanc4035★

Poor @admin tried so much :( . Perhaps discuss doesnt want my editorials wikified. Not that I have a problem with that >:-) XD

(18 Sep '18, 16:18) vijju123 ♦♦5★

XDDDDDDDDD

(18 Sep '18, 16:47) l_returns5★

@taran_1407 is more powerful than @admin xD.

(20 Sep '18, 15:09) aryanc4035★

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.

(20 Sep '18, 16:55) taran_14076★

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.

(20 Sep '18, 17:16) aryanc4035★

Discuss doesnt want my editorials wikified ^_^

GoForDiscuss

(20 Sep '18, 17:26) vijju123 ♦♦5★
showing 5 of 8 show all

Is @karolis_kusas tester and @um_nik editorialist of this question ?? xD

link

answered 18 Sep '18, 14:56

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

I liked karolis' short code. It was clean. And @mgch liked um_nik's code XD

(18 Sep '18, 15:04) vijju123 ♦♦5★

You missed context here xD.

Need some help ??

(18 Sep '18, 15:23) aryanc4035★

I think yes XD

(18 Sep '18, 15:45) vijju123 ♦♦5★

Hahahaha @aryanc403

(18 Sep '18, 16:19) the_extractor4★

Dont be a meanie and tell me the context wtf ._.

(18 Sep '18, 16:37) vijju123 ♦♦5★

That is why I asked for wikifying. xD

Ok. Take this.

View Content
(18 Sep '18, 16:42) aryanc4035★

XD...........

(18 Sep '18, 16:48) l_returns5★

Tester and editorialist's solution arent linked at all. :/

(18 Sep '18, 18:20) vijju123 ♦♦5★

Reread my answer.

View Content
(18 Sep '18, 19:47) aryanc4035★

May be they felt that author is very nice so there is no need of it..

(18 Sep '18, 20:29) l_returns5★

Let me disclose.

@karolis_kusas soln link points to tester soln. And this soln can be opened.
@um_nik soln link points to editorialist soln. And this soln gives access denied.

(18 Sep '18, 20:59) aryanc4035★
1

Wtf. WEW. I need to ask @admin aaj kal kaha madhosh hai woh LOL.

(19 Sep '18, 00:07) vijju123 ♦♦5★
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[l-1] in 1D. xD

Upd - My Soln :P

link

answered 18 Sep '18, 15:00

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

edited 18 Sep '18, 15:56

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.

link

answered 20 Sep '18, 20:32

codebreaker123's gravatar image

4★codebreaker123
1765
accept rate: 10%

Please, can anyone help me! My Solution: https://www.codechef.com/viewsolution/20213601 Why I'm getting WA?

link

answered 21 Sep '18, 01:00

msrathode's gravatar image

3★msrathode
1
accept rate: 0%

I'm not generating 2-D arrays. I'm directly comparing the elements of both strings.

(21 Sep '18, 01:03) msrathode3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×850
×647
×241
×40
×28

question asked: 16 Sep '18, 02:56

question was seen: 1,890 times

last updated: 21 Sep '18, 01:03