Blog of TurtleShip: February 2012

Tuesday, February 14, 2012

(The difference of two squares) mod 4

Argument
: Let a , b any integer, and z = a^2 - b^2
Then (z mod 4) can never be 2 for any value of a and b.

Proof
Lemma 1. (A perfect square mod 4 ) is always either 0 or 1.
Proof for lemma 1.
Let k = any number.
Then 2k is an ever number, and (2k+1) is an odd number.
Square of 2k = 4k^2 ==> (4k^2) mod 4 = 0
Square of (2k+1) = (4k^2 + 4k + 1) ==> (4k^2 + 4k + 1) mod 4 = 1

From lemma 1, we can conclude that (a^2 - b^2) can one of following four cases
1) even^2 - even^2
2) even^2 - odd^2
3) odd^2 - even^2
4) odd^2 - odd^2
where even = an even number and odd = an odd number.

Taking mod 4 for each case,
1) (0 - 0) mod 4 => 0
2) (0 - 1) mod 4 => 3
3) (1 - 0) mod 4 => 1
4) (1 - 1) mod 4 => 0

Therefore, for all possible cases, taking mod 4 of difference of squares always result in 0,1, or 3, but never 2.

Monday, February 13, 2012

Dynamic Programming with profile - example 3

This is a problem from TopCoder SRM 383 DIV1 - 500 point.

Here is a link to the problem statement : http://community.topcoder.com/stat?c=problem_statement&pm=8397&rd=10806

Here is the problem statement.

Problem Statement

You are building a house and are laying the floorboards in one of the rooms. Each floorboard is a rectangle 1 unit wide and can be of any positive integer length. Floorboards must be laid with their sides parallel to one of the sides of the room and cannot overlap. In addition, the room may contain features such as pillars, which lead to areas of the floor where no floorboards can be laid. The room is rectangular and the features all lie on a unit-square grid within it. You want to know the minimum number of floorboards that you need to completely cover the floor.

You are given a vector <string> room containing the layout of the room. Character j in element i of room represents the grid-square at position (i, j) and will be a '.' if this square needs to be covered with a floorboard or a '#' if the square is a feature where no floorboard can be laid. Return an int containing the minimum number of floorboards you need to completely cover the floor.

Definition

Class:	FloorBoards
Method:	layout
Parameters:	vector <string>
Returns:	int
Method signature:	int layout(vector <string> room)
(be sure your method is public)

Constraints

- room will contain between 1 and 10 elements, inclusive.

- Each element of room will contain between 1 and 10 characters, inclusive.

- Each element of room will contain the same number of characters.

- Each character in room will be a '.' or a '#'.

Examples

{"....."
,"....."
,"....."
,"....."
,"....."}

Returns: 5

5 boards laid side-by-side will cover this square room.

{"......."
,".#..##."
,".#....."
,".#####."
,".##..#."
,"....###"}

Returns: 7

A possible optimal layout could look like the following

|------ |#--##| |#----| |#####| |##--#| |---###

Each floorboard is represented by a consecutive horizontal sequence of '-' characters or a consecutive vertical sequence of '|' characters.

{"####"
,"####"
,"####"
,"####"}

Returns: 0

This is a strange room, with no floor area to cover.

{"...#.."
,"##...."
,"#.#..."
,".#...."
,"..#..."
,"..#..#"}

Returns: 9

An optimal pattern here is:

---#|| ##--|| #-#||| |#-||| ||#||| ||#||#

{".#...."
,"..#..."
,".....#"
,"..##.."
,"......"
,".#..#."}

Returns: 9

Approach
Let
R = number of rows in room.
C = number of columns in room.
Constraints tell us that 1 <= R,C <= 10

From small constraints, we can try the following approach :
Go through each row and try every possible combination.
Each row has at most 10 columns. So 2^10 maximum combination.
There are at most 10 rows.
So at worst, it will take 10 * 2^10 = 10 * 1024 = 10,240 operations.
Formally, runtime is O(R * 2^C)

Let's define state, recurrence, and profile.

State
dp[idx][profile]
= minimum number of boards we can use to cover all the areas from row[0] to row[idx]
when (idx-1)th row has configuration of profile.

Recurrence
The shape of each row depends on the shape of the previous row.

Profile
Binary representation of the previous row.
(i)th bit of profile is set if (i)th column of the row is a part of a vertical strip.
0 otherwise( which means it is either a pillar or a part of a horizontal strip).

Source code

class FloorBoards {

public:

int layout(vector <string>);

};

int R;

int C;

int mem[11][1<<10];

vector<string> room;

"mask" is a binary number representing shape of the previous row.

(i)th bit of mask is set to 1 if (i)th column of the previous row is a part of a vertical strip.

0 otherwise.

int rec(int idx, int mask)

{

if(idx == R) return 0;

int& res = mem[idx][mask];

if(res!=-1) return res;

res = INF;

for(int i=0; i < (1<<C); i++)

{

//check validity of the current config

bool isValid = true;

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

{

if( ((i>>j) & 1) && ( room[idx][j] == '#') )

{

isValid = false;

break;

}

if(!isValid) continue;

//Count the number of vertical and horizontal strips to use for the current row.

int vert = 0;

int hori = 0;

bool isHori = false;

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

{

It is a vertical strip.

If the current column of the above row is also a part of a vertical strip,

the current square is a part of the continuation of the previous vertical strip.

Only use a new vertical strip if the previous column is not a part of a vertical strip.

if( (i>>j) & 1)

{

isHori = false;

if( ((mask>>j) & 1) == 0 )

vert++;

}

else // The current square is either a pillar or a horizontal strip

{

if(room[idx][j] == '#') //It is a pillar

{

isHori = false;

}

else //It is a horizontal strip

{

if(!isHori)

{

isHori = true;

hori++;

}

res = min(res, vert + hori + rec(idx + 1, i));

}

return res;

}

int FloorBoards::layout(vector <string> _room) {

room = _room;

R = room.size();

C = room[0].size();

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

return rec(0,0);

}

Dynamic Programming with profile - example 2

This is a problem from TopCoder SRM 444 DIV1 - 500 point.

Here is a link to the problem statement : http://community.topcoder.com/stat?c=problem_statement&pm=10487

Approach
Let
R = number of rows
C = number of Columns
Constraints tell us that 1 <= R <= 10, 1 <= C <= 25

We can go through each column, try all configurations for the current column, and choose the best outcome.
Runtime will be O(C * 2^R) => Worst case : 25 * 2^10 = 25 * 1024 = 25600 . Small enough

You can also go through each row, try all configurations for the current row, and choose the best outcome.
Runtime will be O(R * 2^C) => Worst case : 10 * 2^25 = 10 * 33,554,432 = 335,544,320. Too big.

So let's go with iterating each column.

Algorithm

State
dp[idx][profile]
= maximum outcome for (idx)th column when its previous column has configuration of "profile"

recurrence
The validity of configuration of the current column depends on the configuration of the previous column.

Profile
A binary number representing configuration of the previous column.
(i)th bit of profile is set to 1 if (i)th row of the previous column is topleft corner of 2x2 '4' block.

Coding
I explained all the little details in comments in my source code.

Source Code

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

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

typedef long long ll;

class FourBlocks {

public:

int maxScore(vector <string>);

};

int mem[25][1<<10];

int R;

int C;

vector<int> cols;

Count number of bits in "mask"

int countTopLeftFour(int mask)

{

int res = 0;

while(mask > 0)

{

if(mask & 1) res++;

mask = mask>>1;

}

return res;

}

rec(idx,mask) returns maximum outcome for (idx)th column

when its previous column has configuration of "mask"

(i)th bit of mask is set to 1

if ith row of the previous column is topleft corner of 2x2 '4' block.

int rec(int idx, int mask)

{

if(idx == C)

{

if(mask == 0) return 0;

return nINF;

}

if(mask & cols[idx]) return nINF;

int& res = mem[idx][mask];

if(res != -1) return res;

res = 0;

Try every combination for current column.

For each combination, check if it is valid by looking at "mask"

and grid

for(int config = 0; config < (1<<(R-1)); config++)

{

"config" works the same way as "mask"

We only check config to (1<<(R-1) - 1) instead of (1<<R - 1)

because we cannot put the topleft corner of 2x2 '4' block

at the last row.

Let's call the current cell we are looking at

cell[j][idx] where idx stays the same for this column,

and this information is strored at jth bith of config.

We will check following conditions

1. Is cell[j+1][idx] empty?

2. Is cell[j][idx-1] or cell[j+1][idx-1] the beginning of

4x4 block, thus making cell[j][idx] and cell[j+2][idx] unsuitable

locations for the beginning of 4x4 block?

3. Is either cell[j][idx] or cell[j+1][idx] supposed to be '1'?

if( (config & (config<<1)) || (mask & (config | (config<<1))) || (cols[idx] & (config | (config<<1))) )

continue;

//Pick the best outcome out of all valid configurations

res = max(res, rec(idx+1, config | (config<<1)) + countTopLeftFour(config) * 16 + (R - countTopLeftFour(mask | config | (config<<1))));

}

return res;

}

int FourBlocks::maxScore(vector <string> grid) {

R = grid.size();

C = grid[0].size();

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

cols[i]

= jth bit of cols[i] is set to 1

if row j of column i contains '1' block in grid.

0 otherwise.

for(int c = 0; c < C; c++)

{

int mask = 0;

for(int r = 0; r < R; r++)

{

if(grid[r][c] == '1')

mask = mask | (1<<r);

}

cols.push_back(mask);

}

return rec(0,0);

}

Dynamic Programming with profile - example 1

This is a problem from TopCoder SRM 532 DIV 2 - 1000 point.

Here is a link to the problem statement : http://community.topcoder.com/stat?c=problem_statement&pm=11765&rd=14725

For those who are not member of TopCoder, here is a full problem statement.

Problem Statement

Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony.

One day, the queen of the kingdom challenged Mr. Dengklek with a perplexing puzzle: she gave Mr. Dengklek an N × M board made of wood that consists of N*M squares. She then asked Mr. Dengklek to paint the squares according to these rules:

Each square must be either colored or empty.
Each colored square must have an even number of adjacent colored squares. Two squares are adjacent if they share a side.

For example, here is one valid solution for N=4, M=7:

In the above image, black squares denote empty squares and brown squares denote colored squares.

Of course, finding one solution to the puzzle is easy: we do not color anything. Instead, the queen asked Mr. Dengklek a much harder question: to count all valid solutions of the puzzle. Help Mr. Dengklek count the solutions and return the result modulo 1,000,000,007. Two solutions are different if there is a square that is colored in one solution and not colored in the other solution.

Definition

Class:	DengklekPaintingSquares
Method:	numSolutions
Parameters:	int, int
Returns:	int
Method signature:	int numSolutions(int N, int M)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.

M will be between 1 and 8, inclusive.

Examples

Returns: 2

Either Mr. Dengklek colors the square, or he does not. Both choices produce a valid solution.

Returns: 8

Here are the 8 valid solutions:

Returns: 5

Returns: 944149920

Approach
Constraints tell us that 1 <= N <= 100 , 1<= M <= 8

We can go through each row, and try every possible combination of each row.
Each row has maximum of 2^M possible combinations, and some of them will be valid.
There are N rows.
This will take O(N * 2^M), and at worst, it will take 100 * 2^8 = 100 * 256 = 256,000 operations => Small enough.

Algorithm
As the post title suggests, we will use DP with profile.
Let's define state, recurrence, and profile.

State :
dp[r][profile]
= number of valid configuration for (r)th row when (r-1)th row, or previous row, has configuration of "profile"

Recurrence:
The validity of the current configuration of the current row depends on the previous row.
For example, if previous row is shaped like ("+" => colored," =" => not colored)

+=

Then possible configurations of the current row are

=+ ==

which will look like

+= +=
=+ ==

Cases where the current row looks like += and ++ are excluded because such configurations will make colored squared of previous rows have odd number of neighbors.

Profile :
Ternary representation (3 - based representation. ex> Binary : 2 - based representation) of the previous row.
(i)th digit of profile will be
0 : If (i)th square is not colored.
1 : If (i)th square is colored, and has odd number of neighbors.
2 : If (i)th square is colored, and has even number of neighbors.

Coding
Now that we figured out an algorithm, we need to actually implement it.
First thing to note is that "profile" is a number based in 3, or a ternary number.
The problem is that most languages can process decimal and binary numbers, but not ternary numbers.
So we need to make some functions to process ternary numbers properly.

1. pow3[i] = 3^i
2. get3[i][j] = gets (j)th digit of number i
3. set3[i][j][k] = replace (j)th digit of number i with k

Above three functions are enough to handle ternary numbers.

I added comments in my source code to help you understand.

Source Code

class DengklekPaintingSquares {

public:

int numSolutions(int, int);

};

//3^8 = 6561

int mod = 1000000007;

int mem[101][6561];

int R;

int C;

int pow3[9];

int get3[6561][9];

int set3[6561][9][3];

void preCompute()

{

pow3[0] = 1;

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

pow3[i] = 3 * pow3[i-1];

for(int i=0; i < pow3[8]; i++)

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

get3[i][j] = (i/pow3[j]) % 3;

for(int i=0; i < pow3[8]; i++)

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

for(int k=0; k <= 2; k++)

set3[i][j][k] = i + (k - get3[i][j]) * pow3[j];

}

Given current row is idx-th row,

and the previous row has configuration of "mask",

return number of valid configurations.

i-th digit of "mask" will be

0 : if it is not colored.

1 : if it is colored, and has odd number of neighbors.

2 : if it is colored, and has even number of neighbors.

int rec(int idx, int mask)

{

int& res = mem[idx][mask];

if(res != -1) return res;

res = 0;

if(idx == R)

{

Check validity of the "mask"

Return 1 is if valid. Else return 0.

bool isValid = true;

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

if(get3[mask][i] == 1) isValid = false;

if(isValid)

res = 1;

return res;

}

try all configuration for the current row

i-th bit of config is 0 if it is not colored,

i-th bit of config is 1 if it is colored.

for(int config = 0; config < (1<<C); config++)

{

bool isValid = true;

//check if the current configuration is valid

//by looking at previous row's configuration, or "mask"

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

{

bool isColored = ((config>>i) & 1);

if( (get3[mask][i] == 1 && !isColored) || ( get3[mask][i] == 2 && isColored) )

{

isValid = false;

break;

}

if(isValid)

{

int newConfig = 0;

//make new configuration according to config

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

{

if( (config>>i) & 1)

{

/* Look up, left, and right */

int sum = (get3[mask][i] != 0) ? 1 : 0;

if(i > 0)

sum = sum + (( (config>>(i-1)) & 1) ? 1 : 0);

if(i < C-1)

sum = sum + (( (config>>(i+1)) & 1) ? 1 : 0);

if(sum%2 == 1) newConfig = set3[newConfig][i][1];

else newConfig = set3[newConfig][i][2];

}

else

{

newConfig = set3[newConfig][i][0];

}

res = (res + rec(idx+1, newConfig)) % mod;

}

return (res % mod);

}

int DengklekPaintingSquares::numSolutions(int N, int M) {

R = N;

C = M;

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

preCompute();

return rec(0,0);

}

Dynamic Programming with profile - introduction

Introduction

Dynamic Programming , or DP for short, is defined by two factors - state and recurrence.

Two terms can be defined as follow
State : A result produced depending on variable(s). variables to be used and an outcome to be stored depending on the variables need to be determined.

Recurrence : Relationship between each state.

For example, say we are looking for ways to store powers of 5.

State
Variable to be used : exponent
An outcome to be stored depending on the variable : 5^exponent
=> pow[i] = 5^i

Recurrence
5^i = 5 * 5^(i-1)
pow[i] = 5 * pow[i-1]

After defining state and recurrence, we need to determine value(s) for base case(s).

In the above example, base case is pow[0] = 1.

To code powers of 5,

int power_of_5[N]; //make array size of N
power_of_5[0] = 1;
for(int i=1; i < N; i++)
{
power_of_5[i] = 5 * power_of_5[i-1];
}

Dynamic Programming looks simple enough. But the seemingly simple algorithm can be used to solve most complicated problems.
And sometimes, it is necessary to tweak or make minor modifications to traditional DP in order to properly handle difficult problems. One of them is DP with profile.

What is Dynamic Programming with Profile?

Dynamic Programming with profile is all about defining three terms : state, recurrence, and profile.

We already know what state and recurrence are from Introduction.
Let's see why we need profile

profile
: Information about other state(s).

You might argue that "state" itself holds information in its outcome and therefore profile is unnecessary.
Yes, true. However, let's look at the definition of state again.

State : A result produced depending on variable(s). variables to be used and an outcome to be stored depending on the variables need to be determined.

Did you notice that I italicized "an"? There is a reason.

What if you need more than one information about a certain state?
You can say that we can do that by some time of customized data structure to hold both data, like pair<int,int> or Node.

Then what if the data are not necessarily related to each other?
More formally, what if for a fixed variable i, DP[i] is different depending on other information?

This is the time to use DP with profile so that we can handle above cases by using DP[i][profile].

I am guessing you are still very much confused, and have absolutely no idea what I am talking about. Do not worry. I will explain them over and over using examples.

Saturday, February 11, 2012

Codeforces #106 Div 2

This was my first time to participated in Codeforces (http://www.codeforces.com/) , an online programming contest site.

This is a link explaining rules about the contest : http://codeforces.com/blog/entry/456

During the contest, I made a newbie mistake of resubmitting the same solution twice because I didn't understand what "judgement failed." meant. I thought it was something like "compilation error." Only after resubmitting my solution did I learn that "judgement failed" meant "there is something wrong with our server. Please wait a while we fix this issue." I lost about 100 points for that mistake.

But other than that, things went okay.

I solved three problems out of five - A , B, and C.

Here is the link to problem statement : http://codeforces.com/contest/149

Problem A - A Business trip

Algorithm
Our main character, Petya, wants to water her plant as few time as possible while still achieving the goal of making her plant grow more than or equal to k centimeters.

We can use a greedy approach. Follow below steps
1. Sort month by how many centimeters they can make a flower grow in ascending order.
2. Pick the month with the largest growth value, and add it to variable named "sum".
3. Repeat procedure 2 until value of "sum" >= k

Source code

int main()

{

int k;

vector<int> water;

cin>>k;

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

{

int temp;

cin>>temp;

water.push_back(temp);

}

int N = water.size();

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

int sum = 0;

int month = 0;

bool found = false;

if(k == 0){

cout<<0<<endl;

found = true;

}

for(int i=N-1; i >= 0 && !found; i--)

{

sum += water[i];

month++;

if(sum >= k)

{

cout<<month<<endl;

found = true;

break;

}

if(!found)

cout<<-1<<endl;

return 0;

}

Problem B - Martian Clock

Algorithm

1. Determine whether the given input has infinite number of bases or not. If it does, output -1. If it has a finite number of valid base, move to step 2.

2. Starting from a minimum valid base, keep increasing base by one until you reach a base that is not valid.

Explanation

Q1 : How do I determine whether the given input has an infinite number of bases or not?

Let's first observe the obvious : the first digit of a number is not affected by base.

To illustrate, let's take a look at number 4.

4 in base 5 is 4.

4 in base 6 is 4.

4 in base 7 is 4.

...

4 in base 58 is 4.

....

More formally,

x in base y

= x * y^0

= x * 1

= x where x is a single integer.

So if both hour and minute are single characters, the given input has infinite number of bases IF they are valid time.

For example, B:9 is a valid time in any base, because it will be 12:09 in any base above base 13.

However, Z:9 is not a valid time in any base because it will be 35:09 in any valid base.

Note that once we verify that both hour and minute are single characters, we only have to check the validity of hour because maximum number a single character can represent in 'Z', or 35, which is a valid number for minute.

Q2 : Once we determine that the given input has a finite number of bases, how do we find the minimum valid base?

Note that in base x , the highest number you can have at each digit is (x-1).

For example, in base 10, the highest number you can have at each digit is 9.

If you reverse the above statement, you can find out that if the highest number you have at each digit is x-1, the minimum valid base is x.

So go through each character in the input, find the highest single character x, and the minimum valid base is x+1.

Source code

int toInt(char ch)

{

if('0' <= ch && ch <= '9')

return (ch - '0');

return (ch - 'A' + 10);

}

int toDecimal(string num, int b)

{

int result = 0;

int mult = 1;

for(int i=(num.size() - 1); i >= 0; i--)

{

result += toInt(num[i]) * mult;

mult *= b;

}

return result;

}

int main()

{

string input;

cin>>input;

bool found = false;

int hourSt = -1;

int mid = 0;

int minSt = -1;

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

{

if(input[i] == ':')

{

mid = i;

break;

}

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

{

if(input[i] != '0')

{

hourSt = i;

break;

}

for(int i=mid+1; i < input.size(); i++)

{

if(input[i] != '0')

{

minSt = i;

break;

}

string HH = (hourSt == -1) ? "0" : input.substr(hourSt,(mid-hourSt));

string MM = (minSt == -1) ? "0" : input.substr(minSt);

infinite case is when both number are single digit.

bool isValid = true;

if( HH.size() == 1 && MM.size() == 1)

{

if(toInt(HH[0]) >= 24)

cout<<0;

else

cout<<-1;

isValid = false;

}

int base = 0;

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

{

base = max(base, toInt(HH[i]));

}

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

{

base = max(base, toInt(MM[i]));

}

base++;

int count = 0;

if(toDecimal(HH, base) < 24 && toDecimal(MM,base) < 60 && isValid)

{

count++;

cout<<base;

}

base++;

while(true && isValid)

{

if(toDecimal(HH, base) < 24 && toDecimal(MM,base) < 60)

{

cout<<" "<<base;

base++;

count++;

}

else break;

}

if(count==0 && isValid)

cout<<"0";

return 0;

}

Problem C - Division into Teams

The problem statement states that it is guaranteed that a fair division into two teams always exists.

This means there is always an optimal solution, and we can start by how the optimal solution looks like.

There are three conditions that the optimal solution meets

#1 Each boy plays for exactly one team (x + y = n).
#2 The sizes of teams differ in no more than one (|x - y| ≤ 1).
#3 The total football playing skills for two teams differ in no more than by the value of skill the best player in the yard has. More formally:

$\text{[math]}$

#1 and #2 tell us that each team took turns picking a player.

#3 tells that after picking players, the team who went first (who picked the best player and possibly one more player than the other player) gave one or two players away to the other team to balance each team's skills. Since there is always an optimal solution, we don't have to worry about giving too many players away.

Algorithm

Let there be team X and team Y.

1. Sort all players by their skills in descending order.

2. Each team picks player. Team X goes first. Each team will obviously pick the best available player.

3. After picking all players, team X will give the worst player that is has away to team Y until formula in #3 is met.

Source Code

int main()

{

int n;

cin>>n;

vector< pair<int,int> > boys;

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

{

int temp;

cin>>temp;

boys.push_back(make_pair(temp,i));

}

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

vector< pair<int,int> > x;

vector< pair<int,int> > y;

long long xSum = 0;

long long ySum = 0;

long long maxP = boys[n-1].first;

for(int i=(n-1); i >= 0; i--)

{

if(i%2 == 0)

{

x.push_back( boys[i] );

xSum += boys[i].first;

}

else

{

y.push_back( boys[i] );

ySum += boys[i].first;

}

while( (xSum - ySum) > maxP && abs( int(x.size() - y.size()) ) <= 1)

{

int point = x[0].first;

int num = x[0].second;

x.erase(x.begin());

xSum -= point;

ySum += point;

y.push_back( make_pair(point,num));

}

cout<<x.size()<<endl;

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

{

cout<<x[i].second<<" ";

}

cout<<endl;

cout<<y.size()<<endl;

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

{

cout<<y[i].second<<" ";

}

cout<<endl;

return 0;

}

Thursday, February 9, 2012

TopCoder SRM 532 DIV2

Today's SRM was frustrating for me.

I forgot to check for a special case while solving DIV2 - 500 point problem, and it failed system test.
I also made one unsuccessful challenge. My only successful submission was for DIV2 - 250.

I ended up getting a very low score, and failed to become blue.

DIV 2 - 250 problem

Problem Statement

Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony. The ducks are numbered by distinct positive integers from A to B, inclusive, where A <= B.

Last night, Mr. Dengklek could not sleep, so he tried to count all the ducks in the kingdom. (It is known that counting ducks can help people to fall asleep.) When counting the ducks, Mr. Dengklek walked across an imaginary meadow and whenever he saw a new duck, he called out its number. He only called out actual duck numbers, i.e., numbers from A to B. He never called the same number twice. The numbers he called out are not necessarily in the numeric order.

You are given a vector <int> ducks. The elements of ducks are the numbers Mr. Dengklek called out when counting the ducks last night. It is possible that he missed some of the ducks. Obviously, the number of ducks he missed depends on the values A and B. The values of A and B are unknown to you. Compute and return the smallest possible number of ducks Mr. Dengklek might have missed.

Definition

Class:	DengklekTryingToSleep
Method:	minDucks
Parameters:	vector <int>
Returns:	int
Method signature:	int minDucks(vector <int> ducks)
(be sure your method is public)

Constraints

ducks will contain between 1 and 50 elements, inclusive.

Each element of ducks will be between 1 and 100, inclusive.

All element of ducks will be distinct.

Examples

{5, 3, 2}

Returns: 1

If A=2 and B=5, the only duck Mr. Dengklek missed is the duck number 4.

{58}

Returns: 0

If A=B=58, Mr. Dengklek did not miss any ducks.

{9, 3, 6, 4}

Returns: 3

In this case, the smallest possible number of missed ducks is 3: the ducks with numbers 5, 7, and 8.

{7, 4, 77, 47, 74, 44}

Returns: 68

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Returns: 0

Logic.
Sort "ducks", which will make ducks[0] == A and ducks[N-1] == B, where N = is length of duck.
Since ducks do not have a same number, (B-A+1) - N is our answer.

Source Code.

class DengklekTryingToSleep {
public:
int minDucks(vector <int>);
};

int DengklekTryingToSleep::minDucks(vector <int> ducks) {
sort(ducks.begin(), ducks.end());
int N = ducks.size();
int A = ducks[0];
int B = ducks[N-1];

return ( (B-A+1) - N);
}

DIV2 - 600 point problem

Problem Statement

Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony.

Mr. Dengklek works as a chain maker. Today, he would like to make a beautiful chain as a decoration for one of his lovely ducks. He will produce the chain from leftovers he found in his workshop. Each of the leftovers is a chain piece consisting of exactly 3 links. Each link is either clean or rusty. Different clean links may have different degrees of beauty.

You are given a vector <string> chains describing the leftovers. Each element of chains is a 3-character string describing one of the chain pieces. A rusty link is represented by a period ('.'), whereas a clean link is represented by a digit ('0'-'9'). The value of the digit in the clean link is the beauty of the link. For example, chains = {".15", "7..", "532", "..3"} means that Mr. Dengklek has 4 chain pieces, and only one of these ("532") has no rusty links.

All links have the same shape, which allows Mr. Dengklek to concatenate any two chain pieces. However, the link shape is not symmetric, therefore he may not reverse the chain pieces. E.g., in the above example he is able to produce the chain "532.15" or the chain ".15..37..", but he cannot produce "5323..".

To produce the chain, Mr. Dengklek will follow these steps:

Concatenate all chain pieces in any order.
Pick a contiguous sequence of links that contains no rusty links. Remove and discard all the remaining links.

The beauty of the new chain is the total beauty of all the links picked in the second step. Of course, Mr. Dengklek would like to create the most beautiful chain possible.

Return the largest possible beauty a chain can have according to the above rules.

Definition

Class:	DengklekMakingChains
Method:	maxBeauty
Parameters:	vector <string>
Returns:	int
Method signature:	int maxBeauty(vector <string> chains)
(be sure your method is public)

Notes

Mr. Dengklek is not allowed to remove and discard individual links before concatenating the chain pieces.

If all links in the input are rusty, Mr. Dengklek is forced to select an empty sequence of links. The beauty of an empty sequence is 0.

Constraints

chains will contain between 1 and 50 elements, inclusive.

Each element of chains will contain exactly 3 characters.

Each character in each element of chains will be either a '.' or one of '0'-'9'.

Examples

{".15", "7..", "402", "..3"}

Returns: 19

One possible solution:

In the first step, concatenate the chain pieces in the order "..3", ".15", "402", "7.." to obtain the chain "..3.154027..".
In the second step, pick the subsequence "154027".

The beauty of the chain in this solution is 1+5+4+0+2+7 = 19.

{"..1", "7..", "567", "24.", "8..", "234"}

Returns: 36

One possible solution is to concatenate the chain pieces in this order:

"..1", "234", "567", "8..", "24.", "7.." -> "..12345678..24.7..",

and then to pick the subsequence "12345678". Its beauty is 1+2+3+4+5+6+7+8 = 36.

{"...", "..."}

Returns: 0

Mr. Dengklek cannot pick any links.

{"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}

Returns: 28

{"..1", "3..", "2..", ".7."}

Returns: 7

{"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"}

Returns: 58

Logic.
Let's start by recognizing patterns.
Let n = a number.
Let Golden Rule = Mr.Denglek picks only contiguous sequence of links that contains no rusty links.

#1. All "nnn" chain will be included in answer.
Proof.
A chain made of all numbers can fit anywhere, so it will be optimal to include it in the answer.
The least you can get is 0 by adding it, so it wouldn't "hurt" the optimal solution.

#2 Only one of chain with format either ".nn" or "..n" can be included in answer.
Proof.
Apply Golden Rule.
Since ".nn" and "..n" both have a rusty link at its leftmost position. they can be connected by other chains only with their right link. ex> ".nn" + "nnn"

#3 Only one of chain with format either "n.." or "nn." can be included in answer.
Proof.
Same as #2

#4. Chains with format "n.n" can use only one of its numbers as a part of answer.
According to Golden Rule, he has to stop when he reaches "."

#5 Chain with format ".n." can only used as a single link.

Algorithm.
Answer will have a format left + middle + right.
Go through each string in chains, find which chain can be include in left, middle, and right, and store their maximum values.

Find a combination that results in maximum value.

Also, check for a single chain that results in maximum value. This is to prepare for cases like "7.1", ".3.", where an answer is made of a single link. ( I forgot to do this during test).

Source Code. (it passed system test.)

int toInt(char ch)

{

if(ch == '.') return 0;

return (ch - '0');

}

int DengklekMakingChains::maxBeauty(vector <string> chains) {

int left = 0;

int right = 0;

int mid = 0;

int solo = 0;

int maxSideL = 0;

int maxSideR = 0;

vector<int> sideL;

vector<int> sideR;

int N = chains.size();

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

{

string cur =chains[i];

int len = cur.size();

bool isDot1 = (cur[0] == '.');

bool isDot2 = (cur[1] == '.');

bool isDot3 = (cur[2] == '.');

bool isSolo = (isDot1 && !isDot2 && isDot3);

bool isSide = (!isDot1 && isDot2 && !isDot3);

bool isRusty = (isDot1 && isDot2 && isDot3);

bool isLeft = (isDot1);

bool isRight = (isDot3);

bool isMiddle = (!isDot1 && !isDot2 && !isDot3);

int now = 0;

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

now += toInt(cur[j]);

if(isSolo)

{

solo = max(solo, now);

}

else if(isSide)

{

maxSideL = max(maxSideL, toInt(cur[2]));

maxSideR = max(maxSideR, toInt(cur[0]));

sideL.push_back(toInt(cur[2]));

sideR.push_back(toInt(cur[0]));

}

else if(isMiddle)

{

mid += now;

}

else if(isRusty)

{

continue;

}

else if(isLeft)

{

left = max(left, now);

}

else if(isRight)

{

right = max(right ,now);

}

int S = sideL.size();

int best = 0;

//left + middle + right

best = max(best, left + right);

//left + middle + side

best = max(best, left + maxSideR );

//side + middle + right

best = max(best, maxSideL + right );

//side + middle + side

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

{

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

{

if(i==j) continue;

best = max(best , sideL[i] + sideR[j]);

}

solo = max(solo, left);

solo = max(solo, right);

solo = max(solo, mid);

solo = max(solo, maxSideL);

solo = max(solo, maxSideR);

return max(solo ,(mid + best));

}