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

svn file restore older versions

To restore the version of the file.sh from the lastest commit, type this :
[pene@donunix] svn revert file.sh

To get the version form the release number 214 :
[pene@donunix] svn update -r 214 file.sh

The above is from http://donunix.blogspot.com/2008/04/svn-file-restore-older-versions.html
Don Unix - Unix Tips n Tricks

interview street challenge update

Solved string reduction. Now have 7.

Claire gave a very simple solution which also has a simple proof of correctness. Keep working on char with max cnt and another neighboring char until no more operation is possible. You must be left with 1 or 2 equal char. My solution is much more complicated and I do not have a good proof so far.

Your rank: 71
Your score: 460.625

Jan 6 update: hacked the bipartite matching code a bit and had 2 more testcases passed for problem solving problem.
Your rank: 66
Your score: 479.625

Jan 7 update: one more problem AC, string transmission. enumerate all periods and some simple DP with memorization.

Your rank: 63
Your score: 513.5

It gets harder to move up in rank now.

Jan 08 update
Had 2/10 for circle summation. Why TLE.
After 3 TLE, lost all 6pt earned for this problem. Back to 63.

solved circle summation, need O(N^2 logM) where N=50, M=10^9
Your rank: 61
Your score: 526
Rank Hacker Country Score Submissions Solved
61 lantimilan NA 526.00 36 9

Solved Equations, the answer is derived by x*y/(x+y)=N! and then ans is the number of factors of N!^2.
EQUATIONS C++
Submission Accepted
15/15 testcases passed
45 Point(s)
View Submission Processed 2012-01-09 01:22 UTC

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.

CF #100

This round is special since there will be 100 shirts to top 100 coders. End up #471 and far from top 100. Actually this is a good time to get shirts because problem A-D are easy and E,F are hard. About 20 people get E or F so if you can make A-D reasonably fast, you get to top 100. I was lucky enough to get B and D, but A and C failed pretest.

A is easy but I didn't add eps when dealing with floating point.
C is not that easy and took me quite a while to realize what I did was wrong. Nonetheless I was able to fix it quickly after the contest, a priority_queue or set suffices.

B is brute-force with some careful book keeping.

D is greedy although I do not have a proof.

Luckily I got B and D and rating was up to 1768(+105) and now in div1.