_w_'s blog

By _w_, history, 3 years ago, In English

I was solving the 1482E - Панорама города, and it turns out to be WA. I am not sure why did this happen please help me out.

I have used a 2D dp array where dp[i][0] stores the maximum beauty that can be achieved if we combine ith building with the last building dp[i][1] stores the maximum beauty that can be achieved if put in a new photo

While storing the value in dp[i][0] I also took note that in some cases using dp[i-1][0] and dp[i-1][1] both may result with same beauty. So, I took the one that had the greater beauty for the smallest building in the last photo cause that will give a better solution if we happen to find a smaller building with better beauty.

for this "combine" I used a 2D mn_idx array that stores for each state the index of building with minimum height in the current photo ending at ith building.

I could not see the testcases, it shows WA on test 8. So is the logic completely wrong (it will be better if you could please explain why is that so?)?

Here is my code

Code
  • Vote: I like it
  • +4
  • Vote: I do not like it

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

It's not guaranteed that if you combine it with last photo or start a new photo from here you will get the maximum

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

    Could you please provide a counter test?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Here is a test case

      7

      7 6 3 5 1 2 4

      2 -7 -7 -4 3 -8 1

      for 5th index(1 based indexing) if you take the last and merge it,it won't give max or by anyway unless merging it with 1st index

      answer for i=1 to i=7 are as:-

      2 -5 -5 -7 5 5 6

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

        Sorry but the code works for this test case and provides better result. 2 -5 -5 -2 5 5 6.

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

          My Bad for the answer I didn't run it on my code but there are many cases

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You approach is wrong cause your code will fail on

5
1 3 4 5 2
100 10 10 10 -1000