https://www.codechef.com/COZI2017/problems/COZIA
how this solution is get accepted??-https://www.codechef.com/viewsolution/13096241
May be the pair is exist between 1st and last element then this solution gives WA?
what if pair exist between i=0 and j=n-1,this solution only compare adjacent elements
j>i doesnt means that j is exact 1 greater then i
He used a nice trick.
As you say, if that pair is I=0 and j=n-1. We can prove that if this is true, then I=n-2 and j=n-1 is also a pair.
First see, when is the array not beautiful? When its completely sorted in descending order. Else you will find at least one A[I] such that A[I]<=A[j]for I< j. Only in an array sorted in descending order will you observe that no A[I] exists such that A[I]<=A[j] for I<j
Now, you say that what if I=0 and j=n-1 is the pair. Well, if this is the case, then it means you are saying I can only be paired with j=n-1.
This indirectly means that A[I]> A[I+1]…> A[n-2] and only on j=n-1 is A[I]<= A[n-1]
But see, can we not conclude from above that-
Since A[n-2]< A[I] AND A[I]< A[n-1]
This implies that A[n-2]< A[n-1]
See, can we not conclude this? Your test case such that “I=0 and j=n-1 are the ONLY POSSIBLE PAIR in ENTIRE ARRAY” does not exist.
Take an example of -
10 9 8 7 6 11.
I=0 and j=n-1 are forming pairs. I does not form pair with any other element except j=n-1. But see, isn’t my observation A[n-2]< A[n-1] holding true? That guy used a very neat trick to solve the problem in O(N) time, cause O(N^2) algo is likely to give a time-out.
Try formulating test cases on your own and you’d see what I am trying to hint at! If your condition of I getting paired with only j=n-1 or rather, any other index, you can see that my observation holds true. Meaning, if you say that index I can only be paired with index j, then my conclusion that j-1 can be paired with j is also true. In other words-
If an element A[I] at index I can be paired with ONLY A[j] at index j, and no other element before j, then this implies that A[j-1] (or rather, any element before j) could also be paired with j.
Hope this helps 
EDIT-
I debugged your code, it seems that your approach is wrong. What I feel is that you are trying to find maxima of the array, and then check if elements before it are less than or not.
Now first, if maxima occurs at any position except I=0, its obvious that elements before it would be less than it. Its maxima (maximum valued element) for a reason!
And in case maxima occurs at I=0, your test is inconclusive. As if maxima occurs at I=0, we cannot guarantee if array is beautiful or not before checking other elements after it. Lets take this test case for example-
1
4
28 7 25 24
Maxima occurs at I=0. And your code checks if any element before maxima is less than it. In this case, since there is no element before I=0 which we can check, that loop wont run and your code will return no. But if we look closely, we NEED something to check rest of array.
My approach would had been, if I were to do it using maxima, was to locate global maxima. If it occurs at I!=0, then beautiful array, and if its at I=0, look for other maxima. If that maxima is at I!=1, beautiful array, else if at I=1, we again cannot say anything and must look further
(Note that property of descending order is that every maxima occurs just after previous one. Eg-
25 > 16 > 14 > 10. Index of Maxima for range [0,3] is 25, for range [1,3] is 1, for range [2,3] is 2. Note how they are consecutive.
OR another approach should be, as that coder used, check if array is in descending array. If no, then beautiful array, else its not.
1 Like
What logic did you follow? I want to know what was in your mind which you were trying to implement. Will help me see if its an implementation issue or wrong approach
You are failing this test case-
1
4
28 7 25 24
I am Debugging whats wrong.
max is at index 3(if i assume 1 indexing),so i run loop till max index -1 and find whether if there is any element less then max if yes then set flag true and break and print yes else not,answer is yes for 1 4 28 7 25 24
Noo. The test case like-
T=1 , N=4 and Array is {28,7,25,24}. Damn, I should have cross checked. XD. Read my answer after edit, I answered your query there
i agree with u,its my mistake,but i am using right approach with some mistakes,Thanks for helping me…
Ps-i am not pro coder
now i have to remove this question? its already solved?
No need to remove the Q. You leave it or close it (if your karma is enough).
Yes, there are some mistakes in your approach, else it can yield correct results.