Makise_Kurisu's blog

By Makise_Kurisu, history, 4 years ago, In English

Hi, I was trying to solve this problem from a coding test and came up with an O(n^4) solution which goes like first I will precompute the 2-D prefix sums of the entire grid and then for each cell naively Bruteforce for all possible solutions in n^2 operations, It would be great if you can share your insights/solutions for the problem. The contest is over 5 days back you can answer as late as you want until you are assured of this.

PROBLEM STATEMENT
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Seems like it is supposed to be a brute force with 2d prefix sums.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I figured that solution out as I mentioned in the post, please share any better/different solution or approach you have.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      On second thought, brute force with 2d prefix sums would be O($$$n^5$$$) right? Because you have to build two rectangles at the same time for each point?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess no, as we are just traversing the entire grid for each cell 4 times so it should be O(4*n^4) which is O(n^4) only

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why would not $$$O(n^4)$$$ pass?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I was not able to implement this solution in time, that's why I asked for an approach or solution that is somewhat easier to implement and also if the solution that I suggested in the blog is the desired/correct one or not