FIrst problem was pretty standard, can be solved by dfs and maintaing the ancestors nodes, although i got TLE in one of the subtasks.
The second problem was very interesting though, the max or value will definitely be the ors of all the array elements, now to choose the smallest subset, i couldn`t think of any good approach other than the testing all subsets, later in gfg i saw the same problem but there it is solved just like the subset sum problem with complexity of n^2 which i think will not fit here due to the value beign of order 10^5. How did you guys solve it ??
Oh god missed a great opportunity, could you share the procedure of applying, since I tried to Google but couldn’t find anything related to it and is there a way of getting notified about such events in the future. My college isn’t even aware about this, they want us to learn LaTeX and outdated syllabus FFS , feel like crying now : - (
Integer distribution can be solved by dp and Bit manipulation.
But I have dought in first question . I found a post whether the solution is greedy not passing all test cases …
The question wasn’t solvable with the given constraints … it was a variation of subset cover which is NP hard … I geuss you should raise a ticket to google to notify them of the same as many of us have also done.
Just btw : Due to weak test cases … just checking subsets of size 1 , 2 , 3 gives AC … which is another fallacy at google’s end
Would you mind elaborating on the explanation there or pointing to the core concepts being used. Also where does binary lifting come into the picture in this?
I didn’t give the test but these problems are very standard. The first one is O(T*N*100) using dfs+dp and second one can be solved by keeping which index is at the starting position.
