interview street challenge update: rank 26 solve 13

26 lantimilan NA 947.00 54 13

After solve meeting point, I got one step up in the rank. However, meeting point is not actually very interesting and I should have AC long before. L1 distance is easy because x and y dimension are independent. Linf is a bit different, it seems. Linf is also called Chebyshev distance. Wiki told you that Linf can be converted into L1 by rotating the (x,y) coordinates by 45deg. So you are solving L1 distance instead and that is easy. I got a WA because of integer overflow.

Meeting Point C++
Submission Accepted
13/13 testcases passed
50 Point(s)
View Submission Processed 2012-01-21 23:33 UTC
Meeting Point C++
Wrong Answer
4/13 testcases passed
8 Point(s) View Submission Processed 2012-01-21 23:22 UTC

interview street challenge update: rank 27 solve 12

27 lantimilan NA 847.00 52 12

After pass 10/11 in xorkey, I moved myself to 27, a career high.

However, my interval tree must have some problem since I got both 10/11 in xorkey and quadrant, both of which are range query problems and use the same data structure. There is almost no algorithm involved except maintain the data structure, which is interval tree or range tree or augmented binary tree. Now I am not sure which name is the appropriate one.

The idea for xorkey is to maintain a sorted subseq in each interval and then query bit-by-bit. However keep a vector inside a node is too expensive, as I got bad_alloc in local test. Instead put all data into a big array and only maintain a pointer to the start and stop index in that array.

Name Language Result Submission Status Submission time
XOR key C++
Time Limit Exceeded
10/11 testcases passed
40 Point(s) View Submission Processed 2012-01-15 21:21 UTC
XOR key C++
Time Limit Exceeded
1/11 testcases passed
2 Point(s) View Submission Processed 2012-01-15 19:31 UTC
XOR key C++
Time Limit Exceeded
1/11 testcases passed
2 Point(s) View Submission Processed 2012-01-14 20:56 UTC

interview street challenge update: 29 now

29 lantimilan NA 807.00 49 12

After getting 12/13 in quadrant and 3/9 in arithmetic progression, I am in 29 now.

Recent submissions
Name Language Result Submission Status Submission time
ARITHMETIC PROGRESSIONS C++
Wrong Answer
3/9 testcases passed
7 Point(s) View Submission Processed 2012-01-13 18:21 UTC
ARITHMETIC PROGRESSIONS C++
Segmentation fault
3/9 testcases passed
7 Point(s) View Submission Processed 2012-01-13 18:06 UTC
Quadrant Queries C++
Time Limit Exceeded
10/11 testcases passed
25 Point(s) View Submission Processed 2012-01-13 09:27 UTC
Quadrant Queries C++
Wrong Answer
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-13 06:46 UTC
Quadrant Queries C++
Wrong Answer
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-13 00:32 UTC
Points in a Plane C++
Time Limit Exceeded
1/10 testcases passed
3 Point(s) View Submission Processed 2012-01-12 01:46 UTC

interview street challenge update: still 12 solved

30 lantimilan NA 803.00 47 12

Recent submissions: Why even logN per query TLE for Quadrant problem?

Name Language Result Submission Status Submission time
Quadrant Queries C++
Time Limit Exceeded
10/11 testcases passed
25 Point(s) View Submission Processed 2012-01-13 09:27 UTC
Quadrant Queries C++
Wrong Answer
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-13 06:46 UTC
Quadrant Queries C++
Wrong Answer
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-13 00:32 UTC
Points in a Plane C++
Time Limit Exceeded
1/10 testcases passed
3 Point(s) View Submission Processed 2012-01-12 01:46 UTC
ARITHMETIC PROGRESSIONS C++
Time Limit Exceeded
2/9 testcases passed
3 Point(s) View Submission Processed 2012-01-10 00:00 UTC
Quadrant Queries C++
Time Limit Exceeded
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-09 18:41 UTC
Quadrant Queries C++
Wrong Answer
1/11 testcases passed
0.5 Point(s) View Submission Processed 2012-01-09 17:29 UTC
Task Scheduling C++
Submission Accepted
10/10 testcases passed
30 Point(s)
View Submission Processed 2012-01-09 16:31 UTC
Lego Blocks C++
Submission Accepted
10/10 testcases passed
50 Point(s)
View Submission Processed 2012-01-09 05:42 UTC
EQUATIONS C++
Submission Accepted
15/15 testcases passed
45 Point(s)
View Submission Processed 2012-01-09 01:22 UTC

latex squeeze vertical space, spell check

http://dcwww.camd.dtu.dk/~schiotz/comp/LatexTips/LatexTips.html

\begin{itemize}\addtolength{\itemsep}{-0.5\baselineskip}


\usepackage{bibspacing}
\setlength{\bibspacing}{\baselineskip}

Solution: The tweaklist.sty package redefines the itemize, enumerate and description packages, so that all parameters can be adjusted. This was done by copying the original definitions, and adding "hook commands" that are executed when entering the environment. The hook commands are initially empty, but can be redefined with \renewcommand.

ispell -t filename.tex

interview street challenge update: 12 solved

32 lantimilan NA 778.50 43 12

TLE for both quadrant query and arithmetic progression, guess O(Q*sqrt(N)) is not fast enough for them.
Although I passed 2/9 for arithmetic progression. Now ranked 33.

33 lantimilan NA 762.50 43 12

Rank Hacker Country Score Submissions Solved
34 lantimilan NA 759.50 42 12
Task Scheduling C++
Submission Accepted
10/10 testcases passed
30 Point(s)
View Submission Processed 2012-01-09 16:31 UTC

Rank Hacker Country Score Submissions Solved
37 lantimilan NA 701.00 39 11

Lego blocks: A simple DP problem, I don't know why I didn't solve it earlier.

Lego Blocks C++
Submission Accepted
10/10 testcases passed
50 Point(s)
View Submission Processed 2012-01-09 05:42 UTC

Now has 11. The remaining problems would be tough.

interview street challenge update: 10 solved

I am in top 50 now, with 10 solved.
================================
Rank Hacker Country Score Submissions Solved
49 lantimilan NA 616.00 38 10
================================

Solved this weekend:

EQUATIONS C++
Submission Accepted
15/15 testcases passed
45 Point(s)
View Submission Processed 2012-01-09 01:22 UTC

Circle Summation C++
Submission Accepted
10/10 testcases passed
30 Point(s)
View Submission Processed 2012-01-08 18:16 UTC

String Transmission C++
Submission Accepted
10/10 testcases passed
30 Point(s)
View Submission Processed 2012-01-08 05:32 UTC