don’t mind the question
but how much time it took for you to prove this solution when you tried doing it first.
2 Likes
Bit tricky to say for sure, I originally came up with an incorrect idea (using prefix min and suffix max). After that I was just trying some small cases to verify, and realized that idea was wrong. Once I got that counter case it was fairly intuitive to reach the a_i < a_(i + 1) condition and realize that we can make a range really close to a value then increase / decrease it.
So I’d say around 30-40 mins to come up with the actual soln (not too sure since I was toying around with the general idea, not 100% fixed on just this variant), and maybe another 15 mins or so to roughly formalize a proof.
Still working out the finer details and formalizing a proper construction took me another 15-20 mins to think and write out when I was proposing the problem.
6 Likes
Still it is exploding speed.
Actually I was able to do this question instantly with a very nice proof. Ig it is definitely shorter then the editorial.
First some observations :
- Observe that if you have 2 numbers A and B then you can make A to B or B to A.
- So you can basically make a chain of same numbers.
- So if you are able to make a chain like this : [m,m,m,m,…m,x] and x>m where m is the minimum element then you will definitely be able to make a strictly increasing sequence out of this. Just keep updating m=(right_element+m)/2 starting from the last m.
Here is the outline :
- If array is already SI then print YES.
else
2)If the last element is greater then the minimum element then print YES
else
3)Now the last element is the minimum element, so our job now is to find an element that is greater then the last element and also has a some smaller element to the left of it.
It can easily be done by maintaining prefix_minimas.
4)Also check for case of all equal elements.
6 Likes
I solved it using prefix mins can you verify my idea of proof above thanks!!
Simple even if you find one such pair such that Ai < Ai+1 then we will always be able to convert the whole sequence into the strictly increasing one
It took very much time because i was thinking the problem can’t be that simple so did’t submitted 
but still nice catch 
CodeChef: Practical coding for everyone solution
3 Likes
Yes, it uses prefix mins, but mostly just replicates the same condition as the intended solution (a_i < a_(i + 1)).
My original idea with prefix min and suffix maxs was actually really different and would fail on cases like these:
3
10 4 8
Fun fact, that’s actually the counter case I found that led me to realizing the actual solution during the early stages of thinking about this idea.
Also the editorial is a bit on the long side only because it does an excellent job breaking down each and every observation and its proof, even if it might be trivial for a lot of participants. Additionally it also shows an explicit construction to make it clearer, kudos to the editorialist for doing a brilliant job with it.
6 Likes
This how I proved (sadly after the contest had ended) that the presence a single A_i < A_{i+1} is sufficient and necessary for the sequence to be sortable. It looks long but there are just a few main ideas (those that I have bolded) that solve the problems. Rest is just to maintain rigor. Once you get the bolded ideas, getting the rest part is much easier.
Firstly like the official solution says, by the averaging we can bring any two adjacent numbers arbitrarily close to each other (but the ordering between them remains same). Like if two adjacent elements are (1,2) and we apply averaging again and again we get (1,2) \longrightarrow (1, 1.5) \longrightarrow (1, 1.25) and so on. The second term keeps coming closer to 1 but is always larger than 1. We cannot make it equal to 1 in a finite number of steps.
The main proposition is that if you can find a contiguous part of the sequence that is strictly increasing, then you can always apply averaging such that the elements just adjacent to this sub-sequence also become a part of it, increasing its length.
To make myself clear, if the sequence was 14, 25, 11, 15, 17, 19, 21, 10, 9 (where the part in bold is the sub-sequence I’ve been talking about). The 10 present on right side and 25 on the left side of this are breaking the chain of increasing numbers. I claim that we can do averaging such that these 10 and 25 also become a part of the chain. I’ll call 25 and 10 the border numbers, and 11 and 21 as the guard numbers.
We do two steps.
Step 1:
Bring the border numbers very close to the guardian numbers by doing average on the (border, guardian) pair and changing the value of the border number. At the end of this step our sequence would look like 14, 11.001, 11, 15, 17, 19, 21, 20.999, 9
Step 2:
Now change the values of the guardian numbers by averaging the border number and the number adjacent to it in the chain (like 15 is adjacent to 11 and 19 is adjacent to 21).
After this the sequence would look like 14, 11.001, 13, 15, 17, 19, 20, 20.999, 9
Note how the length of the bold sequence has been increased. This is a general algorithm that I can apply to any sequence, not just the one I took in the example
So when we have a single adjacent pair such that A_i < A_{i+1} (i.e. increasing), we can always increase the length of this increasing sub-sequence successively and the full sequence will eventually be fully sorted.
This proves that the condition is sufficient. Now let’s prove it’s necessary.
Suppose there are no two elements such that A_i < A_{i+1} . This means that the sequence is non-increasing. It seems obvious why this should not be sortable, but we can prove it easily by induction (which is probably the uncoolest way, but everything else I think of seems to be hand-waving over some things.)
18 Likes
Bro step 1,did not understand it how did you change 2 to 11.001. Could you explain it once again
I dont think this question was easy in any way. Even I had found the result at end but the proving the result is quite tedious I would say.
3 Likes
Noice! I also thought of this but I was not sure at that time
1 Like
Yeah sorry about that, it was a typo. Instead of 2 it should have been 25 (or anything greater than 11). I hope you see now how I made 25 to 11.001
9 9 9 7 9 8.99
9 9 7.01 7 7.01 8.99
9 7.02 7.01 7 7.01 8.99
7.03 7.02 7.01 7 7.01 8.99
8.94 8.95 8.96 8.97 8.98 8.99
Answer Yes
2 Likes
I have one doubt that how is it possible to convert
7 2 4 1 6 8 3 9 into strictly increasing sequence as 7 > 2 and it will always remain greater than 2.
How can we make a chain of same numbers in this case 7 2 4 1 6 8 3 9 ?
7 > 2 how can this pair be made strictly increasing ?
Please can you explain this test case step wise using your method.
Thanks
We can still decrease 7.
We have (a,b) = 7,2.
a = (a+b)/2; //a now is 3.5 which was earlier 7
Again, a = (a+b)/2; //now a is 2.75
we will keep doing this infinite times and eventually a which once was 7 will now be shrinked to almost 2 (not exactly 2, but a value just greater than 2).
Still it will remain greater than 2 so how this sequence will become strictly increasing?
Thanks for replying.
In that case, 4 will make 2 to be 3.5 after some operations and you know how to proceed further. 
7 , 2 , 4 , 1 …
4.5 , 2 , 4 , 1 …
3.25 , 2, 4 , 1 …
3.25 , 3 , 4 , 1 …
3.25 , 3.5 , 4 , 1 …
Hi there, in the explanation it says for any case other than an array of decreasing order, its always possible to have a strictly decreasing array.
BUT what about this testcase arr = {7, 9, 10, 2, 5} here isn’t it impossible to have a strictly decreasing array ???
Hi there, in the explanation it says for any case other than an array of decreasing order, its always possible to have a strictly decreasing array.
BUT what about this testcase arr = {7, 9, 10, 2, 5} here isn’t it impossible to have a strictly decreasing array ???
can you help me in this case ?