Pizza Stack

Kamaldeep is good at making pizzas. Generally he gets requests to serve N pizzas at once. He serves them in the form of a stack. A pizza should be treated as a circular disk with some radius.

Kamaldeep needs to take care that when he places a pizza on the top of the stack the radius of the pizza should not exceed the radius of the largest pizza in the stack by more than 1. Additionally all radii should be positive integers, and the bottom most pizza should have its radius as 1. Kamaldeep is week in maths :P, so he wants you to find out in how many ways can he create a stack containing N pizzas.

Input

First line of the input contains T (T <= 1000) denoting the number of test cases.

T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.

Output

For each case the output should be a single integer representing the number of ways a stack of size N can be created. As

the answer can be large print it modulo 1000000007.

ANS------->

dp[i][j] -> stack size of i with j different value .

dp[i][j] = j*dp[i-1][j] + dp[i-1][j-1];

1. #include <iostream>
2. using namespace std;
3.  
4. int main()
5. {
6. int t ;
7. cin >> t;
9. long long mo = 1000000007;
10.  
11. long long dp[1002][1002];
12. long long top[1002];
14. for(int i=0 ; i < 1002 ; i++)
15. for(int j=0 ; j < 1002 ; j++)
16. dp[i][j]=0;
17.  
18. dp[1][1]=1 ;
19. top[1]=1;
22. for(int i=2 ; i < 1002 ; i++){
23. long long temp = 0 ;
24. for(int j=1; j<=i; j++){
25. dp[i][j]=j*dp[i-1][j]%mo + dp[i-1][j-1]%mo;
26. temp=(temp+dp[i][j])%mo;
27. }
28. top[i]=temp;
29. }
33. while(t--){
35. int val ;
36. cin >> val ;
37. cout << top[val] << endl ;
39. }
41.  
42. return 0;
43. }

Optical character reorganization system

SUMMARY

In the running world, there is growing demand for the software systems to recognize

characters in computer system when information is scanned through paper documents as we

know that we have number of newspapers and books which are in printed format related to

different subjects. These days there is a huge demand in storing the information available in

these paper documents in to a computer storage disk and then later reusing this information by

searching process. One simple way to store information in these paper documents in to

computer system is to first scan the documents and then store them as IMAGES. But to reuse

this information it is very difficult to read the individual contents and searching the contents

form these documents line-by-line and word-by-word. The reason for this difficulty is the font

characteristics of the characters in paper documents are different to font of the characters in

computer system. As a result, computer is unable to recognize the characters while reading

them.

Thus our need is to develop character recognition software system to perform Document

Image Analysis which transforms documents in paper format to electronic format. For this

process there are various techniques in the world. Among all those techniques we have chosen

Optical Character Recognition as main fundamental technique to recognize characters. OCR

thus derives the meaning of characters, their font properties from their bit-mapped images.

PROBLEM STATEMENT

In the running world there is a growing demand for the users to convert the printed documents

in to electronic documents for maintaining the security of their data. Hence the basic OCR

system was invented to convert the data available on papers in to computer process able

documents, So that the documents can be editable and reusable. The existing system/the

previous system of OCR on a grid infrastructure is just OCR without grid functionality. That is

the existing system deals with the homogeneous character recognition or character recognition

of single languages.

The drawback in the early OCR systems is that they only have the capability to convert and

recognize only the documents of English or a specific language only. That is, the older OCR

system is uni-lingual.

OVERVIEW OF PROPOSED SOLUTION APPROACH

The problem is for the software systems to recognize characters in computer system when

information is scanned through paper documents as we know that we have number of

newspapers and books which are in printed format related to different subjects. Whenever

we scan the documents through the scanner, the documents are stored as images such as

jpeg, gif etc., in the computer system. These images cannot be read or edited by the user.

But to reuse this information it is very difficult to read the individual contents and the

contents form these documents line-by-line and word-by-word. These days there is a huge

demand in “storing the information available in these paper documents in to a computer

storage disk and then later editing or reusing this information by searching process”.

INTEGRATED SUMMARY OF THE LITERATURE STUDIED

Neural network play a very important role in Artificial intelligence. For the neural network training is

important part it provide ability to guess the best Answer. There are two type of training for neural

networks

 Un-Supervised Training

 Supervised Training

Supervised training provides the neural network with training sets and the anticipated output. Unsupervised

training supplies the neural network with training sets, but there is no anticipated output provided

UNSUPERVISED TRAINING

Unsupervised training is a very common training technique for Kohonen neural networks. What is meant by

training without supervision is that the neural network is provided with training sets, which are collections of

defined input values. But the unsupervised neural network is not provided with anticipated outputs.

Unsupervised training is usually used in a classification neural network. A classification neural network takes

input patterns, which are presented to the input neurons. These input patterns are then processed, and one

single neuron on the output layer fires. This firing neuron can be thought of as the classification of which

group the neural input pattern belonged to. Handwriting recognition is a good application of a classification

neural network.

The input patterns presented to the Kohonen neural network are the dot image of the character that was

hand written. We may then have 26 output neurons, which correspond to the 26 letters of the English alphabet.

The Kohonen neural network should classify the input pattern into one of the 26 input patterns.

During the training process the Kohonen neural network in handwritten recognition is presented with 26 input

patterns. The network is configured to also have 26 output patterns. As the Kohonen neural network is trained

the weights should be adjusted so that the input patterns are classified into the 26 output neurons. This

technique results in a relatively effective method for character recognition.

SUPERVISED TRAINING

The supervised training method is similar to the unsupervised training method in that training sets are

provided. Just as with unsupervised training these training sets specify input signals to the neural network.

The primary difference between supervised and unsupervised training is that in supervised training the

expected outputs are provided. This allows the supervised training algorithm to adjust the weight matrix based

on the difference between the anticipated output of the neural network, and the actual output.

There are several popular training algorithms that make use of supervised training. One of the most

common is the back-propagation algorithm. It is also possible to use an algorithm such as simulated annealing

or a genetic algorithm to implement supervised training.

FUNCTIONAL AND NON FUNCTIONAL REQUIREMENTS

FUNCTIONAL REQUIREMENTS

1. The product shall be able to recognize the input character

2. The product shall be able to load the image form the local storage where they are stored.

3. The product shall be able to edit the image correctly.

4. The product should be proper character recognition system.

5. Product shell recognizes the image clearly.

NON FUNCTIONAL REQUIREMENT

1. Reliable: The apps should display authentic and right guidelines/information regarding

information security and should not mislead. Failures/errors should be debug able .

2. Performance: Speed should be efficiently high. The apps/buttons should respond within

1-5s

3. Safety: The apps should not cause any damage to human in any form.

ARCHITECTURE OF THE PROPOSED SYSTEM

The Architecture of the optical character recognition system on a grid infrastructure consists of the three

main components. They are:-

 Scanner

 OCR Hardware or Software

 Output Interface

MODULES AND THEIR FUNCTIONALISTS

Our software system Optical Character Recognition on a grid infrastructure can be divided into five

modules based on its functionality.The modules classified are as follows:-

 Document Processing Module

 System Training Module.

 Document Recognition Module.

 Document Editing Module and

 Document Searching Module.

FINDINGS

 System can detect the character if there is a slight difference in training set character and input set of

character.

 This system more stable as compared to other existing systems.

 Compare with other systems, this provides more correct output.

CONCLUSION

What does the future hold for OCR? Given enough entrepreneurial designers and sufficient research and

development dollars, OCR can become a powerful tool for future data entry applications. However, the

limited availability of funds in a capital-short environment could restrict the growth of this technology. But,

given the proper impetus and encouragement, a lot of benefits can be provided by the OCR system. They are:-

 The automated entry of data by OCR is one of the m ost attractive, labor reducing technology

 The recognition of new font characters by the system is very easy and quick.

 We can edit the information of the documents more conveniently and we can reuse the edited information

as and when required.

 The extension to software other than editing and searching is topic for future works.

The Grid infrastructure used in the implementation of Optical Character Recognition system can be

efficiently used to speed up the translation of image based documents into structured documents that are

currently easy to discover, search and process

FUTURE WORK

The Optical Character Recognition software can be enhanced in the future in different kinds of ways

such as:

 Training and recognition speeds can be increased greater and greater by making it more user-friendly.

 Many applications exist where it would be desirable to read handwritten entries. Reading handwriting is a

very difficult task considering the diversities that exist in ordinary penmanship. However, progress is

being made.

for the full presentation --> http://www.slideshare.net/IAMINURHEARTS1/ocr-ppt-35272335

for youtube presentation -->https://www.youtube.com/watch?v=AYRTcxPvw04&feature=youtu.be

Randomness

You’re given a string S of N characters. It’s known that the string consists of lowercase latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {‘a’, ‘b’, …, ‘z’}. All the letters has equal probability to appear.

You’re given Q queries on this string. Each query is of the form P C, where P is an integer between 1 and N (both inclusive) and C is a character from the set {‘a’, ‘b’, …, ‘z’}. Both P and C were chosen at random and independently from other queries.

When you have a query of the form P C you have to change the Pth symbol of S to C. After every change we ask you to output the number of distinct nonempty sub-strings of S.

Input Format
The first line of input consists of two single space separated integers N and Q - the length of the string S and the number of queries respectively.

The second line contains the string S itself.

The following Q lines describe the queries in the form P C, where P and C are also separated with a single space.

Constraints

4 ≤ N ≤ 75000
4 ≤ Q ≤ 75000

Output Format
Output Q lines. Output the number of distinct substrings of S after the ith query on theith line of the output.

Sample Input

4 4 
aaab
1 a
2 b
3 c
4 d

Sample Output

7
7
9
10

Explanation

after replacing the character at 1st index with a, we still have the original string aaab. The total non empty substrings of aaab are

a b aa ab aaa aab aaab

hence 7.

after replacing the character at 2nd index with b, we have the string abab. The total non empty substrings of abab are

a b ab ba aba bab abab

hence 7.

after replacing the character at 3rd index with c, we have the string abcb. The total non empty substrings of abcb are

a b c ab bc cb abc bcb abcb

hence 9.

after replacing the character at 4th index with d, we have the string abcd. The total non empty substrings of abcd are

a b c d ab bc cd abc bcd abcd

hence 10.

Scoring

There are 12 test cases.

The first four test cases N = 100 and Q = 500
The next four test cases N = 75000 and Q = 10
The last four test cases N = 75000 and Q = 75000

solution-->

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on, 

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.

So we have, 

1 2	ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

1 2 3 4

LCP("ANA", "ANANA") = "ANA". ans += length("ANANA") - length(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5.

Similarly, we have:

1 2	LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2	LCP("BANANA", "NA") = 0 ans = ans + length("NA") - 0 = 13

1 2	LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

code---->

#include<iostream>

#include<string>

#include<algorithm>

using namespace std ;

int LCP(string s , string s1){

int x=s.size();

int y=s1.size();

if(x>y)

    x=y;

    int count=0 ;

    for(int i=0 ; i < x ;i++){

        if(s.at(i)==s1.at(i))

            count++;

        else

         break ;

    }

return count ;

}

void check(string s){

    int x= s.size();

    string ss[x];

    

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

        ss[i]= s.substr(i);     

         sort(ss,ss+x);

         int ans=0;

         ans=ss[0].size();

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

    ans+=( ss[i].size() - LCP(ss[i],ss[i-1]));

    cout << ans << endl ;    

}

int main(){

    int x=0,y=0 ;   

    cin >> x >> y ;

     string s ;

    cin >> s ;

    while(y--){

          int p ;

          char z ;

         cin >>p >> z ;

         s[p-1]=z;

         check(s);

     }

    return 0 ;   

}