Friday, January 22, 2016

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Problem Statements:
https://www.facebook.com/hackercup/problem/582062045257424/

Solution:
We could solve the problem by testing all possible numbers when any 2 digits are swapped.
We swap position i and j for every possible i and j where 1<i<9 and 1<j<9, so the number of all possible combination is small enough for brute force attack.

Example codes:

            long T = inp.NextInt ( );
            for ( int t = 0; t < T; t++ )
            {
                long N = inp.NextLong ( );
                string sn = N.ToString ( );
                char[] cn = sn.ToCharArray ( );
                string ans = "";
                if ( N < 10 )
                {
                    ans = string.Format ( "{0} {1}", N, N );
                }
                else
                {
                    string snmin = sn;
                    string snmax = sn;
                    for ( int i = 0; i < sn.Length; i++ )
                    {
                        for ( int j = i + 1; j < sn.Length; j++ )
                        {
                            //swap then test
                            char[] cc = cn.ToArray ( );
                            char tmp = cc[i];
                            cc[i] = cc[j];
                            cc[j] = tmp;
                            string st = new string ( cc );
                            if ( st.CompareTo ( snmin ) < 0 && st[0] != '0' )
                                snmin = st;
                            if ( st.CompareTo ( snmax ) > 0 )
                                snmax = st;
                        }
                    }

                    ans = string.Format ( "{0} {1}", snmin, snmax );
                }

                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }


No comments:

Post a Comment