hari6988's blog

By hari6988, 10 years ago, In English
Hi ,

I cant think of a O(n) solution for this problem


Can anyone pls give me a hint ?

Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

By hari6988, 11 years ago, In English

Hi,
I am having a little difficulty in understanding how the values are inserted into the TreeMap in a sorted order. Take a look at this code in a class that implements comparable

public int compareTo(STR other)
{
   if(this.val==other.val) return this.team.compareTo(other.team);
  return this.val>other.val?-1:1;
}

I dont understand why -1 is returned when this.val>other.val (The problem requires that the objects be sorted in decreasing order of values). Also, what is returned by
return this.team.compareTo(other.team)  /* team is a String data

Also, the method compareTo is not called anywhere. So,where do the above return statements go to ? Does this occur implicitly whenever values are inserted into the TreeMap? Thanks for the help.

Read more »

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

By hari6988, 11 years ago, In English
Hi,

I am new to Dynamic programming and i came across this problem. I couldn't come up with a proper state for this problem. Can you please help me ?? The problem is as follows:

Suppose you are given three strings of English letters X = x1x2…xm, Y = y1y2…ym, Z = z1z2…zm+n. The string Z is a shuffle of X and Y if and only if Z can be formed by interspersing the characters from X and Y in a way that preserves the left-to-right ordering of the characters from X and Y respectively. For example, cchocohilaptes is a shuffle of chocolate and chips, but chcccochilatspe is not.

Find a DP algorithm to determine whether Z is a shuffle of X and Y .

Read more »

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

By hari6988, 11 years ago, In English
I was studying the Longest common substring problem using DP ...

LCS(s1--p, t1--q) = 1+ LCS(s1--p-1, t1--q-1) if s[p]=t[q]

                                 0 otherwise

This was the solution given in wikipedia... This would give an answer of 0 for the strings "to" and "tom" ... But, shouldnt it be 2 ?? the "to" matches with "to" in tom . But, it compares only the last character and gives the answer`

Read more »

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

By hari6988, 11 years ago, In English
Do you think there should be a seperate section where all forum activities are recorded ? In topcoder, u have seperate set of forums for discussing SRM questions, seperate section for seeking advice from other programmers, a section for general discussions, etc . I think there should be a similar thing in codeforces . It is very difficult to find a particular forum here. For example, i wanted to take a look at the editorial for round 71 , but found it very difficult. Search bar at the top is also not very comprehensive. It would be great if the site admins can take a look at this

Read more »

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

By hari6988, 11 years ago, In English

Hi,

Can someone tell me on what basis you decide that a naive solution will cause time exceeded error ? I have faced this problem quite a few times.

Read more »

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

By hari6988, 11 years ago, In English
Hi, guys ... This is my first blog ... I am completely new to algorithms ... I have just taken it up and I really love it ... I love searching for puzzles each day and try solving them... right now, i am very bad at it ... I hope to improve ASAP and be good one day ... cheers... A problem for u all so that u dont get bored ;) 

You are given a set S of n numbers. You must pick a subset S' of k numbers from S such that the probability of each element of S occurring in S' is equal (i.e., each is selected with probability k/n). You may make only one pass over the numbers. What if n is unknown?

Read more »

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