Saturday, October 23, 2010

Are you a TopCoder?

I haven't done a TopCoder algorithm problem for years. From what I remembered the 250-point level problems were a lot easier back then. I can't believe there are folks who can complete a such task within 15 minutes. I didn't time myself, but it took me about 4 hours to get this particular 250-point problem submitted. During my first attempt I tried searching all possible digits, but it didn't come out too well and it was difficult because I could not consider all the possible cases. After a few tries I knew there is got to be an easier approach. Since the problem is only interested in looking for the longest digits, I should start looking from the longest possible digits and if all the rules applied then I'm done. I started working through this greedy concept and still took me a few more tries and below is what I came up with.

Problem statement: SRM 192 DIV 1 250-point DigitMultiples
You are given two strings of digits, single and multiple. Your job is to find the length of the longest substring (which may be the whole string) of digits in single such that there is a corresponding substring (of the same length) in multiple which satisfies the following constraint. Each digit in the substring of multiple is the same exact integer multiple of the corresponding digit in the substring of single. So "48" is a multiple (4) of "12", but "72" is not a multiple of "36". Multiplication factors from 0 to 9 are possible. Leading zeros are *allowed* in single and multiple and all substrings.



class DigitMultiples {
    //Main rule logic
    private bool Rules(string subM, string subS) {
        int Factor;
        if (subS[0] == '0') {
            Factor = 0;
        } else {
            Factor = (subM[0] - '0') / (subS[0] - '0');
        }
        for (int i = 0; i < subM.Length; i++) {
            int iM = subM[i] - '0';
            int iS = subS[i] - '0';
            if (iS * Factor != iM) {
                if (Factor == 0 && iS != 0) {
                    Factor = iM / iS;
                    continue;
                }
                return false;
            }
        }
        return true;
    }
    //Feed all the possible digits from single and multiple
    private bool RuleHelper(string single, string multiple, int digit) {
        for (int m = 0; m + digit - 1 < multiple.Length; m++) {
            string subM = multiple.Substring(m, digit);
            for (int s = 0; s + digit - 1 < single.Length; s++) {
                string subS = single.Substring(s, digit);
                if (Rules(subM, subS)) {
                    return true;
                }
            }
        }
        return false;
    }
    //Search through string multiple using the longest possible digits
    public int getLongest(string single, string multiple) {
        int PossibleDigits;
        //Getting the longest possible digits
        if (multiple.Length < single.Length) {
            PossibleDigits = multiple.Length;
        } else {
            PossibleDigits = single.Length;
        }
        //Search from top down and quit once it is found
        for (int digit = PossibleDigits; digit >= 1; digit--) {
            if (RuleHelper(single, multiple, digit)) {
                return digit;
            }
        }
        return 0;
    }
}

No comments:

Post a Comment