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.