Test Case Fails in problem C.Powered Addition of Round 633(Div 2)

Revision en3, by jha_saurav, 2020-04-13 16:36:28

link to the question: https://mirror.codeforces.com/contest/1339/problem/C

link to submission: https://mirror.codeforces.com/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.
  1. 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English jha_saurav 2020-04-13 16:39:27 110
en4 English jha_saurav 2020-04-13 16:38:03 15
en3 English jha_saurav 2020-04-13 16:36:28 8
en2 English jha_saurav 2020-04-13 16:35:54 32
en1 English jha_saurav 2020-04-13 16:34:50 2768 Initial revision (published)