loverBoUy's blog

Google kickstart round E| Discussion
By loverBoUy, history, 20 months ago, In English

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

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how many questions u solved?

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    3 and one partial.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      nice bro ,thats good

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u pls share your brute force solution which passed partially.

      Thanks in advance

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i did same but got tle so thats why i want to see the implemenations.

          Thanks

          → Reply
        • »
          »
          »
          »
          »
          20 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 )

          → Reply
»
20 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Video Solutions for all problems.

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you please brief about the algorithm you used to solve C? loverBoUy

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share your approach for second question, Binary search on multiset?

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply