sourabh912's blog

By sourabh912, 10 years ago, In English

I am trying to solve Autocomplete Problem and implementing trie solution for it. I am getting segmentation fault when the length of the input string is 10^6. It seems to be a out of memory issue and I am not able to figure out where I am going wrong. The link to the solution is here . Please help !!

Thanks

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By sourabh912, 10 years ago, In English

Can anyone please explain the approach to solve 295B - Greg and Graph. It is not very clear from the editorial.

Thanks

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By sourabh912, 10 years ago, In English

Hi All,

I came across the following problem recently and could not figure out an efficient way to solve it (other then backtracking). Can anyone please help.

Problem Statement:

A circular cake has 3*N slices. Each slice has a size given. Person X, on his birthday, has to eat the whole cake along with his friends Y and Z. Because its X's birthday, he is made to choose a slice everytime, and the slice immediate to the left and right of what X has picked will be picked by Y and Z. What is the maximum cake X can eat?
Given: An array representing the cake slice size.

Example 1: Input: {4,8,3} Output : 8
Explanation: X will simply pick 8

Example 2: Input: {6,11,14,22,20,3} Output: 34
Explanation: X will pick 14 & 20 sized slices

Example 3: Input: {14,11,6,3,22,20} Output: 36
Explanation: X will pick 14 & 22 sized slices.

Note: X cannot pick 14 & 20 as they are adjacent.

Thanks

Full text and comments »

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

By sourabh912, 12 years ago, In English

Hi All,

I am trying this problem. I think it can be solved using Dynamic Programming with bitmasking. Please explain how to approach this problem. I have been able to come up with the following solution but not sure if I am thinking in the right direction.

1) With bitmasking I will look at all the possible combinations of pizzas(from i=1 to i=1<<n).

2) Solution for say i=10010011(written in binary) will be min(solution for (00010011),solution for (10000011),solution for (10010001),solution for (10010010)). When finding solution of 10010011 from 00010011, I will check if the discount are available from the pizzas that are set to 1 in 00010011 and will avail maximum discount possible. For all this I am using 1-D array.

Thanks

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it