Tobby_And_Friends's blog

[Data Structure Problem] Light OJ 1424 — New Land

By Tobby_And_Friends, history, 7 years ago, In English

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1424

Solution Link: https://ideone.com/2eUIav

Verdict: TLE

Solution Approach: Trying out all possible row combinations and for each row combination finding the maximum area using binary search

Someone please help me out how can I optimize my solution.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Can you write statement of problem here? Seems I have to register for problem statement in link.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    This is the problem statement:

    "Once upon a time there lived an old wise king. He had only one son. The prince had the idea that he (the prince) was about to be the future king; that's why he became too lazy day by day. This made the wise king a bit worried because his lazy son couldn't be the correct man for the throne. He couldn't sleep; his kingdom was in need of a perfect king, not the lazy king.

    One day, while doing his regular works, he found an excellent idea. Next day he called his son. He said that he wanted the prince to have his own kingdom. The prince became very excited. The king continued that the prince can have a land from the king's kingdom, but he should start walking after sunrise and cover a rectangular area before sunset. Then the land would be given to the prince. The lazy prince thought, "It would be an easy task!" That's why he wanted to find the maximum rectangular area in king's land. But there were some rocks in the kingdom, and the prince didn't want any rocks in his new land. He would rather take nothing, but no rocks.

    The kingdom can be thought as an m x n grid, where m is the number of rows and n is the number of columns. Each cell in the grid is a small rectangular land whose area is one. If a land contains rock it will be denoted by a 1, otherwise it will be denoted by a 0. The prince can walk in the sides of the cells and he can either take a cell (land) or ignore it, but he can't take a part of a cell. Now your task is to find the maximum rectangular area the prince could cover.

    Input

    Input starts with an integer T (≤ 4), denoting the number of test cases.

    Each case starts with a line containing two integers: m and n (1 ≤ m, n ≤ 2000). Each of the next m lines contains n characters (either 0 or 1) denoting the kingdom.

    Output

    For each case, print the case number and the maximum rectangular area the prince could take."

    Time limit: 5 seconds

    → Reply