STL & GNU C++ with codeblocks

If we are using STL program in codeblocks, we have to enable GNU c++ option
by selecting

Project->Build options->Have g++ follow the coming C++ 0x ISO C++
language standard [-std =c++0x]

Otherwise it wont compile in codeblocks editor. while submitting the
same code in codeforces.com, we have to select
GNU C++0x4 option for uploading the cpp file.

BHTML & BCSS codeforces problem log

BHTML & BCSS codeforces problem log:

What are all the steps I have done to solve this problem:


For a problem, I started by generating the strings and tried to
compare the strings as follows:

<a><b><b></b></b></a>

Generated string [from HTML] is as follows:
a
a b
a b b

pattern a b has occurence as 2 times.

Pattern should be there in the generated string.

we need to check all the patterns and count/increment the current occurence.

This approach is taking more time, I got "timeout exceeded".

Once again I got failed in substring test case.

for example, <sundar/>
for pattern :sun it should return 0. But it is returning some other values
I stored the values in hashtable and added the number in an array.
instead of comparing strings, I started comparing
integer values.



1)timeout exceeded
2)substring testcase failure <sundar/> query:sun but output is 1. it should be 0
3)string comparison takes time, I added the string in hashtable and
generated the int array to compare & reduce
time
4) Integer comparison also takes around 7 seconds for a problem &
failed in somecases giving improper output.
5) I checked the case of seulgi kim's code. Based on my understanding,
I have created
Nary trees from the HTML. From Nary trees, we will search for the
given query recursively.

6.Through debugging found that PushToStack should be available for
<tag/> cases too
7.Modified the PreOrder() fn return as Long
8.modified the readQuery() to read char by char
9.deleted the query array and created it for each query
10.Tried by changing the stack size limit.
#pragma comment(linker, "/STACK: 2000000")

11. I doubted the readQuery() but I am getting large size input for the query.
I changed the Maximum Query characters Count[MaxQueryCount] from 250
to 4000. Now I have posted it, it was working fine & accepted in the
codeforces.
I thought like query line will have maximum 250 characters. I haven't
read properly about the problem sentences:

" Each query is a sequence x1, x2, ..., xn, where xi is the i-th
element of the query, and n (1 ≤ n ≤ 200) is the number of elements in
the query. The elements are separated by single spaces. Each query
doesn't begin with and doesn't end with a space. Each query element is
a sequence of lowercase Latin letters with length from 1 to 10."

200[queries] * 10 [tag size]* 199 spaces = 398000 characters it can
be...But since the testcases are having less than this limit, I am
able to run with 4000

12.Eventhough I successfully submitted the code in codeforces, I could
found one more problem... that is allocated nodes are not released
properly. I released all the nodes including parent nodes & resubmitted it...

Competition Sites to practice

1 UVA:http://acm.uva.es/p - The Valladolid University Online Judge.
Over N problems, for a reasonable value of N. The problems are culled
from old contests, and online contests.
2.ZJU:Zhejiang University Online Judge - http://acm.zju.edu.cn
3.SGU:Saratov State University Online Contester - http://acm.sgu.ru
4.PKU: Peking University Judge Online of ACM ICPC -
http://acm.pku.edu.cn/JudgeOnline
5.topcoder
6.codeforces

Books recommended in codechef

1. Standard book on Algorithms - Introduction to Algorithms by T H
Cormen, C E Leiserson, R L Rivest, C stein ( Famously known as CLRS )
2. Basic Algorithms - Algorithms by Richard Johnsonbaugh, Marcus Schaefer
3. Game Theory - Winning ways for your mathematical plays by Elwyn R.
Berlekamp, John H. Conway, Richard K. Guy
4. Programming challenges - Steven Skienna
5. Concrete Mathematics - Knuth
6. How to solve it by a computer - Dromey
7. Structure and interpretation of computer programs - Elsevier
8. Programming Language Pragmatics - Micheal Scott : It gives
comparative study of various programming languages and helps you
decide choose the appropriate ones on the basis of time they take to
process information

How P frame seek support will be added in any multimedia framework

Some multimedia frameworks will have support for P frame seek. Some
frameworks wont have this support. So How can we add this support ?

For P frame seek, we can not start directly start decoding & rendering
from the P frame;
Since P frame doesnt have entire frame information, if we start
decoding & rendering from P frame, it will shows
green patches on screen and affect the user experience.


How P frame seek is supported in Directshow multimedia framework ?


For any seek timestamp, Parser will seek the I frame timestamp before
the seek timestamp.
Ex :
I frame is available in 10th second.
if the seek is done to 12th second, the Parser will fetch I frame from
10th second and give it do the decoder.

Source Filter will set IMediaSample's SetPreroll() as true. The
decoder will decode the frame,get necessary information and wont give
it to the renderer.

Once the timestamp reached the seek timestamp, Parser will set the
setPreroll as false, then frame will starts rendering.


OpenCORE:

In OpenCORE's frame have an option to set DoNotRender flag. If we set
this flag, it wont render the given frame.

In Generic, In any multimedia framework,

if we are calling seek to any timestamp, Upto seektimestamp is
reached, video and audio frames are dropped without rendering on
hardware device.In case of audio, we will have more I frames. But if
we are rendering audio alone, video takes more time to catchup
video.User might be able to observe the weird behaviour since ear is
more sensitive than eyes. In this scenario, rendering the audio also
causes the audio clock to increase. It will cause AV sync issues once
video starts rendering.

In any multimedia framework, we have to do the following steps to
do P frame seek:



1.ParserseekTo(Nearest_I_Frame to SeekTimesamp);
2.ParserRead(frame);
3.Decode(decodedAudioVideoFrame);

4. if (decodedAudioVideoFrameTimestamp < SeekTimestamp)
{
release audioVideoFrame;
}
else
render(decodedAudioVideoFrame);

weird video behaviour in Stagefright

In stagefright, if any weird behaviour is observed in video. Following
steps need to be taken:

1.we need to print time taken by parser and decoder.[To check any time
taken process involved]
2.Check any frame is dropped by enabling log [dropping late frame in
awesomeplayer.cpp]
3.Print logs in all sleep() fn in AwesomePlayer[while rendering
frames, threads might go to background and wont do anything because of
Sleep() fn
4.Check for any postVideoEvent(10000ms) this might delay the rendering
of frames. For optimization or any other reason, chipset vendors might
tune this
value

String comparison

Whenever we need to compare strings, what we can use it?

Text: abc bcd bcd abc
Pattern: abc bcd
[Ex: BHTML & BCSS codeforces problem]

we need to compare text and pattern using strcmp. But naive string
comparison takes more time.

Solution 1)we can use RobinKarp or KMP algorithm to reduce time. or
else we can do the following way to avoid the problem.


How to avoid this:

we can use array to store the strings without duplication.

Array [][]={ "abc","bcd"}

Text Array: {0,1,1,0}
Pattern Array: {0,1}

then apply naive comparison in TextArray and pattern Array.

Solution 2)Compare to string array, int array comparison will takes less time.

Solution 3) if we are using array also, we need to compare all the
elements in array on worst case to add or lookup.
in this case, what we can do to improve this ?

We can use Binary Search Tree to store strings. if the given
string is less than the root string,
we need to search it from left child of the string.if it is greater
than or equal to the rootstring, we need to search the
right child of the root.

STL map is using RedBlack tree implementation. we can make
use of map to store strings.STL map can also be used for Hashtable.

DecodeButDoNotRender

Insights on How to implement DecodeButDoNotRender flag in any
multimedia framework ?
This will happen when we dont have more I frames.

what is structure padding ?

what is structure padding ?

if the system is 32 bit system,
we are allocating memory like this:

struct test
{
char a;
int b;
};

It will allocate 8 bytes of memory in 32 bit system. For char,compiler
will allocate the 4 bytes. [char may be 1 or 2 bytes]
this is called data alignment. Data alignment means putting the data
at a memory offset equal to some multiple of the word size,
which increases the system's performance due to the way the CPU handles memory.
For char, 4 bytes are allocated. it will use only 1 bytes.Rest of the
bytes are filled with junk values. this is called structure padding.

For example, in 32 bit system,the data to be read should be at a
memory offset which is some multiple of 4.
if the data starts from the 18th byte, computer has to read two 4
bytes chunks to read the data.
if the data starts from multiple of 4[4,8,12,16,20], computer can read
4 byte chunk once to read the data.
If the read is from two virtual memory pages, then it will take more
time than expected.

In this way, padding improves performance.

if the data members are declared in descending order it will give
minimal wastage of bytes.

struct Test
{
char a;
int b;
char c;
};

sizeof(Test) is 12 bytes.

But if we declared like this, 8 bytes will be allocated for structure "Test".

struct Test
{

int b;
char c;
char a;
};

How to avoid structure paddding?
if we dont want to waste memory & tradeoff the performance,
we need to use pragma pack to align data.

How OMX core library is loaded for stagefright by chipset vendor like Qualcomm /Nvidia ?

How OMX core library is loaded for stagefright by chipset vendor like
Qualcomm /Nvidia ?

Qualcomm and NVIDIA processors will have built-in hardware codecs support.
They will provide the OMX components too. Their OMX core will be
loaded from libstagefrighthw.so .
This libstagefrighthw.so library will be loaded by stagefright in
OMXMaster.cpp in

addPlugin("libstagefrighthw.so");

vertical/horizontal sync in video

Video Is Composed of a Series of Still Images.
changing fast enough that it looks like continuous motion.
timing informations are called vertical sync/horizontal sync.

vertical sync - indicates when a new image is starting
horizontal sync -indicates when a new scanline is starting

Each still is composed of series of scanlines.

Interlaced vs Progressive:
For displays that "paint" an image on the screen, such as a CRT,
Interlaced-each image is displayed starting at the top left corner of
the display, moving to the right edge of the display.

Interlacing: First odd number of pixels are sent to display and then
even number of pixels are sent to display the image.
Advantage: we can reduce memory transfered to display by half for every image.

Progressive: pixels are displayed by sequence of lines.For Higher
resolution, we go for progressive.
Interlaced: First half of image is displayed on screen and then next
half of image is displayed

string searching algorithms with code

http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

code forces FileList problem

Code forces FileList problem :

PseudoCode:
==============

#define MAX_FILENAME 8
#define TwoContinuousDots 0
#define SingleCharBetweenTwoDots 1
#define MAX_FILE_EXT 11
#define EndsWithDot 0
#define MAX_EXT 3

1.read the string input
2.Identify the dot & break the loop
3.if (stringBeginsWith == Dot) return NO;
4.if (CurrentCharPosition > MAX_FILENAME) //DotPosition exceeds
MAX_FILENAME allowed || Dot is not available within 8 character
return NO;
5.Store the ++LastDotPos
6.start loop through the string till EOS reached
7.if [ currentDotPos - lastDotPos == TwoContinuousDots ] { return NO;}
8.if ( CurrentDotPos - lastDotPos == SingleCharBetweenTwoDots ) { return NO;}
9.if ( CurrentDotPos - lastDotPos > MAX_FILE_EXT ) return NO;

At Last of the string,
10.if( CurrentDotPos - lastDotPos == EndsWithDot ) return NO;
11.if( CurrentDotPos - lastDotPos > MAX_EXT ) return NO; //Last
extension exceeds MAXIMUM_EXTENSION size
12.Yes... we are going to parse the valid String
13.create loop1... Search First Dot
14.if (char == FirstDOT) create loop2 and look for SecondDOT
15.if no second DOT and EOS reached,print string. [Ex: t.txt]
16.if(TwoDotsDiff <= MAX_EXT) printf( secondDot + 1 char);Move i by 1
17.else print (3 characters) Move i by 3

Solve contest problems

To Solve any codeforces contest problems:

1)Prepare the testcases from the given problem statement
2)Prepare test samples
3)Prepare design
4)Check if any datastructure can be used & what will be the cons & pros
5)If multiple datastructure can be used, Identify the best
suitable datastructure
6) Sometimes tradeoff clarity/simplicity over efficiency
7) Once completed the code, test with test samples
8) if anyone has already submitted the problem, we can see the
testcases used for testing the solution.
we can check our code with codeforces simple testinputs
This will clarify if we misunderstood the problem statement.
[Ex: For Cd and PWd commands problem, from the problem
statement, I assumed that .. or / wont come at end.
But from the testsamples,I came to know this as a valid input]
9) Think on how to improve the code

After seeing others code,

1) Prepare testcases from code
2) Prepare testsamples to break the code
3) Randomly remove some lines of code and try to fix it...
This will give a chance to understand/read others code.

4.Identify any language functions/features used in code for
addressing particular scenarion & think of it
how to use it
5.Check the efficient code[less execution time] written by others
6.Check others code which is having clarity and simplicity

inspiring barefoot college

http://www.barefootcollege.org

How to traerse/print character by character in a string without using strlen() ?

How to traerse/print character by character in a string without using strlen() ?

Usually we will do like this:

char szString[100]={0};
scanf("%s",szString);

for(int i = 0; i <strlen(szString); i++);
{
printf("%c",szString[i];
}

without knowing strlen(), we can print the same thing as below:

char szString[100]={0};
scanf("%s",szString);

for(int i = 0; szString[i]; i++);
{
printf("%c",szString[i];
}

if szString reaches NULL, it will returns zero, so for loop will be
terminated for that case.

find trailing zeros & its importance

How to find trailing zeros in factorial ?

Input : 6 = 2 * 3 * 4 * 5 = 120 = Trailing zeros = 1
Output : 1

For more detailed tutorial :
http://www.purplemath.com/modules/factzero.htm

#include <stdio.h>

void main()
{
long n =0;
long div = 5;
long sum = 0;

printf("Enter N! value:");
scanf("%ld",&n);

while(n >= div)
{
sum += n/div;
div *= 5;
}
printf(" Output is :%ld", sum);
}

Importance of finding the trailing zeros will be useful in floating
point representation.

It will be used to represent floating numbers
as 2 * (10 ^ 3)
mantissa: 2
exponent: 3

Same will be used to represent negative numbers in floating point
representation;

2 * (10 ^ -3)

Self synchronization Explicit AV synchronization in Stagefright

Self Synchronization or Explicit AV synchronization:
This is used in any file format. while creating AVI/MPEG4 file,
audio and video encoder data wont be written as such.
Encoded Video and audio frames are written to the file based on interleaving.
AudioFrame: A0 A1 A2
VideoFrame: V0 V1 V2
After interleaving, the data will be as like this: V0 A0 V1 A1 V2 A2
Interleaved data is written into file.
Interleaving can be based on number of frames or duration. Let us say
inteleaved duration is for 1 seconds.
Android stagefright is supporting this interleaved duration. Until
interleave duration is reached, MPEG4Writer will buffers data
in list. Once the interleaved duration is reached, it will be
signalled to MPEG4WriterThread.
MPEG4 Writer thread will write the queued samples in to the file.

DirectX Transform Editing Services

http://sworks.com/keng/da/multimedia/dtrans/c++/ - we can have the code for the DirectX Transform samples
http://com.it-berater.org/COM/webbrowser/filters_reference.htm

course on search engine/ text mining

http://net.pku.edu.cn/~course/cs502/2003/