TopCoder SRM 508 DIV2 1000 problem

I tried to solve 1000-point problem in SRM 508 DIV2 this morning.

I tried to use permutations and some math formula to solve it,  but failed miserably.
I ended up looking up a match editorial, and realized there was much easier and faster solution.

Here is the problem statement.

Problem Statement
	You're given ints N and R. Count the number of sequences A0, A1, ..., AN-1 such that each Ai is an integer satisfying 0 ≤ Ai ≤ R and A0 + A1 + ... + AN-1 = A0 | A1 | ... | AN-1. The '|' symbol stands for bitwise OR of the operands. Return the number of such sequences modulo 1,000,000,009.
Definition
	Class: YetAnotherORProblem2 Method: countSequences Parameters: int, int Returns: int Method signature: int countSequences(int N, int R) (be sure your method is public)
Notes
-	If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.
Constraints
-	N will be between 2 and 10, inclusive.
-	R will be between 1 and 15000, inclusive.
Examples
0)
	2 2 Returns: 7 The possible sequences are: {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}.
1)
	2 3 Returns: 9 Now we can also have {0,3} and {3,0}.
2)
	3 3 Returns: 16
3)
	7 1023 Returns: 73741815

Logic.

The first thing to notice is that we have to meet condition

(sum of all sequences ) equals ( result of OR operation over all sequences).

This can be interpreted "each sequence should have different bits set. They never should share any same bit set." Let's call it Rule #1

For example,

given R = 3,  its binary representation is (11).

Possible combinations are

(2,1) ==> ( (10), (01) )

(3,0) ==> ( (11), (00) )

Invalid combinations are

(3,1) ==> ((11), (01))  because both 3 and 1 share the first set bit (counting from the least significant bit).

The second thing to notice is that the highest bit that R will ever use is 13 (indexed from 0), because constraint states that R <= 15000.

This tells that number of bits are small enough to iterate through them and count possible outcomes.

Since we concluded that this is a counting problem, we need to define "state" and "recurrence" 

State can be set as

mem[col][n]

= number of ways to place bits when we have "col" number of columns left to set

and there are "n" number of rows that are still equal to R.

Then our recurrence should take (col, n) as input and output some number.

It will look like

long long rec(int col, int n)

Let's define recurrence.

We will start by n == N, meaning all rows are equal to R at current state.

We will iterate bits from left to right (from the most significant to least significant), and decide how to set current bit for N rows.

To be specific, for each bit we will do one of following

option 1) Pick one row and set its current bit to 1. According to rule #1, bits of all other rows should be set to 0.

option 2)Set bits of all rows to 0

So, our recurrence call will look something like

rec(col, n) calls rec(col-1, z) where z <= n, because number of rows whose values are equal to R decreases or stays the same.

Since our recurrence guarantees that value of col decrease by one every time, it will reach the base case.

Now, let's look at our base case.

Base case:

If no more columns to set (col == 0), and all previous columns are set correctly, there is only one possible result ( = current bit shape). So return 1

We start our recurrence by setting n == N , meaning we have N rows that are equal to R.

We will go through each column(bit) from right to left (from most significant to least significant), and count ways to set bits for N rows.

Let bool isZero = true if current bit of R is set to 0, and false otherwise.

If (n == N and isZero)

We cannot set any bit to 1, because that will make a sequence bigger than R, which is forbidden in problem statement.

So we call rec(n-1, n) ==> Move to the next bit, and all rows are still equal to R

If( n == N and not isZero)

We have two options.

1) Use 0 in all bits of this column, making all the rows smaller than R. This will also make n = 0, because no row is equal to R anymore.

==> rec(col-1, 0)

2) Use 1 in one of N rows. According to Rule #1, all other rows must have 0 in that bit.

This will also make the row whose current bit is set to 1  the only row whose value equal to R.

And you can choose any one of N rows for this.

==> N * rec(col-1, 1)

By  anlyzing n == N, we know now that n will be one of three values : 0,1, N

We also know that this recurrence will end at most 13 steps, because the highest bit R can have is 13 and col decrease by 1 at each step.

If(n == 1 and isZero)

1) We can only set bit to 1 to (N-1) rows whose value is already smaller than R.

=> (N-1) * rec(col-1, 1);

2) We don't set any bit to 1, keeping our current bit shape

=> rec(col-1, 0)

if(n == 1 and not isZero)

1) We can set bit to 1 to the only row whose value is still equal to R.

=> rec(col-1, 1)

2) We set bit to 1 to one of (N-1) other rows whose values are already smaller than R. This will also make the value of the row whose value is currently equal to R now smaller than R, because its current bit has to be set to 0 according to rule #1.

=> (N-1) * rec(col-1,0)

3) We set the current bit to 0 to all N rows. This will make the value of the row whose value is equal to R now smaller than R.

=> rec(col -1, 0)

if(n==0)

If n== 0, no row has value eqaul to R. So isZero does not affect our count.

1) We can set bit to 1 to one of (N) rows whose value is smaller than R.

 => N * rec(col-1, 0)

2) we set all bit to 0 to all N rows.

=> rec(col-1, 0)

Follow is source code ( It passed system test.)

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <string>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

using namespace std;

#define REP(i,a,b) for(int i=a; i < b; i++)

#define REPE(i, a, b) for(int i=a; i <=b; i++)

int INF = numeric_limits<int>::max();

int nINF = numeric_limits<int>::min();

typedef long long ll;

class YetAnotherORProblem2 {

public:

int countSequences(int, int);

};

ll mem[15][11];

int N;

int R;

int mod = 1000000009;

ll rec(int col, int numEqualRows)

{

    ll& res = mem[col][numEqualRows];

    

    if(res != -1) return res;

    if(col == 0)

    {

        res = 1;

    }

    else

    {

        res = 0;

        bool isZero = ( (R & (1<<(col-1))) == 0);

        if(numEqualRows == N)

        {

            if(isZero)

                res = rec(col-1, numEqualRows) % mod;

            else

            {

                res = rec(col-1, 0);

                res += N * rec(col-1, 1);

            }

        }

        if(numEqualRows == 1)

        {

            if(isZero) res = rec(col-1, 1) + (N-1) * rec(col-1, 1);

            else res = rec(col-1, 1) + rec(col-1, 0) + (N-1) * rec(col-1, 0);

        }

        

        if(numEqualRows == 0)

        {

            res = rec(col-1, 0);

            res += N * rec(col-1, 0);

        }

    }

    res %= mod; 

    return res;

}

int YetAnotherORProblem2::countSequences(int _N, int _R) {

    N = _N;

    R = _R;

    memset(mem, -1, sizeof(mem));

    

    return rec(14, N);

}

Google Code Jam Practice

I've never participated in Google Code Jam before, but I decided to participate in the contest this year.

It will be held in March , so I have about a month to prepare.

I went to :  http://code.google.com/codejam/

and read explanations about the contest, and clicked "Practice and Learn."

I started with the easiest problem , as google suggested.

The problem I solved was called "Reverse String." Link : http://code.google.com/codejam/contest/351101/dashboard#s=p1

All I had to do was

1. Receive a string.

2. Reverse the order of the word (but keep the order of each word. That is, do not turn abcd to dcba.)

For example, given input "abcd def ghi"

output "ghi def abcd"

The algorithm itself was not hard. However, it was difficult for me to read and write to files because I have little experience in it.

I remember learning file input/output in shell (Linux) environment, so I assumed it would be possible to use the commands to give inputs to and receive outputs from my program. It worked.

This is how I solved Reverse String.

Assume you are at directory

/Desktop/GoogleCodeJam/

The current directory has two files

1. MyProgram.cpp

2. input.txt

Run following commands in your shell

#1  g++ MyProgram.cpp -o MyProgram.out   

 ===> compiles MyProgram.cpp file and make an executable file named "MyProgram.out"

#2 cat input.txt | ./MyProgram.out > result.txt

===>

command "cat input.txt" outputs all contents in input.txt to standard output.

"| ./MyProgram.out" runs MyProgram.out using data from the standard output.

> result.txt stores all output from MyProgram.out to result.txt

And below is my source code for "ReverseString"

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <string>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

using namespace std;

#define REP(i,a,b) for(int i=a; i < b; i++)

#define REPE(i, a, b) for(int i=a; i <=b; i++)

int INF = numeric_limits<int>::max();

int nINF = numeric_limits<int>::min();

typedef long long ll;

int main()

{

int N;

cin>>N;

cin.ignore();

for(int i=0; i < N; i++)

{

string str;

getline(cin, str);

stringstream ss;

ss<<str;

string word;

string ans = "";

while(ss>>word)

ans = word + " " + ans;

ans.erase(ans.size() - 1);

cout<<"Case #"<<(i+1)<<": "<<ans<<endl;

}

    return 0;

}

TopCoder SRM531 DIV2

DIV2 - 250
Class : UnsortedSequence
Method : getUnsorted
Simple enough.
Approach.
1. sort the array in ascending order
2. Check from the last element, and find a second largest element.
3. Let the index of the second largest element i. Switch arr[i] with arr[i+1]

class UnsortedSequence {

public:

vector <int> getUnsorted(vector <int>);

};

vector <int> UnsortedSequence::getUnsorted(vector <int> s) {

vector<int> emp;

    

    int N = s.size();

    if(N == 1) return emp;

    

    sort(s.begin(), s.end());

    if(s[0] == s[N-1]) return emp;

    

    for(int i = N-2; i >= 0; i--)

        if(s[N-1] != s[i])

        {

            swap(s[i+1], s[i]);

            return s;

        }

    return emp;

}

DIV2 - 500

Class : NoRepeatPlaylist

Method : numPlaylists

There are two approaches, both of which are used during the contest.

One was used by _peanut (http://community.topcoder.com/stat?c=problem_solution&rm=311364&rd=14724&pm=11774&cr=23010876)

and another was used by vexorian (http://community.topcoder.com/stat?c=problem_solution&rm=311312&rd=14724&pm=11774&cr=22652965)

Although _peanut's solution looks simpler and easier to code once you understand dp relation, I prefer vexorian's approach because

1. His approach is simpler to understand.

2. His approach is easier to code.

_peanut's approach

Logic

     1 <= i <= P   , 1 <= j <= N

     dp[i][j]

     = number of ways to make a playlist whose length == i using

     j different songs

     

     = add a new song + add an already added song

     

     = (number of ways to make a playlist whose length == (i-1) using

     (j-1) different songs) * (number of avilable new songs)

     

     + (number of ways to make a playlist whose length == (i-1) using

     j different songs) * (number of already added songs whose 

     previously appearance is at least M songs away from position j)

     

     =dp[i-1][j-1] * (N - (j - 1)) 

     + dp[i-1][j] * max(j-M, 0)

     

     Ans

     = dp[P][N]

     = number of ways to make a playlist whose length == P

     using N different songs

     

     It is hard to understand max(j-M,0) at first sight.

     j is the number of different songs used at position[1...i-1].

     We want to add one of songs from postion[1..i-1] to position i.

     

     If M == 0, we can use any one of j songs.

     Let's see what happens when M == 1.

     This means we cannot use songs from position (i-1).

     Any one of j songs can be at that position.

     So we can use only (j - 1) songs.

     Expand this logic to M == M, and we can use (j-M).

     

     Notice that if M >= j, we cannot add any existing song to position i

     because we have not used enough different songs.

     

     Base

     dp[0][0] = number of ways to make an empty playlist using 0 song.

     = 1

Actual code

int NoRepeatPlaylist::numPlaylists(int N, int M, int P) {

    ll dp[P+1][N+1];

    

    memset(dp, 0, sizeof(dp));

    

    dp[0][0] = 1ll;

    

    for(int i = 1; i <= P; i++)

        for(int j = 1; j <= N; j++)

            dp[i][j] = ( (dp[i-1][j-1] * (N - (j-1))) % mod + (dp[i-1][j] * max(j-M,0)) % mod ) % mod;

    

    return dp[P][N];

    

}

vexorian's approach

Logic

He used classic dynamic programming approach : recursive function + memoizattion.

Define recursion

long long rec(int idx, long long extra, long long mustPlay)

= If you are choosing (idx)th song, 

and have "extra" number of already played songs to choose from, 

and "mustPlay" number of not-played songs to choose from,

how many ways can you make playlist?

Memoization

mem[idx][extra][mustPlay] = result of rec(idx, extra, mustPlay)

Code

 typedef long long ll;

class NoRepeatPlaylist {

public:

int numPlaylists(int, int, int);

};

ll mod = 1000000007;

ll mem[101][101][101];

int last;

int margin;

ll rec(int idx, ll extra, ll mustPlay)

{

    ll& res = mem[idx][extra][mustPlay];

    if(idx == last+1)

    {

        //successfully played all songs

        if(mustPlay == 0)

            return 1ll;

        //should play all songs at least once. Unsuccessful

        return 0ll;

    }

    if((idx - 2) >= margin) extra+=1ll;

    

    if(res == -1)

    {

        res = 0;

        if(mustPlay > 0)

        {

            res = (res + mustPlay * rec(idx+1, extra, mustPlay-1)) % mod;

        }

        if(extra > 0)

        {

            res = (res + extra *rec(idx + 1, extra - 1 , mustPlay)) % mod;

        }

    }

    return (res % mod);

}

int NoRepeatPlaylist::numPlaylists(int N, int M, int P) {

last = P;

    margin = M;

    memset(mem, -1, sizeof(mem));

    return rec(1, 0ll, (ll)N);

}

DIV2 - 1000

Class : KingdomReorganization

Method : getCost

Logic

We need to build a MST out of the given tree(s) defined by vector<string> kingdom.

So in a sense, we are building a MST.

However, the MST we want needs to follow below rule

: Always prefer keeping existing edges (defined by kingdom[i][j] == '1')  to building new edges.

So, assuming we are building a MST from scratch (with no edges at all), how can we force our MST to use edges defined by kingdom?

We can do it by setting cost of existing edges negative, which will be always lower than building new edges and therefore force any greedy algorithm to choose existing edges.

So setting cost of existing edges negative will give us MST we want.

However, how do we cover the cost of going from" the given tree defined by vector<string> kingdom " to an empty MST? In other words, above procedure will destroy all existing roads and rebuild a few of them, and rebuilding sounds like a waste because we are wasting cost of (destroy[i][j] + build[i][j]) when we should be wasting 0 cost by not destroying it in the first place.

We can solve this issue by setting build[i][j] = -(destroy[i][j]).

I will use Kruskal's algorithm to solve this.

class KingdomReorganization {

public:

int getCost(vector <string>, vector <string>, vector <string>);

};

struct edge

{

    int from;

    int to;

    int cost;

    edge(int f, int t, int c): from(f) , to(t), cost(c) {}

};

int getEdgeCost(char ch)

{

    if('A' <= ch && ch <= 'Z')

        return (ch - 'A');

    if('a' <= ch && ch <= 'z')

        return ((ch - 'a') + 26);

    cout<<"This line should never be reached"<<endl;

    return -100;

}

bool sortEdge(edge a, edge b)

{

    if(a.cost < b.cost) return true;

    return false;

}

int KingdomReorganization::getCost(vector <string> kingdom, vector <string> build, vector <string> destroy) {

    int N = kingdom.size();

    int destructCost = 0;

    int createCost = 0;

    

    vector<edge> edges;

    REP(i,0,N)

    REP(j,(i+1),N)

    {

        if(kingdom[i][j] == '1')

        {

            destructCost += getEdgeCost(destroy[i][j]);

            edges.push_back(edge(i,j,-(getEdgeCost(destroy[i][j]))));

        }

        else

        {

            edges.push_back(edge(i,j, getEdgeCost(build[i][j])));

        }

    }

    

    /*

     Kruskal's algorithm.

     Sort edges in ascending order.

     Go through each edge, see if it makes a cycle.

     If yes, skip this edge.

     If no, add this edge to MST

     */

    sort(edges.begin(), edges.end(), sortEdge);

    vector<int> setID;

    REP(i,0,N)

    setID.push_back(i);

    

    for(int i=0; i < edges.size(); i++)

    {

        edge cur = edges[i];

        if(setID[cur.from] != setID[cur.to])

        {

            int oldID = setID[cur.to];

            createCost += cur.cost;

            for(int j=0; j < N; j++)

                if(setID[j] == oldID)

                    setID[j] = setID[cur.from];

        }

        

    }

    return (createCost + destructCost);

}

About this blog

This blog is mainly about algorithms and programming.

I made this blog mostly for myself, and to help those who are facing similar problems.

My TopCoder handle is TurtleShip

My e-mail address is sk765@cornell.edu

And my name is Seulgi Kim