×

# How to approach Devu and Churu (IIT Kanpur Monthly rpogramming contest problem)

 0 Hello Guys, I submitted Solution to Devu and Churu problem but it was giving me TLE since i used a normal approach.I want to know How to approach this problem.some people have used Binary search approach like this one http://www.codechef.com/viewsolution/5957224.TIA :) asked 22 Jan '15, 01:53 3★ajay154 1.6k●7●20●44 accept rate: 8%

 1 Small hint: Fix a height, then try for each 1 <= i <= j <= n such that you are currently looking at row = height and columns from i to j(inclusive). Now for this fixed i, j, you can note that if we iterate over k >= height such that we are currently looking at rectangle (height, i) and (k, j). Then in this rectangle, if we increase k, then number of distinct elements also increase. So you can apply two binary searches over k to solve problem for fixed, height, i and j. So overall complexity will be O(n * n * n * n * log n). Sample Solution You can check my code which uses exactly same variables here. More optimization By using the idea, that k will always increase, you can solve it in O(n^4). You can also use a solution called monotone queue too. Another solution It uses trick that K is not that large, K <= 26. So you can use bitmask idea to solve the problem too. answered 22 Jan '15, 02:38 2.5k●53●137●170 accept rate: 20%
 1 I used two pointers, I solved it in O((n^3)*26), if u don't understand my solution u can think about how to solve that problem for this kind of matrix A(nx1). answered 22 Jan '15, 08:22 5★previus 11 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,214
×1,409
×1,056
×846
×344
×285
×105

question asked: 22 Jan '15, 01:53

question was seen: 3,593 times

last updated: 22 Jan '15, 08:22