# 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**

- If the prior instruction is a
**FOR(f)**then the current one has to be at depth +1 no matter what - 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. Therefor*e 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 😄