We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This may sound like an odd complaint, but I feel the hardest test cases for this problem are not hard enough. Let me explain...
A very naive solution would generate all possible sets of A' and B', filter for A' | B' = C, then sort through to pick the ones which make no more than K changes and have minimal A' and B'. This may complete test case 0 in time but will time out for all the others.
A less naive solution to this would build a tree of all possible changes which satisfy A' | B' = C, then navigate the tree to find all solutions which make no more than K,the permitted number of changes, and from those pick the ones with minimal values of A' and B' This will solve test case 0 in the permitted time but time out for almost all the others.
There are several ways to optimise the tree building, some of which make for very complicated code. However, there are three simple optimisations which dramatically improve performance. And (in Haskell, at least), these are sufficient to pass all the tests.
But tree-building is not the most performant solution. With enough insight into the possible changes to A and B, there is a highly performant solution which is also very simple. I had just realised this (and begun to add the first bits of it to my code) when I made the final optimation to my tree building solution - which passed all the tests. This let me see the editorial, where that simple solution is in fact the one used by the creator of the challenge.
So now I almost feel as if I have cheated. Or been cheated (my only incentive now for writing the best solution is perfectionism).
I know that if certain bit combinations were predominant in (A,B,C) and K were high, tree building/traversal would be very expensive even with modestly sized input values. I think this challenge could be improved by adding those test cases, offering a 40 score for passing the current tests and 50 for passing all (or 50/60, say).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
A or B
You are viewing a single comment's thread. Return to all comments →
@nickasvanidze
This may sound like an odd complaint, but I feel the hardest test cases for this problem are not hard enough. Let me explain...
A very naive solution would generate all possible sets of A' and B', filter for A' | B' = C, then sort through to pick the ones which make no more than K changes and have minimal A' and B'. This may complete test case 0 in time but will time out for all the others.
A less naive solution to this would build a tree of all possible changes which satisfy A' | B' = C, then navigate the tree to find all solutions which make no more than K,the permitted number of changes, and from those pick the ones with minimal values of A' and B' This will solve test case 0 in the permitted time but time out for almost all the others.
There are several ways to optimise the tree building, some of which make for very complicated code. However, there are three simple optimisations which dramatically improve performance. And (in Haskell, at least), these are sufficient to pass all the tests.
But tree-building is not the most performant solution. With enough insight into the possible changes to A and B, there is a highly performant solution which is also very simple. I had just realised this (and begun to add the first bits of it to my code) when I made the final optimation to my tree building solution - which passed all the tests. This let me see the editorial, where that simple solution is in fact the one used by the creator of the challenge.
So now I almost feel as if I have cheated. Or been cheated (my only incentive now for writing the best solution is perfectionism).
I know that if certain bit combinations were predominant in (A,B,C) and K were high, tree building/traversal would be very expensive even with modestly sized input values. I think this challenge could be improved by adding those test cases, offering a 40 score for passing the current tests and 50 for passing all (or 50/60, say).