link to the question: https://codeforces.net/contest/1339/problem/C
link to submission: https://codeforces.net/contest/1339/submission/76490327
After I read the question, I realised the following: 1. if a number of the array is smaller than the previous one, then we will add-in powers of 2 to make it greater than equal to the previous number; and we need to choose those seconds or those iterations only so that we get the minimum possible number that will be greater than equal to the previous number.
- having realised the above, I calculated the difference whenever a number was smaller than the previous one and simply found till when shall I add in powers of 2 so that the number gets greater than equal to the difference calculated(i.e 1+2+4+8+16......); do note here I have iterated in consecutive seconds, i.e if I got 5 seconds then it means it requires the previous 4 additions of powers of 2.
3.now the number which I got from the previous operation will not be the minimum number required at that position. so, to minimise I did the following: (i) first, if my difference was 12 then the number which I will get from step 2 will be 15(1+2+4+8) so I started removing numbers from beginning i.e(15-1-2-4-...) until my number was greater than 12(i.e the difference required). so I will get the minimum number to be added at that position which will be 12. (ii) now if my difference was 11 then the number which I will get from step 2 will be 15(1+2+4+8) now along with the above the process I will also calculate the minimum by directly removing only one element from the addition of powers of two, (i.e remove only 1 or 2 or 4 only one of them) so I will remove 4 from 15 using the following the process, therefore, the number I will get is 11 which needs to be added at that position. (iii) now note that using sub-process (ii) on the example given in sub_process(i) will get number 13(as we will remove only 2), and if we use sub_process(i) on the example given in sub_process(ii) will get number 12(as we will do
15-1-2). now in each of the example, we will take the minimum of the numbers obtained from each process.
now I don't why after thinking the algorithm so thoroughly I am getting a failed test case. So, please let me know which scenario is missing in my solution.
P.S: I have tried my best to explain what have I done in my code, that's why the blog is very lengthy and I have written my code in Python so that it will be intuitive for the reader to co-relate the code and the blog; so, please do give it a try and let me know the issue.
