aMitkvikram's blog

By aMitkvikram, history, 6 months ago, In English,

977D — Divide by three, multiply by two

  1. We can see that all numbers in given sequence are distinct. since all numbers in sequence are of the form . Hence if ai = aj then = = 2x - m = 3y - n which is not possible because any power of 2 will be an even number and any power of 3 will be an odd number.

  2. if there exists in sequence then 2 * ai can not be in sequence and vice versa. We can prove it using contradiction. Suppose there is a number ai such that both and 2 * ai exists in sequence. by little bit of tricks this = , this again is not possible by same argument as above, we just have to change the order of exponents.

  3. Hence for each ai in sequence we see if or 2 * ai is present(remember that only one of them can be present). Now if there is any ai such that both and 2 * ai is not in sequence then this should be an. if there is any such ai that for all 0 ≤  j ≤ n:   ≠  ai AND 2 * ai  ≠  ai, then this is a1.

  4. Once you have got a1, you keep on producing sequence just by doing binary search for and 2 * ai (remember only one of them is present so once you find it you print it).

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aMitkvikram (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you explain your 1st statement ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have updated the first statement. Note that any power of 2 will be even and any power of 3 will be odd, hence (power of 2) can not be equal to (power of 3).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aMitkvikram (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/977/submission/38108720 I wrote a simple comparator function to sort the array. Math is similar.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are many ways to solve this problem but your solution is concise. I solved it using dfs.