I was trying to download some journal article but library's connect from home feature seems having a problem. OK, I can ssh into my machine at school, but my Windows laptop does not give an easy way to launch X. How do I use only terminal to emulate a click on download pdf? At this point wget comes into mind.
The first attempt, wget ..., returns HTTP 403 refused.
Maybe the webserver just don't like wget?
a google search returns something helpful. Of course wget is on the not wanted list, but you can pretend you are a browser.
wget -U firefox http://.../full.pdf
This works.
Friday, September 30, 2011
Monday, September 26, 2011
unix grep
http://www.thegeekstuff.com/2011/01/advanced-regular-expressions-in-grep-command-with-10-examples-%E2%80%93-part-ii/
In this article, let us review some advanced regular expression with examples.
Example 1. OR Operation (|)
Pipe character (|) in grep is used to specify that either of two whole subexpressions occur in a position. “subexpression1|subexpression2″ matches either subexpression1 or subexpression2.
The following example will remove three various kind of comment lines in a file using OR in a grep command.
First, create a sample file called “comments”.
$ cat comments
This file shows the comment character in various programming/scripting languages
### Perl / shell scripting
If the Line starts with single hash symbol,
then its a comment in Perl and shell scripting.
' VB Scripting comment
The line should start with a single quote to comment in VB scripting.
// C programming single line comment.
Double slashes in the beginning of the line for single line comment in C.
The file called “comments” has perl,VB script and C programming comment lines. Now the following grep command searches for the line which does not start with # or single quote (‘) or double front slashes (//).
$ grep -v "^#\|^'\|^\/\/" comments
This file shows the comment character in various programming/scripting languages
If the Line starts with single hash symbol,
then its a comment in Perl and shell scripting.
The line should start with a single quote to comment in VB scripting.
Double slashes in the beginning of the line for single line comment in C.
Example 2. Character class expression
As we have seen in our previous regex article example 9, list of characters can be mentioned with in the square brackets to match only one out of several characters. Grep command supports some special character classes that denote certain common ranges. Few of them are listed here. Refer man page of grep to know various character class expressions.
[:digit:] Only the digits 0 to 9
[:alnum:] Any alphanumeric character 0 to 9 OR A to Z or a to z.
[:alpha:] Any alpha character A to Z or a to z.
[:blank:] Space and TAB characters only.
These are always used inside square brackets in the form [[:digit:]]. Now let us grep all the process Ids of ntpd daemon process using appropriate character class expression.
$ grep -e "ntpd\[[[:digit:]]\+\]" /var/log/messages.4
Oct 28 11:42:20 gstuff1 ntpd[2241]: synchronized to LOCAL(0), stratum 10
Oct 28 11:42:20 gstuff1 ntpd[2241]: synchronized to 15.11.13.123, stratum 3
Oct 28 12:33:31 gstuff1 ntpd[2241]: synchronized to LOCAL(0), stratum 10
Oct 28 12:50:46 gstuff1 ntpd[2241]: synchronized to 15.11.13.123, stratum 3
Oct 29 07:55:29 gstuff1 ntpd[2241]: time reset -0.180737 s
Example 3. M to N occurences ({m,n})
A regular expression followed by {m,n} indicates that the preceding item is matched at least m times, but not more than n times. The values of m and n must be non-negative and smaller than 255.
The following example prints the line if its in the range of 0 to 99999.
$ cat number
12
12345
123456
19816282
$ grep "^[0-9]\{1,5\}$" number
12
12345
The file called “number” has the list of numbers, the above grep command matches only the number which 1 (minimum is 0) to 5 digits (maximum 99999).
Note: For basic grep command examples, read 15 Practical Grep Command Examples.
Example 4. Exact M occurence ({m})
A Regular expression followed by {m} matches exactly m occurences of the preceding expression. The following grep command will display only the number which has 5 digits.
$ grep "^[0-9]\{5\}$" number
12345
Example 5. M or more occurences ({m,})
A Regular expression followed by {m,} matches m or more occurences of the preceding expression. The following grep command will display the number which has 5 or more digits.
$ grep "[0-9]\{5,\}" number
12345
123456
19816282
Note: Did you know that you can use bzgrep command to search for a string or a pattern (regular expression) on bzip2 compressed files.
Example 6. Word boundary (\b)
\b is to match for a word boundary. \b matches any character(s) at the beginning (\bxx) and/or end (xx\b) of a word, thus \bthe\b will find the but not thet, but \bthe will find they.
# grep -i "\bthe\b" comments
This file shows the comment character in various programming/scripting languages
If the Line starts with single hash symbol,
The line should start with a single quote to comment in VB scripting.
Double slashes in the beginning of the line for single line comment in C.
Example 7. Back references (\n)
Grouping the expressions for further use is available in grep through back-references. For ex, \([0-9]\)\1 matches two digit number in which both the digits are same number like 11,22,33 etc.,
# grep -e '^\(abc\)\1$'
abc
abcabc
abcabc
In the above grep command, it accepts the input the STDIN. when it reads the input “abc” it didnt match, The line “abcabc” matches with the given expression so it prints. If you want to use Extended regular expression its always preferred to use egrep command. grep with -e option also works like egrep, but you have to escape the special characters like paranthesis.
Note: You can also use zgrep command to to search inside a compressed gz file.
Example 8. Match the pattern “Object Oriented”
So far we have seen different tips in grep command, Now using those tips, let us match “object oriented” in various formats.
$ grep "OO\|\([oO]bject\( \|\-\)[oO]riented\)"
The above grep command matches the “OO”, “object oriented”, “Object-oriented” and etc.,
Example 9. Print the line “vowel singlecharacter samevowel”
The following grep command print all lines containing a vowel (a, e, i, o, or u) followed by a single character followed by the same vowel again. Thus, it will find eve or adam but not vera.
$ cat input
evening
adam
vera
$ grep "\([aeiou]\).\1" input
evening
adam
Example 10. Valid IP address
The following grep command matches only valid IP address.
$ cat input
15.12.141.121
255.255.255
255.255.255.255
256.125.124.124
$ egrep '\b(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?\.){3}(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)' input
15.12.141.121
255.255.255.255
In the regular expression given above, there are different conditions. These conditioned matches should occur three times and one more class is mentioned separately.
If it starts with 25, next number should be 0 to 5 (250 to 255)
If it starts with 2, next number could be 0-4 followed by 0-9 (200 to 249)
zero occurence of 0 or 1, 0-9, then zero occurence of any number between 0-9 (0 to 199)
Then dot character
In this article, let us review some advanced regular expression with examples.
Example 1. OR Operation (|)
Pipe character (|) in grep is used to specify that either of two whole subexpressions occur in a position. “subexpression1|subexpression2″ matches either subexpression1 or subexpression2.
The following example will remove three various kind of comment lines in a file using OR in a grep command.
First, create a sample file called “comments”.
$ cat comments
This file shows the comment character in various programming/scripting languages
### Perl / shell scripting
If the Line starts with single hash symbol,
then its a comment in Perl and shell scripting.
' VB Scripting comment
The line should start with a single quote to comment in VB scripting.
// C programming single line comment.
Double slashes in the beginning of the line for single line comment in C.
The file called “comments” has perl,VB script and C programming comment lines. Now the following grep command searches for the line which does not start with # or single quote (‘) or double front slashes (//).
$ grep -v "^#\|^'\|^\/\/" comments
This file shows the comment character in various programming/scripting languages
If the Line starts with single hash symbol,
then its a comment in Perl and shell scripting.
The line should start with a single quote to comment in VB scripting.
Double slashes in the beginning of the line for single line comment in C.
Example 2. Character class expression
As we have seen in our previous regex article example 9, list of characters can be mentioned with in the square brackets to match only one out of several characters. Grep command supports some special character classes that denote certain common ranges. Few of them are listed here. Refer man page of grep to know various character class expressions.
[:digit:] Only the digits 0 to 9
[:alnum:] Any alphanumeric character 0 to 9 OR A to Z or a to z.
[:alpha:] Any alpha character A to Z or a to z.
[:blank:] Space and TAB characters only.
These are always used inside square brackets in the form [[:digit:]]. Now let us grep all the process Ids of ntpd daemon process using appropriate character class expression.
$ grep -e "ntpd\[[[:digit:]]\+\]" /var/log/messages.4
Oct 28 11:42:20 gstuff1 ntpd[2241]: synchronized to LOCAL(0), stratum 10
Oct 28 11:42:20 gstuff1 ntpd[2241]: synchronized to 15.11.13.123, stratum 3
Oct 28 12:33:31 gstuff1 ntpd[2241]: synchronized to LOCAL(0), stratum 10
Oct 28 12:50:46 gstuff1 ntpd[2241]: synchronized to 15.11.13.123, stratum 3
Oct 29 07:55:29 gstuff1 ntpd[2241]: time reset -0.180737 s
Example 3. M to N occurences ({m,n})
A regular expression followed by {m,n} indicates that the preceding item is matched at least m times, but not more than n times. The values of m and n must be non-negative and smaller than 255.
The following example prints the line if its in the range of 0 to 99999.
$ cat number
12
12345
123456
19816282
$ grep "^[0-9]\{1,5\}$" number
12
12345
The file called “number” has the list of numbers, the above grep command matches only the number which 1 (minimum is 0) to 5 digits (maximum 99999).
Note: For basic grep command examples, read 15 Practical Grep Command Examples.
Example 4. Exact M occurence ({m})
A Regular expression followed by {m} matches exactly m occurences of the preceding expression. The following grep command will display only the number which has 5 digits.
$ grep "^[0-9]\{5\}$" number
12345
Example 5. M or more occurences ({m,})
A Regular expression followed by {m,} matches m or more occurences of the preceding expression. The following grep command will display the number which has 5 or more digits.
$ grep "[0-9]\{5,\}" number
12345
123456
19816282
Note: Did you know that you can use bzgrep command to search for a string or a pattern (regular expression) on bzip2 compressed files.
Example 6. Word boundary (\b)
\b is to match for a word boundary. \b matches any character(s) at the beginning (\bxx) and/or end (xx\b) of a word, thus \bthe\b will find the but not thet, but \bthe will find they.
# grep -i "\bthe\b" comments
This file shows the comment character in various programming/scripting languages
If the Line starts with single hash symbol,
The line should start with a single quote to comment in VB scripting.
Double slashes in the beginning of the line for single line comment in C.
Example 7. Back references (\n)
Grouping the expressions for further use is available in grep through back-references. For ex, \([0-9]\)\1 matches two digit number in which both the digits are same number like 11,22,33 etc.,
# grep -e '^\(abc\)\1$'
abc
abcabc
abcabc
In the above grep command, it accepts the input the STDIN. when it reads the input “abc” it didnt match, The line “abcabc” matches with the given expression so it prints. If you want to use Extended regular expression its always preferred to use egrep command. grep with -e option also works like egrep, but you have to escape the special characters like paranthesis.
Note: You can also use zgrep command to to search inside a compressed gz file.
Example 8. Match the pattern “Object Oriented”
So far we have seen different tips in grep command, Now using those tips, let us match “object oriented” in various formats.
$ grep "OO\|\([oO]bject\( \|\-\)[oO]riented\)"
The above grep command matches the “OO”, “object oriented”, “Object-oriented” and etc.,
Example 9. Print the line “vowel singlecharacter samevowel”
The following grep command print all lines containing a vowel (a, e, i, o, or u) followed by a single character followed by the same vowel again. Thus, it will find eve or adam but not vera.
$ cat input
evening
adam
vera
$ grep "\([aeiou]\).\1" input
evening
adam
Example 10. Valid IP address
The following grep command matches only valid IP address.
$ cat input
15.12.141.121
255.255.255
255.255.255.255
256.125.124.124
$ egrep '\b(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?\.){3}(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)' input
15.12.141.121
255.255.255.255
In the regular expression given above, there are different conditions. These conditioned matches should occur three times and one more class is mentioned separately.
If it starts with 25, next number should be 0 to 5 (250 to 255)
If it starts with 2, next number could be 0-4 followed by 0-9 (200 to 249)
zero occurence of 0 or 1, 0-9, then zero occurence of any number between 0-9 (0 to 199)
Then dot character
Saturday, September 24, 2011
CF problem 8D
http://codeforces.com/contest/8/problem/D
If t2 is big enough for Bob to visit shop before go home, then ans=dist(cinema,shop,house)+t1
Otherwise we look for a point p such that
for Alan, d(cinema,p) + d(p,shop) + d(shop,house) <= d(cinema,shop,house)+t1
for Bob, d(cinema,p) + d(p,house) <= d(cinema,house)+t2
The trajectory for Alan is an ellipse and the same is true for Bob. So we need to find the intersection of two ellipses. This seems a bit difficult to program.
If t2 is big enough for Bob to visit shop before go home, then ans=dist(cinema,shop,house)+t1
Otherwise we look for a point p such that
for Alan, d(cinema,p) + d(p,shop) + d(shop,house) <= d(cinema,shop,house)+t1
for Bob, d(cinema,p) + d(p,house) <= d(cinema,house)+t2
The trajectory for Alan is an ellipse and the same is true for Bob. So we need to find the intersection of two ellipses. This seems a bit difficult to program.
Friday, September 23, 2011
TC SRM 519
p600 RequiredSubstrings
you are given a vector of string as words, and C<=6, L<=50, each word in words has length <=50. You are to find out the number of strings with length=L and contains exactly C words as substring.
To build a dp solution, you need to remember a state. Clearly you work from len=1 to L, and you need to remember what subset of words you already seen, this is only 1<<6 = 128 so no problem. But you need more than that. Ideally you want all possible prefix of length k-1, when you work on len=k, but this is too much. So you need to cut down your state. Since to have a valid word in len=k, you can separate words already in len=k-1 and words end with the kth char. To get a word end at kth char, you need to have a prefix of some words. OK, so you remember the longest suffix of your string which is a prefix of some word. char appears before that you don't care. Now your state is
dp[len][index_in_prefix][bitset_of_words_contained]
So you built an array prefix[] containing all prefixes of all words including empty string, remove duplicates. Then for each prefix and each char=a_to_z, you construct two arrays, go[p][c] is the index in prefix of the longest suffix of string prefix[p]+char(c), cover[p][c] is the bitset of words covered by string prefix[p]+char(c).
Notice that you can build a trie for all the prefix for fast check whether a given string is a prefix.
you are given a vector of string as words, and C<=6, L<=50, each word in words has length <=50. You are to find out the number of strings with length=L and contains exactly C words as substring.
To build a dp solution, you need to remember a state. Clearly you work from len=1 to L, and you need to remember what subset of words you already seen, this is only 1<<6 = 128 so no problem. But you need more than that. Ideally you want all possible prefix of length k-1, when you work on len=k, but this is too much. So you need to cut down your state. Since to have a valid word in len=k, you can separate words already in len=k-1 and words end with the kth char. To get a word end at kth char, you need to have a prefix of some words. OK, so you remember the longest suffix of your string which is a prefix of some word. char appears before that you don't care. Now your state is
dp[len][index_in_prefix][bitset_of_words_contained]
So you built an array prefix[] containing all prefixes of all words including empty string, remove duplicates. Then for each prefix and each char=a_to_z, you construct two arrays, go[p][c] is the index in prefix of the longest suffix of string prefix[p]+char(c), cover[p][c] is the bitset of words covered by string prefix[p]+char(c).
Notice that you can build a trie for all the prefix for fast check whether a given string is a prefix.
CF #88
Solved A, WA on B, TLE on C.
A. A simulation problem, since t_i <= 10^8, you can run time from 0 to 10^8, then solve each person when their t_i matches current time. Of course you need to sort them by their t_i so that you can get them in O(1) time. B. Recognizing constraints. a and b can both be 10^9 so enumerating even one of them is a bad idea. But mod is only 10^7. So you can try all possible numbers for the first person, i=0 to min(a, mod-1), since if some other choice, say k makes first win, then k%mod would make it win as well. The first wins if i*10^9 + j !=0 % mod for all j=0 to b. In other words -i*10^9 % mod >= b+1
Last catch is integer overflow when you do the multiplication.
C. Tournament. First thing is to realize that brute force will not work. Checking all path of length 2 would be n^3 and n=5000, so you need something better. For tournament, wiki tells you that if a tournament has a cycle, then it has a cycle of length 3. And draw a picture you will see a ways to find the length-3 cycle. Now the rest is easy. Do a DFS or BFS, find any cycle, then find a length-3 cycle out of that cycle.
For DFS you need to remember parent[node] for each node to be able to reconstruct the cycle.
Last but not least, the input can be huge, as large as 2.5MB. So cin will kill you. Use scanf instead.
D. TODO
E. TODO
Summary: When div1 and div2 are together in the same round, the problem is usually easier.
rank 470, rating 1669 (-6)
A. A simulation problem, since t_i <= 10^8, you can run time from 0 to 10^8, then solve each person when their t_i matches current time. Of course you need to sort them by their t_i so that you can get them in O(1) time. B. Recognizing constraints. a and b can both be 10^9 so enumerating even one of them is a bad idea. But mod is only 10^7. So you can try all possible numbers for the first person, i=0 to min(a, mod-1), since if some other choice, say k makes first win, then k%mod would make it win as well. The first wins if i*10^9 + j !=0 % mod for all j=0 to b. In other words -i*10^9 % mod >= b+1
Last catch is integer overflow when you do the multiplication.
C. Tournament. First thing is to realize that brute force will not work. Checking all path of length 2 would be n^3 and n=5000, so you need something better. For tournament, wiki tells you that if a tournament has a cycle, then it has a cycle of length 3. And draw a picture you will see a ways to find the length-3 cycle. Now the rest is easy. Do a DFS or BFS, find any cycle, then find a length-3 cycle out of that cycle.
For DFS you need to remember parent[node] for each node to be able to reconstruct the cycle.
Last but not least, the input can be huge, as large as 2.5MB. So cin will kill you. Use scanf instead.
D. TODO
E. TODO
Summary: When div1 and div2 are together in the same round, the problem is usually easier.
rank 470, rating 1669 (-6)
Thursday, September 22, 2011
count bits
In GCC
__builtin_popcount(k)
In MSVC
unsigned short __popcnt16(
unsigned short value
);
unsigned int __popcnt(
unsigned int value
);
unsigned __int64 __popcnt64(
unsigned __int64 value
);
__builtin_popcount(k)
In MSVC
unsigned short __popcnt16(
unsigned short value
);
unsigned int __popcnt(
unsigned int value
);
unsigned __int64 __popcnt64(
unsigned __int64 value
);
#include <iostream>
#include <intrin.h>
using namespace std;
int main()
{
unsigned short us[3] = {0, 0xFF, 0xFFFF};
unsigned short usr;
unsigned int ui[4] = {0, 0xFF, 0xFFFF, 0xFFFFFFFF};
unsigned int uir;
for (int i=0; i<3; i++) {
usr = __popcnt16(us[i]);
cout << "__popcnt16(0x" << hex << us[i] << ") = " << dec << usr << endl;
}
for (int i=0; i<4; i++) {
uir = __popcnt(ui[i]);
cout << "__popcnt(0x" << hex << ui[i] << ") = " << dec << uir << endl;
}
}
Thursday, September 15, 2011
CF #87
A - Party
Find longest chain in a DAG, and each node has at most one predecessor. A simple DP in topological order.
Passed.
B - Lawnmower
This is an implementation problem. When work on row[i], assume you are moving right, then you have to arrive right[i]. Then you need to look at next nonempty row[k], if row[k] is moving right, then you have to move to left[k], otherwise row[k] is moving left and you have to move to right[k]. You also need to count in the steps moving between rows. And you stop when you have visited all 'W' cells. Notice that you do NOT have to end at last row.
The DP idea below got TLE.
It appears that your move is essentially fixed as you can only go down and in each row you can only move to one direction, left or right. But then you can have several empty rows in between and this will affect your move. So another DP problem. dp[row][first][last] is the number of moves you need to complete current row to last row. If you have some W cells outside [first,last], then it is infeasible and dp[][][] is INF. However during contest forgot to check outside last and didn't finish.
D - Unambiguous Arithmetic Expression
Hacked as TLE. My solution need 1000^3=10^9 and seems too slow. On local machine, the hacking case
1+1+1+...+1 runs in 26s.
Didn't get a good idea about C and E.
rating: 1711 to 1675, almost into div2.
C - Plumber I have to read the tutorial to get the problem. It looks you should arrange from top to bottom, from left to right. But the constraint is huge, each cell has 4 possible orientations and you have 10^5 cells. Even try to enumerate one row seems prohibitive. Now is the catch. When the constraints seem too big, any DP strategy destined to doom, there is a simple formula to count. If it is only 1D, then everybody sees it. Each plumber is either left or right, and once the first one is determined, then every cell will be determined in the same row. So you have the solution now. Each row, and each column, has to have plumbers alternating. That is, for a row, if the first one is chosen to be left, then 2nd one is right, and 3rd one is left and 4th one is right and so on. So you just check 2 possible orientations for each row. If both are good, then your ans will be multiplied by 2, if only one is good, then your ans does not change, if neither is good, you know your ans is zero.
Find longest chain in a DAG, and each node has at most one predecessor. A simple DP in topological order.
Passed.
B - Lawnmower
This is an implementation problem. When work on row[i], assume you are moving right, then you have to arrive right[i]. Then you need to look at next nonempty row[k], if row[k] is moving right, then you have to move to left[k], otherwise row[k] is moving left and you have to move to right[k]. You also need to count in the steps moving between rows. And you stop when you have visited all 'W' cells. Notice that you do NOT have to end at last row.
The DP idea below got TLE.
It appears that your move is essentially fixed as you can only go down and in each row you can only move to one direction, left or right. But then you can have several empty rows in between and this will affect your move. So another DP problem. dp[row][first][last] is the number of moves you need to complete current row to last row. If you have some W cells outside [first,last], then it is infeasible and dp[][][] is INF. However during contest forgot to check outside last and didn't finish.
D - Unambiguous Arithmetic Expression
Hacked as TLE. My solution need 1000^3=10^9 and seems too slow. On local machine, the hacking case
1+1+1+...+1 runs in 26s.
Didn't get a good idea about C and E.
rating: 1711 to 1675, almost into div2.
C - Plumber I have to read the tutorial to get the problem. It looks you should arrange from top to bottom, from left to right. But the constraint is huge, each cell has 4 possible orientations and you have 10^5 cells. Even try to enumerate one row seems prohibitive. Now is the catch. When the constraints seem too big, any DP strategy destined to doom, there is a simple formula to count. If it is only 1D, then everybody sees it. Each plumber is either left or right, and once the first one is determined, then every cell will be determined in the same row. So you have the solution now. Each row, and each column, has to have plumbers alternating. That is, for a row, if the first one is chosen to be left, then 2nd one is right, and 3rd one is left and 4th one is right and so on. So you just check 2 possible orientations for each row. If both are good, then your ans will be multiplied by 2, if only one is good, then your ans does not change, if neither is good, you know your ans is zero.
Subscribe to:
Posts (Atom)
