Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Thread: The Official Programming Thread

  1. #1
    vcs
    vcs is offline
    International Coach vcs's Avatar
    Join Date
    Apr 2009
    Location
    India
    Posts
    10,305

    The Official Programming Thread

    For any programming related problems you might come across..

    I'm struggling with one right now. I'm given a binary string and I need to find the largest substring with an equal number of 1s and 0s in it.

  2. #2
    International Captain ankitj's Avatar
    Join Date
    Jul 2010
    Location
    Hyderabad India
    Posts
    6,105
    There is an easy order n(n-1) ~ n^2 solution, but that might not be good enough for you?

  3. #3
    vcs
    vcs is offline
    International Coach vcs's Avatar
    Join Date
    Apr 2009
    Location
    India
    Posts
    10,305
    How do you do it.. is it using dynamic programming?

  4. #4
    International Captain ankitj's Avatar
    Join Date
    Jul 2010
    Location
    Hyderabad India
    Posts
    6,105
    Well, I'll just check all substrings which are nC2 in number. I will start from the largest and go down to smaller lengths in each iteration. So I check in this order :

    1 to n
    1 to n - 1
    2 to n
    1 to n - 2
    and so on

    Not the smartest way to do it but would it for you.


  5. #5
    vcs
    vcs is offline
    International Coach vcs's Avatar
    Join Date
    Apr 2009
    Location
    India
    Posts
    10,305
    Hmm... was hoping for something better than that. That algorithm popped into my mind, but there's got to be a better way.

  6. #6
    The Wheel is Forever silentstriker's Avatar
    Join Date
    Feb 2006
    Location
    USA
    Posts
    37,851
    So dire. I was a programmer for five years - the best day of my life will be the day I forget the Big O notation.
    Quote Originally Posted by KungFu_Kallis View Post
    Peter Siddle top scores in both innings....... Matthew Wade gets out twice in one ball
    "The future light cone of the next Indian fast bowler is exactly the same as the past light cone of the previous one"
    -My beliefs summarized in words much more eloquent than I could come up with

    How the Universe came from nothing

  7. #7
    International Captain ankitj's Avatar
    Join Date
    Jul 2010
    Location
    Hyderabad India
    Posts
    6,105
    Ya that was the lamest approach

    Here is another: convert 1s and 0s into 1s and -1s. Now do two steps:

    For the string from 1 to n create an array of partial sums indexed from 0 to n, with ith element in the array representing sum of binaries from 1 to i (0th element being left as 0).

    Now in this array of partial sums find duplicates that are farthest apart. If ith and jth partial sums are identical then your substring from i+1 to j has equal 0s and 1s

    First step is going to be order n. Depending on how complex second step is, this may or may not be a better approach

    EDIT: something tells me the two can be done simultaneously. Will get back if I can think.
    Last edited by ankitj; 29-04-2011 at 02:14 PM.

  8. #8
    International Captain ankitj's Avatar
    Join Date
    Jul 2010
    Location
    Hyderabad India
    Posts
    6,105
    We don't have to store partial sums actually. We can create a 2 dimensional array that stores the first and last occurrences of each possible partial sum result and also the difference between the two. As we run down the string calculating partial sums we just have to update the start and end point of that partial sum result.

    For example, consider a string of length 15:
    1 -1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1

    You will get a 2-d array like this:

    a(-1) = (3,9,6)
    a(0) = (0,10,10)
    a(1) = (1,13,12)
    a(2) = (12,14,2)
    a(3) = (15,15,0)

    This indicates that partial sum -1 occurs at 3rd and 9th positions which are 6 places apart and so on.
    a(1) has the largest difference (of 12). Therefore the desired largest substring is from 2 to 13.

    Creating those 2-D array and determining the max of differences are both order n. So overall algorithm is also order n (unless I have missed something).
    Last edited by ankitj; 29-04-2011 at 02:23 PM.

  9. #9
    Global Moderator Spark's Avatar
    Join Date
    Feb 2010
    Location
    A Blood Rainbow
    Posts
    32,501
    Doing a course on scientific computing aws. Useful, easy, and so ****ing boring. Ugh. Don't want to see another error formula in my life. And order(h to the whatever the **** it is) can go die in a fire.
    + time's fickle card game ~ with you and i +


    get ready for a broken ****in' arm

  10. #10
    vcs
    vcs is offline
    International Coach vcs's Avatar
    Join Date
    Apr 2009
    Location
    India
    Posts
    10,305
    When our professor droned on about computational complexity, and how to find the order(n to whatever the **** it is) for months on end, we used to struggle to see the point. For example, when they taught us about Strassen's Algorithm for Matrix Multiplication, one guy in class stood up and asked, why the hell are we learning about an algorithm that reduces the complexity from O(N^3) to to O(N^2.8), whoop de ****ing do. And here Intel are slaving their asses off to build better and better processors with higher clock speeds and multi-core architectures, blah blah. What's the point of all their hard work?

    But yeah, these tiny details become vitally important when the problem sizes become large.
    Last edited by vcs; 30-04-2011 at 02:17 AM.

  11. #11
    Global Moderator Spark's Avatar
    Join Date
    Feb 2010
    Location
    A Blood Rainbow
    Posts
    32,501
    It's very useful and important to know tbf. Only reason why I'm subjecting myself to such bone-dry yawnfests.

  12. #12
    Cricketer Of The Year Agent Nationaux's Avatar
    Join Date
    Jan 2011
    Location
    UK
    Posts
    9,809
    Hey guys, out of curiosity if I were to start my education as a programmer, what language would you recommend that I study first, or would I have to learn something else before trying to understand a programming language (I don't know anything about this field). I would like to learn visual basic because I want to become good at excel. Would I have to also improve my maths in order to do this or can I get by without. And how do I go about doing this, i.e. do I start reading particular books (what books) or take a particular course. Ideally would like someone from UK to answer this because they would understand the education system, but ideas will be welcomed from anyone who knows about the area.

    I recently completed my degree in Accounting and would like to one day specialise in programming accounting software, so it would be of course useful to learn how to programme.

    Thanks
    Last edited by Agent Nationaux; 30-04-2011 at 10:48 AM.

  13. #13
    vcs
    vcs is offline
    International Coach vcs's Avatar
    Join Date
    Apr 2009
    Location
    India
    Posts
    10,305
    Quote Originally Posted by Agent Nationaux View Post
    Hey guys, out of curiosity if I were to start my education as a programmer, what language would you recommend that I study first, or would I have to learn something else before trying to understand a programming language (I don't know anything about this field). I would like to learn visual basic because I want to become good at excel. Would I have to also improve my maths in order to do this or can I get by without. And how do I go about doing this, i.e. do I start reading particular books (what books) or take a particular course. Ideally would like someone from UK to answer this because they would understand the education system, but ideas will be welcomed from anyone who knows about the area.

    Thanks
    Agent, if you want to get into programming, I would suggest that you start with C or C++. You don't really have to worry much about programming language syntaxes and constructs right now. If you are comfortable working in one language, you will find it easy enough to move to another if and when you need to. Aptitude in this field usually is correlated to people who enjoy solving problems, and like Maths in general. If you are interested in Discrete Maths topics like number theory, set theory, permutations, combinations, counting problems and so on, chances are you'll enjoy programming.

    Once you've decided to get started, you can pick up any basic book on C or one of the vast tutorials available on the net, and try writing some simple programs to get acquainted with what is available to you, and how to translate the problem that you are trying to solve into the language. Getting to a stage where you can write simple programs is not difficult at all. Then you can let your own interest take you as deep as you wish to explore!

  14. #14
    Cricketer Of The Year Xuhaib's Avatar
    Join Date
    Nov 2005
    Location
    Karachi
    Posts
    9,506
    this thread is like my C++ class in uni, full of Indian curry with a random Pakistani and a white guy sprinkled here and there.

    I dropped from the course after 2 classes ftr.

  15. #15
    International 12th Man Quaggas's Avatar
    Join Date
    Jun 2009
    Location
    USA
    Posts
    1,683
    Quote Originally Posted by vcs View Post
    When our professor droned on about computational complexity, and how to find the order(n to whatever the **** it is) for months on end, we used to struggle to see the point. For example, when they taught us about Strassen's Algorithm for Matrix Multiplication, one guy in class stood up and asked, why the hell are we learning about an algorithm that reduces the complexity from O(N^3) to to O(N^2.8), whoop de ****ing do. And here Intel are slaving their asses off to build better and better processors with higher clock speeds and multi-core architectures, blah blah. What's the point of all their hard work?

    But yeah, these tiny details become vitally important when the problem sizes become large.
    Or if you can beat the other guy to the exchange by a couple of ns

Page 1 of 2 12 LastLast


Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. The Official Gareth Hopkins isn't terrible thread
    By Athlai in forum Cricket Chat
    Replies: 154
    Last Post: 26-11-2010, 06:21 AM
  2. The Official Bring Back Fiery Thread!
    By cover drive man in forum Off Topic
    Replies: 26
    Last Post: 29-08-2010, 01:53 AM
  3. Finally ! A Last Word Thread
    By SJS in forum Cricket Chat
    Replies: 22
    Last Post: 01-01-2010, 07:42 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •