why im getting wrong ans?? Encoder Painting wall.

Here is my code . i tested as per my knowledge giving correct answer but when im submitting im getting wrong can any one tell where i done mistake

Consider this case

5 4

3 5 5 2 3

1 3 2 4 3

Your solution will give answer : 1

But the answer is : 2

Considering above example :

Your solution is appending 3 to prevColor list for first 5 it encounters in the list and your value of val becomes 1, when you search next max you again get 5, so your val remains same i.e., 1 and you append 2 to prevColor.

But now when you search for next max you encounter 3 for which corresponding color is also 3 which is already present in prevColor so your val doesn’t get updated and hence your val remains 1.

Solution link : https://ideone.com/5dNBx8
Hey i am getting correct answer on your output but still i am getting wrong answer could u plzz help me out also!! I have tried it on various test cases but still didn’t get a case where it fails.


The wrong thing with your approach is that you are only comparing consecutive colors

Consider this example :

5 5

5 4 3 2 3

1 2 3 4 1

Answer with your code : 3

Correct answer : 2

Since in the case of height = 3, the value of lastcolor variable is 2 and hence when it compare color color[p[i].second]==lastcolor it gives false and your code updates ans variable to 3, but since we have already considered color = 1 in case of 5 hence ans variable shouldn’t be updated to 3 but remain 2.

Correct approach would be to use an array of length m+1 and set the value at corresponding index(where index represents color value) 1 for all the cases where you are updating done. Then iterate through this array and print the total number of indexes for whom corresponding value is 1.

I am getting correct answer on both of your test cases, can you give me a corner case where my solution is wrong? code :- https://www.codechef.com/viewsolution/21226382


Consider this case

5 5

5 4 3 4 2

1 1 2 2 3

Answer with your solution : 2

Correct answer : 3

Your code is simply erasing the color=1 inserted at height=5 when i=3 and j=1 in your code.

understood very well! thanks

Thnku so much @deermen001 . Really Appreciated!!

Still confused you can check my solution :