Codenation

54

Can you tell the complexity of 4th one ?

55

O(nlogk) …(20 chars)

56

I used a completely different approach (The starting is same though), I find the frequency of all the numbers, then for all the numbers with an odd freq, I make a string out of it. Now I want to delete all the elements in the string p (My generated string) , from string a(Input string), Or I can say i need to find the minimum substring of a, that contains all the elements of p, This is a pretty common question and can be done using sliding window

For Eg:
a = 2113
p = 23
The minimum substring that contains 2 and 3 is 2113, I will print length of this substring - 1= 3

if
a = 2221131133
p = 23
The minimum substring containing 2 and 3 is 2113 (again) so I print len-1 = 3

Here’s the code, All TC passed https://ideone.com/40jjV3/

2 Likes
57

Can i get the problems link??

58

You don’t need segment tree for the last problem. You can solve it in O(n).
First create the Manacher array, and then precalculate the longest palindrome for each prefix (and suffix) with two pointers.

3 Likes
59

Yes.​​​​​​​​​​​​​​​​​

60

For the 3rd problem (the tree problem):-

The main observation is that you have to select 2 nodes (lets say i and j ) with the maximum number of set bits in their binary representation. Then the answer is just their sum (xi+xj, where x1 and x2 are the numbers of set bits in decimal rep. of i and j).
There are 2 ways of doing this :

  1. Either use Digit DP on the binary form of given N.
  2. Or we can make some useful observations and we see that the optimal answer will always be: min( d1+d2-1, d1+x-1, 2*d1-3), where d1 is the MSB of N, d2 is the 2nd most significant set bit in N, and x is the number of set bits in N.
61

What was your approach for 5th question?. I solved it using square root decomposition.

62

Can you please share your code? I thought of the same thing but couldn’t find any nice implementation of the same. Finally I solved the problem using trie. But I feel that BST would be the best solution to this problem.
Thanks

63

Just a doubt, Why do we need to find the smallest window which has all the odd frequency numbers, the question asks about finding the smallest difference between first and last removed numbers, shouldnt we try to find the smallest window having any two odd frequency numbers so that they can be the first and the last.

Ex. 223774775
your code will give 6 as it is difference between first 3 and last 5
but shouldnt the answer be 3, i.e. the difference between 3 and 4
like the first index be removed is 2 and then 8 and then 5 and so the difference between first and last indes removed is 5-2 = 3.
please tell me if i have misinterpreted the question.

65

First = leftmost, Last = Rightmost

66

holy shit !!! I misinterpreted it by miles :frowning:

67

Thanks for your help

68

yeah i solved two barely ;_;

70

I thought so too but I gave it a shot with normal BST and it worked… The test cases were such that it didn’t make it skewed, but yeah if I had gotten TLE I probably would’ve converted it to self balanced.

1 Like
71

Don’t have the code with me but basically I used X for ordering each node and stored another property on each node that stores the sum of Y values for the subtree rooted at that node

72

Wow ! Would you litterally code up a self balancing bst ?? ( I mean implementing Red-Black tree is quite tough ! ).

74

Haha, I had a RB Tree implementation locally that I would have modified for the question.

1 Like
75

Can someone provide me contest/problem link?

76

Ohh, no I have also done the same thing…that’s why I have passed only 4 test cases. I have wasted my so much time to debug this…
I didn’t realize that the first removal must be leftmost and last must be rightmost.