Hello Codeforces!

This post will be about one of the programming topics called binary search

Some example:

Given a sorted array a1 ≤ a2 ≤ . . . ≤ an of n numbers. Need to find a position numbers x, i.e., i such that ai = x.

A naive solution would be to go through the array and check each number.

--------------------------------------------------------------------

--------------------------------------------------------------------

Time complexity O(N)

Let's try to speed up the algorithm.

We initialize the response area, i.e. such an interval [l, r] on which the answer is (i ∈ [l, r]). In at the very beginning l = 1, r = n.

Then we have 2 cases:

• l = r. And if a[l] = x, then we have found the answer, otherwise the element does not exist in the array.

• l < r. Let's divide our interval into two parts, i.e.

let's take this m = (l+r)/2 and divide the interval into 2 parts [l, m] and [m + 1, r].

• If a[m] < x, then x is definitely not in the left half because all the elements are smaller X. That is. l := m + 1.

• Otherwise, x is in the left half and you can discard the right half. That is. r := m.

--------------------------------------------------------------------

--------------------------------------------------------------------

Time complexity: O(log(N))

I hope you found this blog useful. Good luck!

Hello Codeforces!

After 3 month of practice, I reach green color(Pupil rating)

I believe that you too will achieve what you want

Good luck!

In the theory of formal grammars and automata (TFGiA), an important role is played by the so-called context-free grammars (CS-grammars). A KS-grammar is a quadruple consisting of a set N of non-terminal symbols, a set T of terminal symbols, a set P of rules (productions) and an initial symbol S belonging to the set N.

Each production p of P has the form A –> a, where A is a non-terminal symbol (A of N) and a is a string consisting of terminal and non-terminal symbols. The word output process begins with a line containing only the initial character S. After that, at each step, one of the non-terminal characters included in the current line is replaced by the right side of one of the productions in which it is the left side. If after such an operation a string containing only terminal characters is obtained, then the output process ends.

The CS grammar is given. We need to find the number of rules containing immediate left recursion.

Sample Input:

3

S->Sabc

S->A

A->AA

Output:

2