Results 1 to 8 of 8

Thread: Facebook Hacker's Cup.

  1. #1
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default Facebook Hacker's Cup.

    Is anyone else doing the facebook hacker's cup competition?

    You can win $10,000..


    https://www.facebook.com/hackercup




    I got past 1 & 2.. 3 (still doing it) is confusing LOL..


    1 Was fairly easy..
    2 Required you to write a simple parser for smiley faces/brackets.
    3 Still doing it..

    This is just for the qualifier round.. Can't image the other rounds yet..


    1:

    Capture.PNG

    2:
    2.PNG

    3:
    3.PNG
    Last edited by Brandon; 01-26-2013 at 04:45 PM.
    I am Ggzz..
    Hackintosher

  2. #2
    Join Date
    Jan 2012
    Location
    Calgary, AB, Canada
    Posts
    1,819
    Mentioned
    5 Post(s)
    Quoted
    120 Post(s)

    Default

    I don't plan on doing it, but damn #3 don't have any clue of how I would do that
    Current Project: Retired

  3. #3
    Join Date
    Jun 2012
    Posts
    4,867
    Mentioned
    74 Post(s)
    Quoted
    1663 Post(s)

    Default

    That sounds fun, good luck!

    Win it for Villavu!

  4. #4
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    This doesn't look too hard, but I agree that the other rounds must be crazy. Here's how you get the next value:
    java Code:
    public static int nextValue(final int[] m) {
            int min = m[0];
            for (int i = 1; i < m.length; i++)
                if (m[i] < min)
                    min = m[i];
           
            int value = min + 1;       
            for (int i = 0; i < m.length; i++)
                if (m[i] == value) {
                    value++;
                    i = -1;
                    continue;
                }
           
            return value;
        }

    I may do the rest later just for shits and giggles, I'm not really interested in participating.

  5. #5
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Quote Originally Posted by Echo_ View Post
    This doesn't look too hard, but I agree that the other rounds must be crazy. Here's how you get the next value:
    java Code:
    public static int nextValue(final int[] m) {
            int min = m[0];
            for (int i = 1; i < m.length; i++)
                if (m[i] < min)
                    min = m[i];
           
            int value = min + 1;       
            for (int i = 0; i < m.length; i++)
                if (m[i] == value) {
                    value++;
                    i = -1;
                    continue;
                }
           
            return value;
        }

    I may do the rest later just for shits and giggles, I'm not really interested in participating.


    I'm not so sure that is correct for Question 3 .. It is only supposed to find the min in the last K elements of M array. Not the whole thing

    GetKnownValues gets all the value in the array M.

    Process is supposed to return value M[N - 1]. Only works for Case 1 of Questions 3. GetKnownValues is correct though.. Processing is wrong I think.

    C++ Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    #include <stdexcept>

    template<typename T>
    std::string ToString(T Type)
    {
        std::stringstream SS;
        SS<<Type;
        return SS.str();
    }

    template <typename T>
    T ToNumber(const std::string &Text)
    {
        std::istringstream SS(Text);
        T Result;
        return (SS >> Result ? Result : 0);
    }

    std::ostream& operator << (std::ostream& Str, const std::vector<int>& IA)
    {
        if (!IA.empty())
        {
            Str<<"[";
            for (std::size_t I = 0; I < IA.size() - 1; ++I)
            {
                Str<<IA[I]<<", ";
            }
            Str<<IA[IA.size() - 1]<<"]";
        }
        else
        {
            Str<<"[]";
        }
        return Str;
    }

    std::vector<std::string> ReadFileEx(const std::string& FileName, bool BinaryMode)
    {
        std::string Line;
        std::vector<std::string> Result;
        std::_Ios_Openmode OpenMode;
        if (BinaryMode)
            OpenMode = std::ios::in | std::ios::binary;
        else
            OpenMode = std::ios::in;

        std::ifstream File(FileName.c_str(), OpenMode);
        if (File.is_open())
        {
            while (std::getline(File, Line))
            {
                Result.push_back(Line);
            }
            File.close();
        }
        return Result;
    }

    std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
    {
        std::vector<std::string> Result;
        std::size_t Pos = StringToSplit.find_first_of(Delimiter);
        while(Pos != std::string::npos)
        {
            if(Pos > 0)
            {
                Result.push_back(StringToSplit.substr(0, Pos));
            }
            StringToSplit = StringToSplit.substr(Pos + 1);
            Pos = StringToSplit.find_first_of(Delimiter);
        }
        if(StringToSplit.length() > 0)
        {
            Result.push_back(StringToSplit);
        }
        return Result;
    }

    std::vector<int> StringsToIntegers(std::vector<std::string> Strings)
    {
        std::vector<int> Result;
        for (unsigned I = 0; I < Strings.size(); ++I)
        {
            Result.push_back(ToNumber<int>(Strings[I]));
        }
        return Result;
    }

    std::vector<int> GetKnownValues(std::vector<int> Numbers, std::vector<int> GeneratedNumbers, int &N, int &K)
    {
        N = Numbers[0];
        K = Numbers[1];
        std::vector<int> M(1);

        int A = GeneratedNumbers[0];
        int B = GeneratedNumbers[1];
        int C = GeneratedNumbers[2];
        int R = GeneratedNumbers[3];

        M[0] = A;

        for (unsigned I = 1; I < K; ++I)
        {
            M.push_back((B * M[I - 1] + C) % R);
        }

        return M;
    }

    int Process(std::vector<int> KnownValues, int N, int K)
    {
        int MinValue = *std::min_element(KnownValues.end() - K, KnownValues.end());

        for (int I = 0; I < K; ++I)
        {
            if (std::find(KnownValues.end() - K, KnownValues.end(), ++MinValue) == KnownValues.end())
            {
                break;
            }
        }

        if (KnownValues.size() < N)
        {
            KnownValues.push_back(MinValue);
            Process(KnownValues, N, K);
        }

        return KnownValues[N - 1];
    }



    int main()
    {
        std::stringstream Output;
        std::vector<std::string> Lines = ReadFileEx("TestInput.txt", false);
        int LineCount = ToNumber<int>(Lines[0]);

        if (LineCount < 1 || LineCount > 50)
            throw std::invalid_argument("ERROR! Invalid contraint.  Required: 1 <= T <= 50. Got: " + Lines[0]);


        int N = 0, K = 0;

        for (int I = 1, J = 1; I < LineCount * 2; I += 2, ++J)
        {
            std::vector<int> Known = GetKnownValues(StringsToIntegers(SplitString(Lines[I], " ")), StringsToIntegers(SplitString(Lines[I + 1], " ")), N, K);

            std::cout<<"Case #"<<J<<": "<<Process(Known, N, K)<<"\n\n";
        }

        return 0;
    }
    I am Ggzz..
    Hackintosher

  6. #6
    Join Date
    Jun 2007
    Location
    The land of the long white cloud.
    Posts
    3,702
    Mentioned
    261 Post(s)
    Quoted
    2006 Post(s)

  7. #7
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    But if k is constant, wouldn't the list just contain a bunch of duplicates after k? Like the example:
    m = { 2, 3, 0 }
    m[3] = 1

    Since k didn't change, and you don't consider the addition of 1 to the list for computing the next value, m[4] would just be 1 again. and etc.

  8. #8
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Quote Originally Posted by Echo_ View Post
    But if k is constant, wouldn't the list just contain a bunch of duplicates after k? Like the example:
    m = { 2, 3, 0 }
    m[3] = 1

    Since k didn't change, and you don't consider the addition of 1 to the list for computing the next value, m[4] would just be 1 again. and etc.

    After K elements, it begins to repeat itself.. but, they wanted the array to be of size N. I was so confused because the question was worded weird.

    Example (Posted by some guy):
    if k=10
    and the 10 first values are = 1,2,3,1,2,3,1,2,3,1
    the next will be : 0,4,5,6,7,8,9,10,2,3,1,.....

    "1,2,3,1,2,3,1,2,3,1" => lowest not used value : 0
    "2,3,1,2,3,1,2,3,1,0" => lowest not used value : 4
    "3,1,2,3,1,2,3,1,0,4" => lowest not used value : 5
    ....
    "2,3,1,0,4,5,6,7,8,9" => lowest not used value : 10
    "3,1,0,4,5,6,7,8,9,10" => lowest not used value : 2
    "1,0,4,5,6,7,8,9,10,2" => lowest not used value : 3
    "0,4,5,6,7,8,9,10,2,3" => lowest not used value : 1

    after, it will repeat at " 0,4,5,6,7,8,9,10,2,3,1,....." again and again

    Here's the thing.. When I read the file, I saw a number like:

    1000000000 100000
    999999999 1 999999999 1000000000


    Thus your array has to be 1000000000 elements in size and you must calculate the first 100000 elements..

    There are 20 cases like this in the file.. It took 14 minutes for my Computer to calculate it.. Thus I was not able to upload it within the 6 minute timeframe.. Instead, I just uploaded the source which worked on the Example input rather than the actual file..

    Hopefully, they accepted that.. I read somewhere that they expected us to do 3 with hash tables inorder to reach the 6 minute mark.. Still.. I'm sure it'd have taken almost as long.

    I used stack allocated arrays.. I'm pretty sure it'd take just as long with Heap arrays. Some guys got blue screens, out of memory errors, stack overflows, Kernel Panics.. Some attempted to use recursion ahahaha.

    Here is my final source which worked:

    C++ Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    #include <stdexcept>

    template<typename T>
    std::string ToString(T Type)
    {
        std::stringstream SS;
        SS<<Type;
        return SS.str();
    }

    template <typename T>
    T ToNumber(const std::string &Text)
    {
        std::istringstream SS(Text);
        T Result;
        return (SS >> Result ? Result : 0);
    }

    std::ostream& operator << (std::ostream& Str, const std::vector<int>& IA)
    {
        if (!IA.empty())
        {
            Str<<"[";
            for (std::size_t I = 0; I < IA.size() - 1; ++I)
            {
                Str<<IA[I]<<", ";
            }
            Str<<IA[IA.size() - 1]<<"]";
        }
        else
        {
            Str<<"[]";
        }
        return Str;
    }

    std::vector<std::string> ReadFileEx(const std::string& FileName, bool BinaryMode)
    {
        std::string Line;
        std::vector<std::string> Result;
        std::_Ios_Openmode OpenMode;
        if (BinaryMode)
            OpenMode = std::ios::in | std::ios::binary;
        else
            OpenMode = std::ios::in;

        std::ifstream File(FileName.c_str(), OpenMode);
        if (File.is_open())
        {
            while (std::getline(File, Line))
            {
                Result.push_back(Line);
            }
            File.close();
        }
        return Result;
    }

    std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
    {
        std::vector<std::string> Result;
        std::size_t Pos = StringToSplit.find_first_of(Delimiter);
        while(Pos != std::string::npos)
        {
            if(Pos > 0)
            {
                Result.push_back(StringToSplit.substr(0, Pos));
            }
            StringToSplit = StringToSplit.substr(Pos + 1);
            Pos = StringToSplit.find_first_of(Delimiter);
        }
        if(StringToSplit.length() > 0)
        {
            Result.push_back(StringToSplit);
        }
        return Result;
    }

    std::vector<int> StringsToIntegers(std::vector<std::string> Strings)
    {
        std::vector<int> Result;
        for (unsigned I = 0; I < Strings.size(); ++I)
        {
            Result.push_back(ToNumber<int>(Strings[I]));
        }
        return Result;
    }

    std::vector<int> GetKnownValues(std::vector<int> Numbers, std::vector<int> GeneratedNumbers, int &N, int &K)
    {
        N = Numbers[0];
        K = Numbers[1];
        std::vector<int> M(K);

        int A = GeneratedNumbers[0];
        int B = GeneratedNumbers[1];
        int C = GeneratedNumbers[2];
        int R = GeneratedNumbers[3];

        M[0] = A;

        for (int I = 1; I < K; ++I)
        {
            M[I] = (B * M[I - 1] + C) % R;
        }

        return M;
    }

    void Process(std::vector<int> &KnownValues, int K, unsigned N)
    {
        std::vector<int> Numbers(K);
        std::copy(KnownValues.end() - K, KnownValues.end(), Numbers.begin());
        std::sort(Numbers.begin(), Numbers.end());

        int MinValue = 0;
        for (unsigned I = 0; I < Numbers.size(); ++I)
        {
            if (Numbers[I] == MinValue)
            {
                ++MinValue;
                I = -1;
                continue;
            }
        }

        KnownValues.push_back(MinValue);
    }



    int main()
    {
        std::stringstream Output;
        std::vector<std::string> Lines = ReadFileEx("find_the_mintxt.txt", false);
        int LineCount = ToNumber<int>(Lines[0]);

        if (LineCount < 1 || LineCount > 50)
            throw std::invalid_argument("ERROR! Invalid contraint.  Required: 1 <= T <= 50. Got: " + Lines[0]);


        int N = 0, K = 0;

        for (int I = 1, J = 1; I < LineCount * 2; I += 2, ++J)
        {
            std::vector<int> Known = GetKnownValues(StringsToIntegers(SplitString(Lines[I], " ")), StringsToIntegers(SplitString(Lines[I + 1], " ")), N, K);
            for (int L = K; L < N; ++L)
                Process(Known, K, N);

            Output<<"Case #"<<J<<": "<<Known[N - 1]<<"\n\n";
        }

        std::cout<<Output.str();

        std::fstream File("Output.txt", std::ios::out);
        if (File.is_open())
        {
            File<<Output.str();
        }

        return 0;
    }
    Last edited by Brandon; 01-26-2013 at 11:53 PM.
    I am Ggzz..
    Hackintosher

Thread Information

Users Browsing this Thread

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

Posting Permissions

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