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

Revision en4, by jha_saurav, 2020-04-13 16:38:03

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:

step-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.

Step-2. 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.

step-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)