Problem C: Codeforces Round 455

Python Indentation

The problem can be found here

Problem Statement

In Python, code blocks don’t have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.

We will consider an extremely simplified subset of Python with only two types of statements.

Simple statements are written in a single line, one per line. An example of a simple statement is assignment.

For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with “for” prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can’t be empty.

You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.

Observations and Intuitions

Notice that for any instruction i if the (i-1)^th statement is a FOR then the current instruction i has to have an indent 1 greater than the last FOR. (the i-1 instruction)

For better understanding we will call indent 1 as an instruction being at depth 1 and so on..

So the i th instruction will have a depth 1 greater than depth of last FOR

1. If the prior instruction is a FOR(f) then the current one has to be at depth +1 no matter what
2. If the prior instruction is a STATEMENT(s) then it can belong to any FOR loop above it

the second point may be a bit confusing now .

Solution

Let array s[] hold the instruction type

Lets define the DP state dp[i][j] as the number of programs that have i instructions with the i’th instruction being at depth j

So for the very first statement, the 0'th statement there is only one program. Since it’ll always be at depth 0 if it is a s or an f.

Therefor dp[0][0] = 1

let the current instruction / statement be s[i]

then if the prior statement is s[i-1] ,let it be ‘f’ . Then let dp[i-1][0] = 1

let the s[i-1] have 1 way of being at depth 0 (meaning dp[i-1][0] = 1). Then s[i] no matter what cannot be at depth lesser than or equal to 0. Since a for loop cannot be empty, similarly it cannot have depth 2 since you cannot put 2 indents after a for, so the s[i] has to have a depth 1 if s[i-1]=’f’ and has depth 1.

Similarly if s[i-1] is at depth j then s[i] has to be at depth j+1. Therefore the number of ways s[i] can be at depth j+1 is equal to the number of ways s[i-1] can be at depth j.

therefore if s[i-1] = ‘f’ then, dp[i][j+1] = dp[i-1][j] for all j (make sure you don’t overflow limits to avoid segmentation faults)

Now the part where s[i-1] = ‘s’ then the current statement cannot have a depth greater than s[i-1] and s[i-1] cannot have a depth lesser than s[i]. The number of ways s[i] can be at depth k is the number of ways s[i-1] can be at depth(k,k+1,k+2,k+3….)

here s[3] can be at depth 2 only in one way. This is because it can be at depth 1 with s[i-1] being at depth 1 in 0 ways and depth 2 in 1 way. Therefore s[i]can be at depth 1 in 1 way (0+1). similarly for other depths

for s[4] here there are two ways for it to be at depth 1. since s[i-1] can be at depth 2 in 1 way and depth 1 in 1 way . Therefore s[i] can be at depth 1 in 2 ways (1+1).

similarly s[i] has 3 ways of being at depth 0.

hence for any statement if s[i-1]=’s’ then dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+1] +dp[i-1][j+2] + …dp[i-1][n]

in the above equation dp[i-1][n] n can be i-1 since that’s the maximum depth s[i-1] can achieve.

Apply suffix sum sum to avoid O(n³) complexity

dp[0][0] = 1;
FOR(i,1 to n-1)
	{
		if(s[i-1]=='f')
		{
			FOR(j,0 to i-1)
			dp[i][j+1] = dp[i-1][j];
		}
		else
		{
			suffix = 0;
			FOR(j,i-1 to 0)
			{
				suffix = suffix + dp[i-1][j];
				dp[i][j] = suffix;
			}
		}
	}

The final answer is the sum of dp[n-1][j] for all j .

Thanks for reading 😄