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.
Wednesday, September 14, 2011
declare var to the wrong type
I got caught by this issue when working on CF #82 div2, problem D, Treasure Island. It seems a straightforward problem and I implemented the naive idea. This will TLE but this is not my problem at this point. I got WA for testcase #38. However the testcase is too big to be shown fully on the submission page. I looked at my code, and a few AC code. Looks the only difference is that they precomputed dp[4][1000][1000], the max distance you can travel from cell[i][j] with direction[x]. This will speed up considerably, from 10^9 to 10^6. I know, but I got WA, not TLE. So what went wrong here.
Looking at my code, tried a couple of different things. Changing scanf to cin, change char[] to string, change [] to vector. None helps. Tried to generate some random input and run my code as well as some AC code. They agree. Plus to generate a nontrivial testcase for this problem is not that easy. I almost gave up and wrote a message to the problem setter for the complete testcase. Then something just kept pulling me back to the problem. Fix it.
My last resort was to hack the testcase. I tried to output some debugging information for that specific case. For CF it is not easy. I have to get around earlier testcases before reaching the testcase #38. Once I was there, something apparently wrong surfaces. Whenever inst.len > 128, the step went wrong. I still don't get it and switched between the naive impl and the speed-up version. Finally, I realized something. And that was it. I wrote
char dir=inst.dir, len=inst.len;
and then len is of type char and happens to be at most 128 on CF machine.
That was it.
Integer overflow are among the hardest bugs to ferret out. And when it bites, it hurts greatly.
Looking at my code, tried a couple of different things. Changing scanf to cin, change char[] to string, change [] to vector. None helps. Tried to generate some random input and run my code as well as some AC code. They agree. Plus to generate a nontrivial testcase for this problem is not that easy. I almost gave up and wrote a message to the problem setter for the complete testcase. Then something just kept pulling me back to the problem. Fix it.
My last resort was to hack the testcase. I tried to output some debugging information for that specific case. For CF it is not easy. I have to get around earlier testcases before reaching the testcase #38. Once I was there, something apparently wrong surfaces. Whenever inst.len > 128, the step went wrong. I still don't get it and switched between the naive impl and the speed-up version. Finally, I realized something. And that was it. I wrote
char dir=inst.dir, len=inst.len;
and then len is of type char and happens to be at most 128 on CF machine.
That was it.
Integer overflow are among the hardest bugs to ferret out. And when it bites, it hurts greatly.
Tuesday, September 13, 2011
TC SRM 517 div2 p1000 CuttingGrass
// srm517div2p1000.cpp
//
// 1. each pos is cut <= 1 times
// if not, then can postpone the first cut to merge with the second cut, this
// results in a better configuration
//
// 2. once a subset of pos are cut, then the best way is to order cuts by
// increasing grow[pos]
//
// The DP solution is to calc(int day, int pos, int T), the total height
// for grass[pos..N-1] after we decide cuts up to day.
// and we try all T=1,...,N
//
// another solution is to use max-weight-matching, due to idy
// L is grass set, R is day set
// w[l][r] = height that got cut if we cut grass[l] at day[r]
// try all T=1,...,N
// find a max-weight-matching of size T, then the total height is
// sum init[i]+grow[i]*T - matching
//
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct Grass
{
int grow, init;
};
bool operator<(const Grass &g1, const Grass &g2)
{
return g1.grow < g2.grow;
}
int N;
vector<Grass> G;
int dp[51][51]; // day,pos
class CuttingGrass
{
public:
int theMin(vector<int> init, vector<int> grow, int H);
};
int calc(int day, int pos, int T)
{
if (pos>=N) return 0;
int &ans=dp[day][pos];
if (ans>=0) return ans;
ans = G[pos].init+G[pos].grow*T + calc(day,pos+1,T);// no cut on pos
if (day<T) {
int tmp = G[pos].grow*(T-day-1) + calc(day+1,pos+1,T); // cut on pos
ans=min(ans,tmp);
}
return ans;
}
int CuttingGrass::theMin(vector<int> init, vector<int> grow, int H)
{
N=int(init.size());
int sum=0;
for(int i=0; i<N; ++i) sum+=init[i];
if (sum<=H) return 0;
G.resize(N);
for(int i=0; i<N; ++i) { Grass g={grow[i],init[i]}; G[i]=g; }
sort(G.begin(), G.end());
for(int t=1; t<=N; ++t)
{
memset(dp,-1,sizeof dp);
if (calc(0,0,t)<=H) return t;
}
return -1;
}
Friday, September 9, 2011
CF #85
Problem C.
Notice that nxm <= 40, so min(n,m)<=6, suppose n<=6, at most 6 columns;
for each row, try 2^6 ways to put spiders.
use dp with memorization to solve(m,prev,mask), prev is the bitset of row[r-1], mask is the cells in previous row that not covered yet, they have to be covered by current row.
Notice that nxm <= 40, so min(n,m)<=6, suppose n<=6, at most 6 columns;
for each row, try 2^6 ways to put spiders.
use dp with memorization to solve(m,prev,mask), prev is the bitset of row[r-1], mask is the cells in previous row that not covered yet, they have to be covered by current row.
Thursday, September 8, 2011
CF #86
Failed all submissions,
http://codeforces.ru/contest/113/problem/A
problem A, WA. Passed A offline. Too many places went wrong. Need to be more careful. The problem is straightforward.
1. check each word to be valid
2. if only one word, return true
3. get type=0 (adj), then type=1(noun), then type=2(verb)
if there are words remaining, return false
if both genders appear, return false
if count of type[1] is not 1, return false
return true if none of above apply.!
problem B, hacked
The problem asks for all distinct substring that has a given prefix and a given suffix. SPOJ has a similar problem asks for the number of distinct substr, with n=1000.
One idea is to use suffix array, and count each l=1,2,...,n distinct prefix. However this seems too slow. My implementation accepted when using MSVC++, but TLE in GNU C++ 4.6. Shocking enough, there are solutions run in 10ms, while mine is 1.40s under MSVC++.
A faulty implementation of naive string matching. A correct one is:
problem C, know will TLE and it did.
You want to use Sieve of Eratosthenes but memory is an issue because N is 3x10^8. However bitset or vector<bool> fits in memory limit. Also optimizations for the sieve helps, when at elem=p, start marking at p^2 instead of 2p, and take increment of 2p instead of p.
The following number theory result might also help.
Fermat's theorem on sums of two squares
From Wikipedia, the free encyclopedia
In additive number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
p = x^2 + y^2
with x and y integers, if and only if
p = 1 mod 4.
For the prime sieve method, a recent result by
Jonathan P. Sorenson, The Pseudosquares Prime Sieve
might also be of interest.
http://codeforces.ru/contest/113/problem/A
problem A, WA. Passed A offline. Too many places went wrong. Need to be more careful. The problem is straightforward.
1. check each word to be valid
2. if only one word, return true
3. get type=0 (adj), then type=1(noun), then type=2(verb)
if there are words remaining, return false
if both genders appear, return false
if count of type[1] is not 1, return false
return true if none of above apply.!
problem B, hacked
The problem asks for all distinct substring that has a given prefix and a given suffix. SPOJ has a similar problem asks for the number of distinct substr, with n=1000.
One idea is to use suffix array, and count each l=1,2,...,n distinct prefix. However this seems too slow. My implementation accepted when using MSVC++, but TLE in GNU C++ 4.6. Shocking enough, there are solutions run in 10ms, while mine is 1.40s under MSVC++.
A faulty implementation of naive string matching. A correct one is:
n=len(text); m=len(patt)
vector<int> ans;
for i=0 to n-1
{
for j=0 to m-1
if (i+j >= n || text[i+j] != patt[j]) break;
if (j>=m) ans.push_back(i); // found a match
}
return ans;
problem C, know will TLE and it did.
You want to use Sieve of Eratosthenes but memory is an issue because N is 3x10^8. However bitset
The following number theory result might also help.
Fermat's theorem on sums of two squares
From Wikipedia, the free encyclopedia
In additive number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
p = x^2 + y^2
with x and y integers, if and only if
p = 1 mod 4.
For the prime sieve method, a recent result by
Jonathan P. Sorenson, The Pseudosquares Prime Sieve
might also be of interest.
Tuesday, September 6, 2011
install package for latex
There are times you need packages that does not come with your tex distribution, MikTeX for Windows and TexLive for Fedora Linux. And you need somehow install that package. Your got some zip or .tar.gz from CTAN, then:
latex foo.ins (this generates .sty)
[lyan@localhost algorithm2e]$ cp algorithm2e.sty ~/texmf/tex/latex/algorithm2e/
[lyan@localhost algorithm2e]$ cp algorithm2e.pdf ~/texmf/doc/
[lyan@localhost algorithm2e]$ sudo texhash ~/texmf
[sudo] password for lyan:
texhash: Updating /home/lyan/texmf/ls-R...
texhash: Done.
Then you can \usepackage{algorithm2e} in your latex source.
Note your local tex directory should mimic TDS Tex Directory Structure. texmf/tex/latex/package for .sty and texmf/doc/ for .pdf.
And by the way, algorithm2e seems pretty nice for algorithm formatting. If you want to use package algorithms.sty for whatever reason, here is an example
\usepackage{fullpage,amsmath,amsthm,algorithmic,algorithm,algorithm2e}
\DontPrintSemicolon
latex foo.ins (this generates .sty)
[lyan@localhost algorithm2e]$ cp algorithm2e.sty ~/texmf/tex/latex/algorithm2e/
[lyan@localhost algorithm2e]$ cp algorithm2e.pdf ~/texmf/doc/
[lyan@localhost algorithm2e]$ sudo texhash ~/texmf
[sudo] password for lyan:
texhash: Updating /home/lyan/texmf/ls-R...
texhash: Done.
Then you can \usepackage{algorithm2e} in your latex source.
Note your local tex directory should mimic TDS Tex Directory Structure. texmf/tex/latex/package for .sty and texmf/doc/ for .pdf.
And by the way, algorithm2e seems pretty nice for algorithm formatting. If you want to use package algorithms.sty for whatever reason, here is an example
\usepackage{fullpage,amsmath,amsthm,algorithmic,algorithm,algorithm2e}
\DontPrintSemicolon
\begin{algorithm}
\caption{The generalized JV Algorithm for Uniform Demand FTFL}
\label{alg:jv}
\begin{algorithmic}
\WHILE{$U\neq \emptyset$}
\FOR{each active $j$}
\STATE raise $\alpha_j$ uniformly
\FORALL{$i\in\fac$}
\IF {$\alpha_j \geq d_{ij}$}
\IF {$i$ is fully-paid} \STATE raise $z_{ij}$
\ELSE \STATE raise $\beta_{ij}$ ($i$ is not fully-paid)
\ENDIF
\ENDIF
\ENDFOR
\IF {$j$ reached $r$ open facilities} \STATE $j$
is saturated \ENDIF
\COMMENT{After $j$ is saturated, $\alpha_j$
freezes along with $\beta_{ij},z_{ij}$ for all
$i\in\fac$.}
\IF {$j$ reached a dead facility} \STATE $j$ is
blocked
\ENDIF
\COMMENT{After $j$ is blocked, $\alpha_j$ freezes
along with $\beta_{ij},z_{ij}$ for all
$i\in\fac$.}
\ENDFOR
\FOR{each $i$ not dead or open}
\IF {$i$ is reached by some $j$ that is saturated} \STATE $i$ is sleep \ENDIF
\IF {$i$ is fully-paid}
\IF {$i$ is sleep} \STATE $i$ is dead
\ELSE \STATE $i$ is open \ENDIF
\ENDIF
\ENDFOR
\ENDWHILE
\end{algorithmic}
\end{algorithm}
Saturday, September 3, 2011
about bitmask and subset Dynamic Programming
It is all too common to use bitmask 0 to 1<<n -1 to represent all subsets of {1,...,n} and do some calculation on each subset. Now if your DP algorithm requires subsets be computed before their supersets, what do you do?
Ideally you would like to generate all subsets in the order of empty set, all {i}, then all {i,j}, ... However this might not be easy to implement, in particular, the 0,1,2,3,... subsets do not assume that order. Still you would like to do calculation use that order, that is, you compute dp[0], then dp[1], dp[2], dp[3], ... up to dp[(1<<n)-1]
You can use dp[s] = sum { for each j in s, dp[s^1<<j] }
Why, because s excludes j, that is s^1<<j is always a smaller integer than s. So even though the subsets are not generated in the order of size, they still guarantee subsets generated before super sets.
Ideally you would like to generate all subsets in the order of empty set, all {i}, then all {i,j}, ... However this might not be easy to implement, in particular, the 0,1,2,3,... subsets do not assume that order. Still you would like to do calculation use that order, that is, you compute dp[0], then dp[1], dp[2], dp[3], ... up to dp[(1<<n)-1]
You can use dp[s] = sum { for each j in s, dp[s^1<<j] }
Why, because s excludes j, that is s^1<<j is always a smaller integer than s. So even though the subsets are not generated in the order of size, they still guarantee subsets generated before super sets.
Thursday, September 1, 2011
TC SRM 516
Missed the match because overslept.
p250 is easy since plain xor cipher gives you key. And each cipher maps to one plain so you can try them all.
p500 reads daunting but is actually simple. each row is a 50-ary number. Since each col is independent, just accumulate counts and assign 0 to the max cnt, 1 to second max cnt, etc. Watch for integer overflow when do multiplication.
p1000 is a tricky problem, even petr did a resubmission. First of all, the problem asks for an lexico first eulerian tour. We all know eulerian tour and there is a linear time algorithm with simple implementation using recursion. So what is the difficult part? In the tour, an edge cannot have the same label as its prev edge. The problem statement goes through all the trouble to disguise this by saying no two consecutive edges are same labelled except the begin edge and last edge of the tour. So how to do that? A greedy algorithm would use the minimum valid edge as next edge, but this fails. See this example
edge(0,1)='a'
edge(0,4)='f'
edge(1,2)='c'
edge(1,3)='c'
edge(1,4)='b'
edge(2,4)='d'
edge(3,4)='e'
A valid tour is 0-1-3-4-2-1-4-0, with edges a-c-e-b-c-d-f
Now greedy will choose edge(1,4)=b as next edge instead of edge(1,3)=c, then it is doomed since we will have to enter 1 and leave 1 using two edges both labeled 'c'. And it is not a valid tour.
So the algorithm? Pretty much brute force. You try all possible next edge, see if use this edge will allow the rest to have a valid tour, and pick the minimum label edge as your choice. It is obvious that the solution is valid and lexico minimum. Now how do you check the rest edges?
For each node, it needs to have an even number of edges, and the max cnt of them cannot be more than 1/2 of total cnt. It is clear that if this holds for all vertices and the subgraph is connected, then the subgraph has a valid eulerian tour. In fact, you are checking an eulerian path from vertex first to vertex last, each vertex other than first/last should have maxcnt=othercnt. For first and last, each get an extra deg for othercnt because for first=last, it has to be first=last=0, then you can have an extra 2 othercnt since it is valid to have maxcnt=othercnt+2 for vertex[0]. For first!= last, it is maxcnt=othercnt before, and if you use one of maxcnt, then you are good, if you use one othercnt, then you will have maxcnt=othercnt+1 and it is allowed.
Since we only have 40 nodes, and at most 40*40/2=800 edges. For each vertex and each of its neighbor, we remove that edge and do a check. the check is linear time. So the total is 40*40*40*40=800*800=640000, which is a small number and will run in time limit.
OK, code here, also at here
p250 is easy since plain xor cipher gives you key. And each cipher maps to one plain so you can try them all.
p500 reads daunting but is actually simple. each row is a 50-ary number. Since each col is independent, just accumulate counts and assign 0 to the max cnt, 1 to second max cnt, etc. Watch for integer overflow when do multiplication.
p1000 is a tricky problem, even petr did a resubmission. First of all, the problem asks for an lexico first eulerian tour. We all know eulerian tour and there is a linear time algorithm with simple implementation using recursion. So what is the difficult part? In the tour, an edge cannot have the same label as its prev edge. The problem statement goes through all the trouble to disguise this by saying no two consecutive edges are same labelled except the begin edge and last edge of the tour. So how to do that? A greedy algorithm would use the minimum valid edge as next edge, but this fails. See this example
edge(0,1)='a'
edge(0,4)='f'
edge(1,2)='c'
edge(1,3)='c'
edge(1,4)='b'
edge(2,4)='d'
edge(3,4)='e'
A valid tour is 0-1-3-4-2-1-4-0, with edges a-c-e-b-c-d-f
Now greedy will choose edge(1,4)=b as next edge instead of edge(1,3)=c, then it is doomed since we will have to enter 1 and leave 1 using two edges both labeled 'c'. And it is not a valid tour.
So the algorithm? Pretty much brute force. You try all possible next edge, see if use this edge will allow the rest to have a valid tour, and pick the minimum label edge as your choice. It is obvious that the solution is valid and lexico minimum. Now how do you check the rest edges?
For each node, it needs to have an even number of edges, and the max cnt of them cannot be more than 1/2 of total cnt. It is clear that if this holds for all vertices and the subgraph is connected, then the subgraph has a valid eulerian tour. In fact, you are checking an eulerian path from vertex first to vertex last, each vertex other than first/last should have maxcnt=othercnt. For first and last, each get an extra deg for othercnt because for first=last, it has to be first=last=0, then you can have an extra 2 othercnt since it is valid to have maxcnt=othercnt+2 for vertex[0]. For first!= last, it is maxcnt=othercnt before, and if you use one of maxcnt, then you are good, if you use one othercnt, then you will have maxcnt=othercnt+1 and it is allowed.
Since we only have 40 nodes, and at most 40*40/2=800 edges. For each vertex and each of its neighbor, we remove that edge and do a check. the check is linear time. So the total is 40*40*40*40=800*800=640000, which is a small number and will run in time limit.
OK, code here, also at here
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define sz(a) int(a.size())
bool valid(int first, int last, const vector<string> &graph);
vector<int> euler(char prev, int v, vector<string> graph)
{
//cout << "euler " << prev << ' ' << v << endl;
//for(int i=0; i<sz(graph); ++i)
//{
//for(int j=0; j<sz(graph[0]);++j) cout << graph[i][j];
//cout << endl;
//}
int n = sz(graph);
int deg[50]={0};
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) deg[i]+=(graph[i][j]!='.');
vector<int> ans(1,v);
if (deg[v]==0) return ans; // basecase, when v has deg=0
// find a neighbor and remove edge, decr deg
int next=sz(graph[v]);
for(int k=0; k<sz(graph[v]); ++k)
{
char ch = graph[v][k];
if (ch=='.'||ch==prev) continue;
//use edge(v,k) and check the rest
graph[v][k]=graph[k][v]='.';
// need to use min vertex so the first valid k is next
if (valid(k,0,graph)) { next=min(next,k); }
graph[v][k]=graph[k][v]=ch;
}
if (next>=sz(graph[v])) return vector<int>();
char ch = graph[v][next];
graph[v][next]=graph[next][v]='.';
vector<int> sub=euler(ch,next,graph);
if (sub.empty()) return vector<int>();
for(int i=0; i<sz(sub); ++i) ans.push_back(sub[i]);
return ans;
}
void dfs(int v, int visit[], const vector<string> &graph)
{
if (visit[v]) return;
visit[v]=1;
int n = sz(graph);
for(int i=0; i<n; ++i) if (!visit[i] && graph[v][i]!='.')
dfs(i,visit,graph);
}
// all non-isolated vertices must be connected
bool connected(const vector<string> &graph)
{
int n = sz(graph);
int visit[50]={0};
dfs(0,visit,graph);
int deg[50]={0};
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if (graph[i][j]!='.') deg[i]++;
for(int i=0; i<n; ++i) if (deg[i] && !visit[i]) return false;
return true;
}
// every node has to be balanced, #maxcnt <= #total/2
bool valid(int first, int last, const vector<string> &graph)
{
int n = sz(graph);
if (!connected(graph)) return false;
for(int i=0; i<n; ++i)
{
int total=0;
int cnt[100]={0};
for(int j=0; j<n; ++j)
{
char ch = graph[i][j];
if (ch=='.') continue;
int k;
if ('A'<=ch && ch<='Z') k=ch-'A';
else k=ch-'a'+26;
cnt[k]++; total++;
}
sort(cnt,cnt+sizeof(cnt)/sizeof(int), greater<int>());
int extra=0;
// first=last only possible when both are 0, and maxcnt=other+2 is fine
// when first!=last, both can have maxcnt=other+1 because we have
// maxcnt=other before use one edge
if (i==first) { ++total; ++extra; }
if (i==last) { ++total; ++extra; }
if (total%2!=0) return false;
if (cnt[0]>total-cnt[0]+extra) return false;
}
return true;
}
class LexSmallestTour
{
public:
vector<int> determineTour(vector<string> roads, vector<int> queries)
{
vector<int> empty;
if (!valid(0,0,roads)) return empty;
vector<int> tour=euler(' ', 0, roads);
if (tour.empty()) return empty;
vector<int> ans;
for(int i=0; i<sz(queries); ++i)
{ if (i) cout << ' '; cout << tour[queries[i]];
ans.push_back(tour[queries[i]]);
}
cout << endl;
return ans;
}
};
// SRM 516 div1 p250
//
// brute force
//
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PI;
#define INF (1<<29)
#define fort(i,a) for(typeof a.begin() i=a.begin(); i!=a.end(); ++i)
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
#define sz(a) int(a.size())
class NetworkXOneTimePad
{
public:
int crack(vector <string> plain, vector <string> cipher)
{
int ans=0;
string c = cipher[0];
for(int i=0; i<sz(plain); ++i)
{
string key;
for(int j=0; j<sz(c); ++j)
{
char ch;
if (plain[i][j]==c[j]) ch='0';
else ch='1';
key+=ch;
}
bool good=true;
for(int k=1; k<sz(cipher); ++k)
{
bool found=false; // found a plain for cipher[k]
for(int kk=0; kk<sz(plain); ++kk)
{
bool match=true; // plain[kk] match cipher[k]
for(int j=0; j<sz(cipher[k]); ++j)
{
char ch;
if (plain[kk][j]==key[j]) ch='0';
else ch='1';
if (ch!=cipher[k][j]) { match=false; break; }
}
if (match) { found=true; break; }
}
if (!found) { good=false; break; }
}
if (good) ++ans;
}
return ans;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"110", "001"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"101", "010"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(0, Arg2, crack(Arg0, Arg1)); }
void test_case_1() { string Arr0[] = {"00", "01", "10", "11"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"00", "01", "10", "11"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; verify_case(1, Arg2, crack(Arg0, Arg1)); }
void test_case_2() { string Arr0[] = {"01", "10"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"00"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, crack(Arg0, Arg1)); }
void test_case_3() { string Arr0[] = {"000", "111", "010", "101", "110", "001"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"011", "100"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 6; verify_case(3, Arg2, crack(Arg0, Arg1)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
NetworkXOneTimePad __test;
__test.run_test(-1);
}
// END CUT HERE
[lyan@localhost topcoder]$ cat RowsOrdering.cpp
// SRM 516 div1 p500
//
// The problem reads daunting but turned out to be very easy
//
// basically you are treating each row as a number in 50-ary
// since each col is independent, you can work with them without
// worry about other cols
//
// since you are to minimize the sum, you can assign 0 to the
// max cnt char in the col, 1 to 2nd max cnt char, ...
//
// then you sum the weighted cnt in each col
//
// now you work with a vector of sums and you assign larger
// weight to smaller sum
//
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PI;
#define INF (1<<29)
#define fort(i,a) for(typeof a.begin() i=a.begin(); i!=a.end(); ++i)
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
#define sz(a) int(a.size())
class RowsOrdering
{
public:
int order(vector <string> rows)
{
const int MOD = 1000000000+7;
int M = sz(rows[0]);
vector<LL> cols(M);
for(int c=0; c<M; ++c)
{
int row[55]={0};
for(int r=0; r<sz(rows); ++r)
{
int val=0;
char ch = rows[r][c];
if ('a'<=ch && ch<='z') val = ch-'a';
else if ('A'<=ch && ch<='X') val = ch-'A'+26;
row[val]++;
}
sort(row,row+sizeof(row)/sizeof(int),greater<int>());
LL sum=0LL;
for(int i=0; i<51; ++i)
{
sum += i*row[i];
}
cols[c]=sum;
}
sort(cols.begin(), cols.end(), greater<LL>());
LL factor=1LL, ans=0LL;
for(int i=0; i<M; ++i)
{
ans = (ans+cols[i]*factor%MOD) % MOD;
factor = factor*50LL % MOD;
}
ans = (ans+sz(rows))%MOD;
return ans;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"bb", "cb", "ca"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 54; verify_case(0, Arg1, order(Arg0)); }
void test_case_1() { string Arr0[] = {"abcd", "ABCD"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 127553; verify_case(1, Arg1, order(Arg0)); }
void test_case_2() { string Arr0[] = {"Example", "Problem"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 943877448; verify_case(2, Arg1, order(Arg0)); }
void test_case_3() { string Arr0[] = {"a", "b", "c", "d", "e", "f", "g"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 28; verify_case(3, Arg1, order(Arg0)); }
void test_case_4() { string Arr0[] = {"a", "a"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; verify_case(4, Arg1, order(Arg0)); }
void test_case_5() { string Arr0[] = {"dolphinigle", "ivanmetelsk", "lympandaaaa"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 356186235; verify_case(5, Arg1, order(Arg0)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
RowsOrdering __test;
__test.run_test(-1);
}
// END CUT HERE
Subscribe to:
Posts (Atom)
