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:
- Contest Admins: Jeevan JeevanJyot Jyot Singh, Lavish lavish315 Gupta
- Setters: Jeevan JeevanJyot Jyot Singh, Chaithanya Dragonado Shyam D, Stuart cstuart Lim, Zobayer Zobayer_Abedin Abedin, Harasees harasees_singh Singh, Dilshodbek DilshodbekX Khujaev
- Testers: Manan mexomerf Grover, Jatin rivalq Garg
- Statement Verifier: Jeevan JeevanJyot Jyot Singh
- Video Editorialists: Garvit garvitvirmani0 Virmani, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc
- Text Editorialists: Nishank IceKnight1093 Suresh
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!
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
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$$$).
greedy approach
think about filling up the answer in bitwise
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.