Friday, May 18, 2012

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...

No comments: