Блог пользователя JeevanJyot

Автор JeevanJyot, история, 22 месяца назад, По-английски

We invite you to participate in CodeChef’s Starters 73, this Wednesday, 11th January, rated till 6-stars (i.e. for users with rating $$$< 2500$$$)

Time: 8 PM — 11:00 PM IST

Joining us on the problem-setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to pro users.

Also, if you have some original and engaging problem ideas and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
22 месяца назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Minimum Or Path

I tried Dp dp[i] = minimum(arr[i] | (dp[i+1],dp[i+2].....dp[i+a[i]]))

I tried to make a binary trie(with keeping track of indices) to solve this, but was getting wrong answer for 3 testcases

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Because the optimal substructure does not hold.

    Consider $$$A=[100_2,111_2,111_2,111_2,10_2,100_2,1_2,10_2]$$$.

    The correct answer is $$$110_2(1->5->6->8)$$$,but your method will give $$$111_2$$$($$$dp[5]=11_2$$$).

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    greedy approach
    think about filling up the answer in bitwise

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    First of all, $$$answer$$$ will be atleast $$$A[1] | A[N]$$$. I define a boolean vector $$$killed$$$ (initialised to all $$$false$$$), where $$$killed[i] = true$$$ would represent that I am not allowed to use $$$i_{th}$$$ index in my path.

    Now, start from MSB($$$i = 19$$$ for this problem), if $$$i_{th}$$$ bit is already set in $$$answer$$$, then just continue.

    Else see if it is possible to make this bit as $$$0$$$ in our $$$answer$$$ : Iterate over all indices ignoring the ones which are already killed, set $$$killed[j] = true$$$ for all such $$$j$$$ such that $$$i_{th}$$$ bit is 1 in $$$A[j]$$$ and then, if it is possible to reach index $$$N$$$ from index $$$1$$$, then we can afford to lose those indices and can have $$$i_{th}$$$ bit in our $$$answer$$$ as 0!

    Checking for $$$i_{th}$$$ bit will take $$$O(N)$$$ time, hence total time complexity would be $$$O(N*log(MAXA_i))$$$.

    You can check out my submission Link.