JeevanJyot's blog

CodeChef Starters 73 (Rated till 6 Stars) — 11th January
By JeevanJyot, history, 16 months ago, In English

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!

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

»
15 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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$$$).

    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    greedy approach
    think about filling up the answer in bitwise

    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply