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

×

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

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

ajay154's gravatar image

3★ajay154
1.6k72044
accept rate: 8%


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.

link

answered 22 Jan '15, 02:38

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

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).

link

answered 22 Jan '15, 08:22

previus's gravatar image

5★previus
11
accept rate: 0%

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:

×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