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.