Try thinking in a reverse manner, that is from a non decreasing array, we will delete some prefix and append that prefix of numbers to end of the array and after doing this operation for certain number of times , you will find that you have the array like:-
[3 3 3 3 3 4 4 4 1 1 1 2 2] for our original array :- [1 1 1 2 2 3 3 3 3 3 4 4 4 ]
If you are able to notice the modified array, you can easily see the elements follow a pattern:-
(1) elements are in non decreasing order to certain extent, then
(2) it decreases to some value and then follow the same pattern of non decreasing sequence.
So, Overall for the given input array which we need to make it non-decreasing sequence by allowed operations(delete some suffiix and insert at the beginning of the array) , we can have following answers:-
(1) Answer is “YES” if:-
(i) Given array is already in non-decreasing order.
(ii) Given array has exactly on change point(arr[i]<arr[i-1] for valid ‘i’) and arr[n-1]<=arr
(2) Else, answer is “NO”
Hope this helps.
I think it was more geometric ,constructive and maths questions .
Can anyone explain what logic is used in this - ICM0003 Problem - CodeChef .
The questions were a bit difficult to be rated for only div2 and div3.
Few queries -
How does rating change work out with parallel contests? Which contest is considered first? If one’s division changes after the first contest, how does it affect the rating calculation in the second?
I think P(X=i) would be sin(A) ^ (2i-2) * cos(A) ^ 2 and E(X) would be sec(A) ^ 2, where A = (N-2) * PI / N / 2.
Hey, I made a mistake. The explanation is correct. Thanks.
The contest which starts first is calculated first.
Division change after the first contest does not affect the second contest’s rating calculation.
Thanks a lot, @admin!
In case of division change after first contest calculation, for the second contest calculation, is the contestant considered belonging to the changed division or the division in which (s)he participated? If latter, how are the rating changes combined?
The latter. There is no non-trivlal combination - it shows up in the user profile that they participated in the contest in whichever division they actually participated in, even if according to their (retrospective) rating then, they should have been in a different division.
when will the ratings come??
The ratings for this contest will be updated once the April Long Challenge is over.
- ICM0013 (Lucky Boundaries) - Editorial
- ICM0001 (Suffix Sort) - Editorial
- ICM0003 (Infinite polygons) - Editorial
- ICM0005 (Team Division) - Editorial
- ICM0004 (Stack Of Rectangles) - Editorial
- ICM0006 (Special String) - Editorial
- ICM0012 (How many cuts) - Editorial
- ICM0010 (Good pairs of substrings) - Editorial
why such a long delay in updating the ratings, has codechef become so incumbent?
Please read announcement section of contest then decide what codechef become.
Not sure what word you were aiming for there… Incompetent, maybe?
Anyway, we are so ‘incumbent’ because updating the ratings of this contest while the Long contest is ongoing will change the division of some users participating in it, which will mess up their Long contest participation.
I am sorry for that, I told that because I couldn’t wait for the rating changes.
Is their any bug or what ? some contestants are shown rating changes while some are not?