CF 106 div2

A: sort to decreasing order, take elements till >=k, watch for k=0 and -1
B: the only -1 case is when both hh and mm are single digit. Otherwise check r=base to 60. base is max digit already show up +1
C: sort increasingly and assign alternatively will work. The induction proof relies on that previous diff is no more than next element.
D: DP with calc(begin, end, c1, c2) computes #coloring with [begin,end) and begin-1 has c1 and end has c2. Need to consider two cases, (...) and (...)( ), and enumerate all 0,1,2 coloring.
E: forward and backward KMP to compute front[] and back[] where front[i] is longest prefix that matches s[0..i] and back is the longest suffix that matches s[n-1..n-1-i]. reverse s[] to compute back[]. To implement KMP needs some careful indexing and initialization. Watch for off-by-one and index-out-of-bounds.

Fixing wrong labels

The command \label must appear after (or inside) \caption. Otherwise, it will pick up the current section or list number instead of what you intended.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{gull}
\caption{Close-up of a gull} \label{fig:gull}
\end{figure}

latex algorithm package options

\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\algsetup{indent=2em}
\floatname{algorithm}{LPR}

noend does not print endfor endif
indentation can be customized as well.
floatname will name algorithm as LPR1, LPR2, LPR3, ...

latex customized enumerate list

Latex allows the creation of enumerated (ordered) lists up to four deep. The numbering styles for each depth can be styled to suit your needs using the \renewcommand{label}{style} command, where label is the list depth being styled and style is how you want that number to be shown.

label may be any of the following:

\labelenumi: first level
\labelenumii: second level
\labelenumiii: third level
\labelenumiv: fourth level

style may be any combination of characters and numbers. The item number for each list may be printed using by using any of the following (from first depth to fourth depth):

enumi
enumii
enumiii
enumiv

These numbers may be styled with the following macros:

\alph{number}: lowercase letters
\Alph{number}: uppercase letters
\arabic{number}: numbers
\roman{number}: lowercase roman numerals
\Roman{number}: uppercase roman numerals

That’s a lot to take in, so let’s look at an example. If we want to generate a list which is numbered a style like this:

1. First level
1. a) Second level
1. a) i: Third level

Then we would style the list like so:

\renewcommand{\labelenumi}{\arabic{enumi}. }
\renewcommand{\labelenumii}{\labelenumi\alph{enumii}) }
\renewcommand{\labelenumiii}{\labelenumii\roman{enumiii}: }

This would be added to the top of the document, before \begin{document}.

\begin{enumerate}
\renewcommand{\theenumi}{P\arabic{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{(\alph{enumii})}
\renewcommand{\labelenumii}{\theenumii}
\end{enumerate}

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