As I didn't find any blog regarding this. Let's discuss our approach here :)
Question A) Simple but tricky.
Question B) I used binary search on multiset to find the largest number <=2*ri.
Question C) My logic was to find the minimum index I (0<= I <=n) such that both sides should be a palindrome.
Question D) I thought to use some brute force and don't know why it passed partially.
Your approach will be welcome in the comment box. Thank you
POV: Why are you guys downvoting this blog? Why there is so much unnecessary hate? This blog helps people to get logic from their superior and some random guys just downvoting this blog. illogical
how many questions u solved?
3 and one partial.
nice bro ,thats good
can u pls share your brute force solution which passed partially.
Thanks in advance
In order to deliver pizza in m minutes, we could have so many paths. I iterate over possible ways and keep doing given operations for that path (if the way is valid) and update the answer as maximum.
i did same but got tle so thats why i want to see the implemenations.
Thanks
I did the same but Since there are four directions I think the time complexity for this would be 4^m and in worst case it will be 4^20( 10^12 )
Video Solutions for all problems.
u r doing really great.Congo
Can you please brief about the algorithm you used to solve C? loverBoUy
You can use hashing to solve the problem. If you note carefully we require the substring of minimum size $$$l$$$ such that the prefix of the first $$$l$$$ characters is a palindrome and the part remaining after after the prefix ( suffix of length $$$n-l$$$ ) is also a palindrome.
To quickly check if a given substring is palindrome we can use string hashing. Implementation.
Let s be some prefix of the original string such that
p = s + s + s + ... + s
then
1) s will be a palindrome
2) If we will add one more s at the end of the original string then it will still be a palindrome
so s will be our final answer
for finding s, we can see that, length(s) would be a factor of length(p) So we will iterate i from 1 to n and check if this much prefix can be our answer.
since i will be factor of n, the overall time complexity of the approach will be much lower
great approach...
Can you share your approach for second question, Binary search on multiset?
submission
thank you
Has anybody written a recursive dp (with a 3 states memoization) for Problem D1 that has passed? My recursive dp is giving TLE somehow. This is the link to code: http://pastie.org/p/6Dl2su1sXIuIAuUzUgdKSK
Your code is correct. However the choice of $$$-1$$$ as showing that a state is unvisited is problematic. For example assume that the cost of going left is $$$-1$$$ and we go left from our original position. In such a case our cost of reaching the left cell will be $$$-1$$$. When the recursion comes to that point again it will see that $$$memo[i][j][m]==-1$$$ and again calculate the cost for that cell. To avoid such a case we can fill the memo with a large value (like $$$-1e18$$$) will never be possible. Made this change and code passes the first subtask now.
This mistake will cost me tonight's sleep.
For C, the alternate solution in the editorial doesn't seem right. An counter-example is $$$ababa$$$. The answer for this is $$$ba$$$ which is not a generator of the input string.
ba is not a palindrome