Got two more, now 26/29 solved

Problem solving and Point in Plane.

Problem solving: Dilworth theorem and use bipartite matching. I have to use Hopcroft and Karp's O(n^2.5) algorithm as the graph is dense, and I need some early termination when doing BFS to set up layers. Anyway it is pretty fast after that implementation optimization. Knowing algorithm seems not enough.

Point in Plane: calculating the min number of turns is easy, but counting is a bit tricky. My first idea is to enumerate all bit masks but this will give 2^16*2^16 which is way to slow for even a single case, not to mention T=50 cases. Then it is simple to notice that each submask you remove must be collinear and you can order the sequence by the bit pattern you removed in each turn so that pt[0] always being the first point to remove. The advantage is that then you can simply multiply by factorial of number of opt move to get the count, because each op in a seq is different and between different seq they have at least one op different because the first op is different: pt[0] is with a different subset of points. One trick is to enumerate all subsets of a given bit pattern with a simple loop:
for(int i=b; i>0; i=(i-1)&b)

I know I have seen this somewhere before but have to google it to find from stackoverflow.com

Now I have only 3 unsolved, with xorkey passed 10/11 and TLE on the last.
The other two are:
lucky numbers, with 10^4 cases seems I need a better DP, or I can manipulate the 10^4 cases somehow.
count scoreboard, this one is tough, with only 8 people solved. The least solved problem so far.

my first programming competition shirt from Spotify Code Quest 2012

Solved 2 out of 8 and placed 47th. Top 100 get shirts.
One of them is easy and the other one is a DP problem.
After looking at the solution, I should probably get 4 out of 8. Problems are set by KTH and Per Austrin is one of the solution writers.
==================================
Hi there!

Congratulations on making it into the top 100 contestants in the Spotify Code Quest 2012! As promised will you receive a t-shirt for your efforts, so please fill in the following form so we can send it to you as soon as possible!

Best regards
The Spotify Code Quest Team

knocked down qudrant query and changing bits

Made several stupid mistakes in changing bits but got it eventually. O(sqrt(N)) per query is fast enough. Now I got 24/29 solved.

Solved Problems

String Reduction: greedy with reducing max cnt char

Permutation game: easy bit

Task Scheduling: segment tree

Circle Summation: matrix mult

Quadrant Queries: segment tree

K Difference: easy

String Transmission

EQUATIONS: factor

Lego Blocks: dp with a wall to cut

Grid Walking: dp with precalculation

String Similarity

Substring Diff

Vertical Sticks: indepdently calculate each stick

FIND STRINGS

ARITHMETIC PROGRESSIONS: ans is q!*d^q1*d^q2..., when q is more than MOD, then ans is 0

Meeting Point: axis transformation to get L1 norm

Changing Bits: blocks of sqrt(N)

Save Humanity: overlap two prefix match (forward and reverse) to obtain a match with 1 error

Stone Piles: Grundy number and sum of games, very tricky

Billboards: minimize throw away, sliding window

Kingdom Connectivity: topological sort with cycle detection

Square Subsequences: try all split and find common substr

Fairy Chess: moving diamond and edges

Connect the country: simulation

square subsequence, now 12th

I think I had squared subsequence and I did. Now placed at 12th!

The idea is to try all possible ways to break s[] into s1[] and s2[] and count the number of equal subseq in both s1[] and s2[] with the last char of s1 matched.

The recurrence is common[n1][n2] = common[n1][n2-1] + common[n1-1][n2] - common[n1-1][n2-1]
we add back common[n1-1][n2-1] if s1[n1-1] match s2[n2-1].

# Status Signal Time
1 Passed Your code produced correct output for this testcase. 0.07061
2 Passed Your code produced correct output for this testcase. 0.070552
3 Passed Your code produced correct output for this testcase. 0.564724
4 Passed Your code produced correct output for this testcase. 0.503675
5 Passed Your code produced correct output for this testcase. 0.383056
6 Passed Your code produced correct output for this testcase. 0.514264
7 Passed Your code produced correct output for this testcase. 0.695142
8 Passed Your code produced correct output for this testcase. 0.524266
9 Passed Your code produced correct output for this testcase. 0.556575
10 Passed Your code produced correct output for this testcase. 0.473493

Rank Hacker Country Score Submissions Solved
11 diogoaos Brazil 811.00 56 21
12 lantimilan USA 784.00 79 19
13 liangjiaxing Canada 778.00 50 19
14 jin.ubc Canada 763.00 42 20
15 uwi Japan 760.00 39 19
15 megaterik Belarus 760.00 102 22
17 hadi Iran 740.00 48 19
18 Amtrix Germany 735.00 20 19
19 chhung6 Hong Kong 732.00 76 19
20 ttim Kazakhstan 730.00 95 19

truly amazing, am now 14th

Rank Hacker Country Score Submissions Solved
11 diogoaos Brazil 811.00 55 21
12 liangjiaxing Canada 778.00 50 19
13 jin.ubc Canada 763.00 42 20
14 lantimilan USA 761.00 78 18
15 uwi Japan 760.00 39 19
15 megaterik Belarus 760.00 102 22
17 hadi Iran 740.00 48 19
18 Amtrix Germany 735.00 20 19
19 chhung6 Hong Kong 732.00 76 19
20 yuke Canada 730.00 39 19

Fairy Chess cpp 2012-02-16 14:10:49 Processed Accepted View Details
Fairy Chess cpp 2012-02-16 14:03:34 Processed Wrong Answer
0/8 testcases passed
View Details
Fairy Chess cpp 2012-02-16 13:37:18 Processed Wrong Answer
5/8 testcases passed
View Details
Fairy Chess cpp 2012-02-16 11:49:12 Processed Wrong Answer
2/8 testcases passed
View Details
Fairy Chess cpp 2012-02-16 11:48:07 Processed Wrong Answer
1/8 testcases passed
View Details

fairy chess

although my submission only passed 2/8, and TLE for the rest 6 cases, I entered top 20 for the first time. (TLE is better than WA)

Rank Hacker Country Score Submissions Solved
11 diogoaos Brazil 811.00 55 21
12 liangjiaxing Canada 778.00 50 19
13 jin.ubc Canada 763.00 42 20
14 uwi Japan 760.00 39 19
14 megaterik Belarus 760.00 102 22
16 hadi Iran 740.00 48 19
17 Amtrix Germany 735.00 20 19
18 lantimilan USA 733.00 75 17
19 chhung6 Hong Kong 732.00 76 19
20 yuke Canada 730.00 39 19

Submissions /
Fairy Chess
# Status Signal Time
1 Passed Your code produced correct output for this testcase. 2.77617
2 Failed Your code exceeded the timelimit for this testcase. 6.00837
3 Failed Your code exceeded the timelimit for this testcase. 9.25258
4 Failed Your code exceeded the timelimit for this testcase. 12.4928
5 Failed Your code exceeded the timelimit for this testcase. 15.721
6 Passed Your code produced correct output for this testcase. 18.9332
7 Failed Your code exceeded the timelimit for this testcase. 22.1734
8 Failed Your code exceeded the timelimit for this testcase. 25.4016

hey, I made into top 20, page 2 on leader board

Rank Hacker Country Score Submissions Solved
11 diogoaos Brazil 800.00 54 21
12 liangjiaxing Canada 778.00 51 19
13 jin.ubc Canada 763.00 42 20
14 uwi Japan 760.00 39 19
14 megaterik Belarus 760.00 103 22
16 Amtrix Germany 735.00 20 19
17 chhung6 Hong Kong 732.00 77 19
18 yuke Canada 730.00 39 19
18 ttim Kazakhstan 730.00 96 19
20 lantimilan USA 728.00 75 17

solved save humanity, now at 20, career high

Rank Hacker Country Score Submissions Solved
21 lantimilan USA 728.00 75 17

Save Humanity cpp 2012-02-15 01:36:07 Processed Accepted View Details

Somehow I got promoted to 20th, without work.

11 diogoaos Brazil 800.00 54 21
12 liangjiaxing Canada 778.00 51 19
13 jin.ubc Canada 763.00 42 20
14 uwi Japan 760.00 39 19
14 megaterik Belarus 760.00 103 22
16 Amtrix Germany 735.00 20 19
17 chhung6 Hong Kong 732.00 77 19
18 yuke Canada 730.00 39 19
18 ttim Kazakhstan 730.00 96 19
20 lantimilan USA 726.00 74 17

solved stone piles

A rather tough problem but got lucky in finding Sprague-Grundy theory.
with this success now I am career high rank 24

24 lantimilan USA 698.00 72 16

21 openendings Australia 710.00 22 18
21 MemSQL USA 710.00 21 18
21 KVF Ukraine 710.00 45 17
24 lantimilan USA 698.00 72 16
25 turuthok USA 697.00 52 17
26 nima.aghdaii Canada 679.00 64 17
27 imbanoob Canada 673.00 43 17
28 stormclass China 662.00 76 18
29 Lanbo Chen China 659.00 64 17
30 sevenkplus China 656.00 25 15

fedora 16 notes

To install a network printer, enable ipp port
system-config-firewall
need to reboot
By default, CUPS uses TCP port 631 for network communication. If you're connecting to a print server running CUPS, ensure the server firewall allows connections on port 631.
then system-config-printer (yum install this if not available)

Annoying things, the new gnome UI looks more like Mac now, alt-tab does not switch between terminal windows, there is no Minimize or Maximize window short-cut key.

rpm commands

repoquery --list glibc.i686
yum search keyword

To burn CD/DVD: Using Brasero in GNOME

IP address and config network manager: nmcli dev list or nm-tools

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}