This code appeared in the Facebook Hacker Cup 2012 – Qualification Round

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.

If product i has price Pi and weight Wi, then the following holds for product i+1:

Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)
You carefully calculated the parameters for the generator (P1, W1, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.

Input
The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P1, W1, M, K, A, B, C and D.

Output
Output T lines, one for each test case. For each case, output “Case #t: a b”, where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 1018
1 ≤ M, K ≤ 107
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 109

Sample Input
5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19

Sample Output
Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1

My Solution

My first approach was the naive/brute force one, as usual. It managed to solve the problem, but once N goes over 10,000 the algorithm becomes too slow.

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main(){
    unsigned long long int n;
    unsigned long long int t,i,j,x,y;
    unsigned int p1,w1,m,k,a,b,c,d;
    unsigned int *prices;
    unsigned int *weights;
    unsigned int bargains,terribles,notBargain,notTerrible;
    unsigned int refP,refW;

     cin >> t;

    for (i=0;i<t;i++){
        bargains = terribles = 0;

        cin >> n >> p1 >> w1 >> m >> k >> a >> b >> c >> d;

        prices = (unsigned int*)malloc(sizeof(unsigned int)*n);
        weights = (unsigned int*)malloc(sizeof(unsigned int)*n);

        prices[0]=p1;
        weights[0]=w1;

        if (n==1){
            bargains = 1;
            terribles = 1;
        }

        else{
            for (j=1;j<n;j++){
                prices[j] = (((a*prices[j-1])+b)%m)+1;
                weights[j] = (((c*weights[j-1])+d)%k)+1;
            }

            for (x=0;x<n;x++){
                refP=prices[x];
                refW=weights[x];
                notBargain = notTerrible = 0;
                for (y=0;y<n;y++){
                    if (x==y)
                        continue;
                    if ((prices[y]<refP&&weights[y]<=refW)||(weights[y]<refW&&prices[y]<=refP)){
                        notBargain = 1;
                        if (notTerrible)
                            break;
                    }
                    if ((refP<prices[y]&&refW<=weights[y])||(refW<weights[y]&&refP<=prices[y])){
                        notTerrible = 1;
                        if (notBargain)
                            break;
                    }

                }
                if (notBargain==0)
                    bargains++;
                if (notTerrible==0)
                    terribles++;
            }
        }

        cout << "Case #" << i+1 << ": " << terribles << " " << bargains;
        if (i<t-1)
            cout << endl;

    }

    return 0;
}

Since I am not sure what kind of numbers the input will use I worked on a faster algorithm. The basic idea is the following: I noticed that after a while (i.e., for n>1000) the sequence of products becomes stable, and the number of bargains and terrible deals grow at fixed intervals. So my second program calculates those intervals and apply it manually in case N is very large. It improved the running time considerably:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

void findvalues(unsigned int n,unsigned int *currentBargains, unsigned int *currentTerribles, unsigned int p1, unsigned int w1, unsigned int m, unsigned int k, unsigned int a,unsigned int b, unsigned int c, unsigned int d){
    unsigned int *prices;
    unsigned int *weights;
    unsigned int bargains,terribles,notBargain,notTerrible;
    unsigned int refP,refW;
    unsigned int j,x,y;

    bargains = terribles = 0;

    prices = (unsigned int*)malloc(sizeof(unsigned int)*n);
    weights = (unsigned int*)malloc(sizeof(unsigned int)*n);

    prices[0]=p1;
    weights[0]=w1;

    for (j=1;j<n;j++){
        prices[j] = (((a*prices[j-1])+b)%m)+1;
        weights[j] = (((c*weights[j-1])+d)%k)+1;
    }

    for (x=0;x<n;x++){
        refP=prices[x];
        refW=weights[x];
        notBargain = notTerrible = 0;
        for (y=0;y<n;y++){
            if (x==y)
                continue;
            if ((prices[y]<refP&&weights[y]<=refW)||(weights[y]<refW&&prices[y]<=refP)){
                notBargain = 1;
                if (notTerrible)
                    break;
            }
            if ((refP<prices[y]&&refW<=weights[y])||(refW<weights[y]&&refP<=prices[y])){
                notTerrible = 1;
                if (notBargain)
                    break;
            }

        }
        if (notBargain==0)
            bargains++;
        if (notTerrible==0)
            terribles++;
    }

    *currentBargains=bargains;
    *currentTerribles=terribles;

    free(prices);
    free(weights);

    return;

}

int main(){
    unsigned long long int n,initialNumber,count;
    unsigned long long int t,i,j,x,y,h;
    unsigned int p1,w1,m,k,a,b,c,d;
    unsigned int *prices;
    unsigned int *weights;
    unsigned long long int bargains,terribles,notBargain,notTerrible;
    unsigned int refP,refW;
    unsigned int bargainResults[500],terribleResults[500], currentBargains,currentTerribles;
    unsigned long long int baseB, baseT,variation,initialValue;

     cin >> t;

    for (i=0;i<t;i++){
        bargains = terribles = 0;

        cin >> n >> p1 >> w1 >> m >> k >> a >> b >> c >> d;

        if (n==1){
            bargains = 1;
            terribles = 1;
        }

        else if (n<2000){
            prices = (unsigned int*)malloc(sizeof(unsigned int)*n);
            weights = (unsigned int*)malloc(sizeof(unsigned int)*n);

            prices[0]=p1;
            weights[0]=w1;

            for (j=1;j<n;j++){
                prices[j] = (((a*prices[j-1])+b)%m)+1;
                weights[j] = (((c*weights[j-1])+d)%k)+1;
            }

            for (x=0;x<n;x++){
                refP=prices[x];
                refW=weights[x];
                notBargain = notTerrible = 0;
                for (y=0;y<n;y++){
                    if (x==y)
                        continue;
                    if ((prices[y]<refP&&weights[y]<=refW)||(weights[y]<refW&&prices[y]<=refP)){
                        notBargain = 1;
                        if (notTerrible)
                            break;
                    }
                    if ((refP<prices[y]&&refW<=weights[y])||(refW<weights[y]&&refP<=prices[y])){
                        notTerrible = 1;
                        if (notBargain)
                            break;
                    }

                }
                if (notBargain==0)
                    bargains++;
                if (notTerrible==0)
                    terribles++;
            }

            free(prices);
            free(weights);
        }

        else{
            for (int z=0;z<500;z++){
                findvalues(z+1000,&currentBargains,&currentTerribles,p1,w1,m,k,a,b,c,d);
                bargainResults[z]=currentBargains;
                terribleResults[z]=currentTerribles;
            }

            initialValue = bargainResults[0];
            variation = 0;

            for (h=0;h<500;h++){
                if (initialValue!=bargainResults[h]){
                    initialValue=bargainResults[h];
                    break;
                }
            }

            initialNumber = 1000 + h;
            baseB = bargainResults[h];

            for (;h<500;h++){
                if (initialValue!=bargainResults[h])
                    break;
                variation++;
            }

            count = 0;
            while (initialNumber<=n){
                if (count==variation){
                    baseB++;
                    count=0;
                }
                initialNumber++;
                count++;
            }

            bargains=baseB;

            initialValue = terribleResults[0];
            variation = 0;

            for (h=0;h<500;h++){
                if (initialValue!=terribleResults[h]){
                    initialValue=terribleResults[h];
                    break;
                }
            }

            initialNumber = 1000 + h;
            baseT = terribleResults[h];

            for (;h<500;h++){
                if (initialValue!=terribleResults[h])
                    break;
                variation++;
            }

            count = 0;
            while (initialNumber<=n){
                if (count==variation){
                    baseT++;
                    count=0;
                }
                initialNumber++;
                count++;
            }

            terribles=baseT;

        }

        cout << "Case #" << i+1 << ": " << terribles << " " << bargains;
        if (i<t-1)
            cout << endl;

    }

    return 0;
}

It turns out that even this version was not fast enough, as it didn’t solve the (huge) input file. I am guessing one would need to be able to figure out the number of bargains and terrible deals from the formulas alone, without the need to generate all or part of the products.

Good thing I solved the other two problems, so I managed to qualify anyway.