Facebook Hacker Cup – Auction

2012
01.27

import java.util.*; public class Auction {

static int m, k; static int earliest; static long n; static long lcm; static int[] firstMod, min, max, minMap, maxMap; public static class Tree { private class Entry { // if min or max is 0, then the subtree is empty int value; int min; int max; boolean exists; public Entry(int value) { this.value = value; } public String toString() { return value+"|m"+min+"|M"+max+"|"+(exists?"T":"F"); } } Entry[] tree; int size; boolean[] exist; public Tree(int max) { tree = new Entry[2 * max + 2]; exist = new boolean[max + 1]; size = 0; Entry emptyTree = new Entry(0); // dummy entry, used as empty subtree genTree(1, max, 1); for (int i = 0; i < tree.length; i++) { if (tree[i] == null) tree[i] = emptyTree; } } private void genTree(int L, int R, int at) { if (L > R) return; int M = (L + R) / 2; tree[at] = new Entry(M); genTree(L, M - 1, at * 2); genTree(M + 1, R, at * 2 + 1); } public void clear() { size = 0; clear(1); } public void clear(int at) { if (at >= tree.length || tree[at].min == 0) return; tree[at].min = 0; tree[at].max = 0; tree[at].exists = false; exist[tree[at].value] = false; clear(at * 2); clear(at * 2  + 1); } public boolean isEmpty() { return size == 0; } public int first() { return tree[1].min; } public int last() { return tree[1].max; }  public void add(int n) { int at = 1; exist[n] = true; while (true) { if (n < tree[at].value) at *= 2; else if (n > tree[at].value) at = 2 * at + 1; else { if (!tree[at].exists) size++; tree[at].exists = true; break; } } updateMinMax(at); } public void remove(int n) { int at = 1; exist[n] = false; while (true) { if (n < tree[at].value) at *= 2; else if (n > tree[at].value) at = 2 * at + 1; else { if (tree[at].exists) size--; tree[at].exists = false; break; } } updateMinMax(at); } public boolean contains(int n) { return exist[n]; } private void updateMinMax(int at) { while (at >= 1) { Entry L = tree[0], R = tree[0], M = tree[at]; if (at * 2 < tree.length) L = tree[at * 2]; if (at * 2 + 1 < tree.length) R = tree[at * 2 + 1];   if (L.min != 0) M.min = L.min; else if (M.exists) M.min = M.value; else M.min = R.min;  if (R.max != 0) M.max = R.max; else if (M.exists) M.max = M.value; else M.max = L.max;  at /= 2; } } } public static class Sequence { int[] leading, repeat, first; long l, r, mod; public int get(int i) { if (i < l) return leading[(int) i]; i -= l; return repeat[(int) (i % r)]; } public String toString() { return Arrays.toString(leading)+"("+Arrays.toString(repeat)+")"; } public Sequence(int p1, long a, long b, long m) { mod = m; first = new int[(int) mod + 1];  int P = p1; List list = new ArrayList(); boolean[] seen = new boolean[(int) (m+1)]; for (int i = 1; i <= n; i++) { if (seen[P]) { int start = list.indexOf(P); leading = new int[start]; repeat = new int[list.size() - start]; for (int j = 0; j < start; j++) leading[j] = list.get(j); for (int j = start; j < list.size(); j++) { repeat[j - start] = list.get(j); first[list.get(j)] = j + 1; } break; } else { list.add(P); } seen[P] = true; P = (int) (((a * P + b) % m) + 1); if (i == n) { leading = new int[(int) n]; repeat = new int[0]; for (int j = 0; j < n; j++) { leading[j] = list.get(j); } } } l = leading.length; r = repeat.length; } }  public static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a%b); } public static long ceil(long a, long b) { // assumes a >= 0 return (a+b-1)/b; } public static long floor(long a, long b) { if (a < 0) return -ceil(-a, b); return a/b; } public static long timesSeen(int p, int w) { if (P.first[p] == 0 || W.first[w] == 0) return 1; int mod = (int) ((((W.first[w] - P.first[p]) % W.r) + W.r) % W.r); long firstSeen = P.r * firstMod[mod] + P.first[p]; long k = Math.min(floor(firstSeen - P.first[p], lcm), floor(firstSeen - W.first[w], lcm)); firstSeen -= k * lcm; return (n - firstSeen) / lcm + 1; } public static void generateMinMax() { boolean[] seen = new boolean[(int)W.r]; int[] seenWhen = new int[k+1]; minMap = new int[(int) P.r]; maxMap = new int[(int) P.r]; earliest = 1000000000; for (int i = 0; i < W.r; i++) { long first = 0; if (P.l + 1 - (W.l + i + 1) > 0) first = ceil(P.l + 1 - (W.l + i + 1), W.r); // get the first time we see it after the leading P terms seenWhen[i] = (int)(W.r * first + W.l + i + 1); earliest = Math.min(earliest, seenWhen[i]); }  if (P.r == 0) return; Tree window = new Tree((int)(W.mod)); for (int start = 0; start < W.r; start++) { long endW = start, L = 0, R = 0; int smallest = earliest; if (seen[start]) continue; window.clear(); int atW = start; //while (smallest <= Math.max(P.l + P.r, W.l + W.r)) { // nope. while (smallest - earliest < P.r) { // nope. seen[atW] = true; int startElement = W.repeat[atW]; long last = seenWhen[atW] + (window.size - 1) * P.r; while (last + P.r <= n) { if (L > R) { R = L; endW = atW; } int next = W.repeat[(int) endW]; if (window.contains(next)) break; window.add(next); last += P.r; endW += P.r; endW %= W.r; R++; } int when = seenWhen[atW]; if (!window.isEmpty() && when - earliest < P.r) { minMap[when - earliest] = window.first(); maxMap[when - earliest] = window.last(); } window.remove(startElement); seenWhen[atW] += W.r; atW += P.r; atW %= W.r; L++; if (atW == start) { // we've looped, HOPE THIS WORKS RIGHT smallest += W.r; } } }  firstMod = new int[(int)W.r]; for (int i = 0; i < W.r / gcd(P.r, W.r); i++) { firstMod[(int) (P.r * i % W.r)] = i; } } public static Sequence P, W; public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int ca = 1; ca <= t; ca++) { n = in.nextLong(); int p1 = in.nextInt(), w1 = in.nextInt(); m = in.nextInt(); k = in.nextInt(); int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt();  P = new Sequence(p1, a, b, m); W = new Sequence(w1, c, d, k);  generateMinMax();  lcm = 0; if (W.r > 0 && P.r > 0) lcm = (W.r / gcd(W.r, P.r) * P.r);  min = new int[m+1]; max = new int[m+1]; for (int i = 0; i <= m; i++) min[i] = k+1; // lower bound: 0, upper bound: k+1  for (int i = 0; i < P.l; i++) { min[P.get(i)] = W.get(i); max[P.get(i)] = W.get(i); } for (int i = (int)P.l; i < P.l + P.r; i++) { int j = i; while (j < W.l) { min[P.get(i)] = Math.min(min[P.get(i)], W.get(j)); max[P.get(i)] = Math.max(max[P.get(i)], W.get(j)); j += P.r; } if (j < n) { int id = j + 1 - earliest; if (minMap[id] > 0) min[P.get(i)] = Math.min(min[P.get(i)], minMap[id]); if (maxMap[id] > 0) max[P.get(i)] = Math.max(max[P.get(i)], maxMap[id]); } }  long terrible = 0; int maxMaxs = 0; for (int i = m; i >= 1; i--) { if (max[i] > maxMaxs) {

// System.out.println(“Terrible: ”+i+“,”+max[i]+“ ct=”+timesSeen(i,max[i]));

terrible += timesSeen(i, max[i]); maxMaxs = max[i]; } } long bargains = 0; int minMins = k+1; for (int i = 1; i <= m; i++) { if (min[i] < minMins) { bargains += timesSeen(i, min[i]); minMins = min[i]; } }  System.out.printf("Case #%d: %d %d%n", ca, terrible, bargains); } }

}

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Facebook Hacker Cup – Alphabet Soup

2012
01.27
Problem statement:

Alfredo Spaghetti really likes soup, especially when it contains
alphabet pasta. Every day he constructs a sentence from letters,
places the letters into a bowl of broth and enjoys delicious alphabet
soup.

Today, after constructing the sentence, Alfredo remembered that the
Facebook Hacker Cup starts today! Thus, he decided to construct the
phrase “HACKERCUP”. As he already added the letters to the broth, he
is stuck with the letters he originally selected. Help Alfredo
determine how many times he can place the word “HACKERCUP”
side-by-side using the letters in his soup.

Input
The first line of the input file contains a single integer T: the
number of test cases. T lines follow, each representing a single test
case with a sequence of upper-case letters and spaces: the original
sentence Alfredo constructed.

Output
Output T lines, one for each test case. For each case, output “Case
#t: n”, where t is the test case number (starting from 1) and n is the
number of times the word “HACKERCUP” can be placed side-by-side using
the letters from the sentence.

Constraints
1 < T ≤ 20
Sentences contain only the upper-case letters A-Z and the space character
Each sentence contains at least one letter, and contains at most 1000
characters, including spaces
Example input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP

Example output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

Solution:

Very easy problem, just iterate through the sentence, and find least
occurrence in the alphabets contained in “HACKERCUP” (notice there are
2 Cs).

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Alphabet {
       public static void main(String[] args) throws FileNotFoundException {
               Scanner sc = new Scanner (new File(args[0]));
               int t = sc.nextInt();
               sc.nextLine();
               for (int i=1; i<= t; i++) {
                       String s = sc.nextLine();
                       char[] ch = s.toCharArray();
                       int[] al = new int[7];
                       int c = 0;
                       for (int i1=0; i1<ch.length; i1++) {
                               switch (ch[i1]) {
                               case ‘H’: al[0]++;
                               break;
                               case ‘A’: al[1]++;
                               break;
                               case ‘C’: c++;
                               break;
                               case ‘K’: al[2]++;
                               break;
                               case ‘E’: al[3]++;
                               break;
                               case ‘R’: al[4]++;
                               break;
                               case ‘U’: al[5]++;
                               break;
                               case ‘P’: al[6]++;
                               break;
                               default: break;
                               }
                       }
                       int min = c/2;
                       for (int j=0; j<al.length; j++) {
                               if (al[j]<min)
                                       min = al[j];
                       }
                       System.out.println(“Case #”+i+”: “+min);
               }
       }

}

 

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Facebook Hacker Cup – Alphabet Soup

2012
01.27
Problem statement:

Alfredo Spaghetti really likes soup, especially when it contains
alphabet pasta. Every day he constructs a sentence from letters,
places the letters into a bowl of broth and enjoys delicious alphabet
soup.

Today, after constructing the sentence, Alfredo remembered that the
Facebook Hacker Cup starts today! Thus, he decided to construct the
phrase “HACKERCUP”. As he already added the letters to the broth, he
is stuck with the letters he originally selected. Help Alfredo
determine how many times he can place the word “HACKERCUP”
side-by-side using the letters in his soup.

Input
The first line of the input file contains a single integer T: the
number of test cases. T lines follow, each representing a single test
case with a sequence of upper-case letters and spaces: the original
sentence Alfredo constructed.

Output
Output T lines, one for each test case. For each case, output “Case
#t: n”, where t is the test case number (starting from 1) and n is the
number of times the word “HACKERCUP” can be placed side-by-side using
the letters from the sentence.

Constraints
1 Sentences contain only the upper-case letters A-Z and the space character
Each sentence contains at least one letter, and contains at most 1000
characters, including spaces
Example input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP

Example output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

Solution:

Very easy problem, just iterate through the sentence, and find least
occurrence in the alphabets contained in “HACKERCUP” (notice there are
2 Cs).

[code]
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Alphabet {
       public static void main(String[] args) throws FileNotFoundException {
               Scanner sc = new Scanner (new File(args[0]));
               int t = sc.nextInt();
               sc.nextLine();
               for (int i=1; i                       String s = sc.nextLine();
                       char[] ch = s.toCharArray();
                       int[] al = new int[7];
                       int c = 0;
                       for (int i1=0; i1                                switch (ch[i1]) {
                               case 'H': al[0]++;
                               break;
                               case 'A': al[1]++;
                               break;
                               case 'C': c++;
                               break;
                               case 'K': al[2]++;
                               break;
                               case 'E': al[3]++;
                               break;
                               case 'R': al[4]++;
                               break;
                               case 'U': al[5]++;
                               break;
                               case 'P': al[6]++;
                               break;
                               default: break;
                               }
                       }
                       int min = c/2;
                       for (int j=0; j

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Facebook Hacker Cup – Alphabet Soup

2012
01.27

Problem statement: Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup. Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup. Input The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed. Output Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence. Constraints 1 < T ≤ 20 Sentences contain only the upper-case letters A-Z and the space character Each sentence contains at least one letter, and contains at most 1000 characters, including spaces Example input 5 WELCOME TO FACEBOOK HACKERCUP CUP WITH LABEL HACKERCUP BELONGS TO HACKER QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG MOVE FAST BE BOLD HACK THE HACKERCUP Example output Case #1: 1 Case #2: 2 Case #3: 1 Case #4: 0 Case #5: 1 Solution: Very easy problem, just iterate through the sentence, and find least occurrence in the alphabets contained in “HACKERCUP” (notice there are 2 Cs). [code] import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Alphabet { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner (new File(args[0])); int t = sc.nextInt(); sc.nextLine(); for (int i=1; i<= t; i++) { String s = sc.nextLine(); char[] ch = s.toCharArray(); int[] al = new int[7]; int c = 0; for (int i1=0; i1

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Facebook Hacker Cup – Alphabet Soup

2012
01.27
Problem statement:

Alfredo Spaghetti really likes soup, especially when it contains
alphabet pasta. Every day he constructs a sentence from letters,
places the letters into a bowl of broth and enjoys delicious alphabet
soup.

Today, after constructing the sentence, Alfredo remembered that the
Facebook Hacker Cup starts today! Thus, he decided to construct the
phrase “HACKERCUP”. As he already added the letters to the broth, he
is stuck with the letters he originally selected. Help Alfredo
determine how many times he can place the word “HACKERCUP”
side-by-side using the letters in his soup.

Input
The first line of the input file contains a single integer T: the
number of test cases. T lines follow, each representing a single test
case with a sequence of upper-case letters and spaces: the original
sentence Alfredo constructed.

Output
Output T lines, one for each test case. For each case, output “Case
#t: n”, where t is the test case number (starting from 1) and n is the
number of times the word “HACKERCUP” can be placed side-by-side using
the letters from the sentence.

Constraints
1 Sentences contain only the upper-case letters A-Z and the space character
Each sentence contains at least one letter, and contains at most 1000
characters, including spaces
Example input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP

Example output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

Solution:

Very easy problem, just iterate through the sentence, and find least
occurrence in the alphabets contained in “HACKERCUP” (notice there are
2 Cs).

[code]

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Alphabet {
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner (new File(args[0]));
int t = sc.nextInt();
sc.nextLine();
for (int i=1; i String s = sc.nextLine();
char[] ch = s.toCharArray();
int[] al = new int[7];
int c = 0;
for (int i1=0; i1

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Facebook Hacker Cup – Billboard

2012
01.27
Problem statement:

We are starting preparations for Hacker Cup 2013 really early. Our
first step is to prepare billboards to advertise the contest. We have
text for hundreds of billboards, but we need your help to design them.

The billboards are of different sizes, but are all rectangular. The
billboard widths and heights are all integers. We will supply you with
the size in inches and the text we want printed. We want you to tell
us how large we can print the text, such that it fits on the billboard
without splitting any words across lines. Since this is to attract
hackers like yourself, we will use a monospace font, meaning that all
characters are of the same width (e.g.. ‘l’ and ‘m’ take up the same
horizontal space, as do space characters). The characters in our font
are of equal width and height, and there will be no additional spacing
between adjacent characters or adjacent rows. If you print a word on
one line and print the next word on the next line, you do not need to
print a space between them.

Let’s say we want to print the text “Facebook Hacker Cup 2013″ on a
350×100″ billboard. If we use a font size of 33″ per character, then
we can print “Facebook” on the first line, “Hacker Cup” on the second
and “2013″ on the third. The widest of the three lines is “Hacker
Cup”, which is 330″ wide. There are three lines, so the total height
is 99″. We cannot go any larger.

Input
The first line of the input file contains a single integer T: the
number of test cases. T lines follow, each representing a single test
case in the form “W H S”. W and H are the width and height in inches
of the available space. S is the text to be written.

Output
Output T lines, one for each test case. For each case, output “Case
#t: s”, where t is the test case number (starting from 1) and s is the
maximum font size, in inches per character, we can use. The size must
be an integral number of inches. If the text does not fit when printed
at a size of 1″, then output 0.

Constraints
1 ? T ? 20
1 ? W, H ? 1000
The text will contain only lower-case letters a-z, upper-case letters
A-Z, digits 0-9 and the space character
The text will not start or end with the space character, and will
never contain two adjacent space characters
The text in each case contains at most 1000 characters

Example input
5
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup

Example output
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7

Solution:

Since the width and height are fairly small, simulation is feasible.
Solve the problem by iterating font size from 1 until the billboard
cannot contain all the words. Fill the billboard line by line.
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Billboards {        public static void main(String[] args) throws FileNotFoundException {                Scanner sc = new Scanner (new File(args[0]));                int t = sc.nextInt();                for (int i=1; i<= t; i++) {                        int w = sc.nextInt();                        int h = sc.nextInt();                        sc.skip(" ");                        String s = sc.nextLine();                        String[] sa = s.split(" ");                        int size = 0;                        for (int j=1; j<10000; j++) {                                int saPtr = 0;                                int currH = h;                                while (true) {                                        currH -= j;                                        if (currH < 0)                                                break;                                        int currW = w;                                        while (currW >= (sa[saPtr].length()*j) ) {                                                currW -= sa[saPtr].length()*j;                                                currW -= j;                                                saPtr++;                                                if (saPtr == sa.length) {                                                        size = j;                                                        break;                                                }                                        }                                        if (size == j)                                                break;                                }                                if (size < j)                                        break;                        }                        System.out.println("Case #"+i+": "+size);                }        } }

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

My 2011 in numbers

2011
12.31
111207-lg-23a2011rev

169 – new friends on Facebook

116 – people in my Google+ circles

54 – Facebook events joined

 

77 – days spent in London over the summer

29 – days spent at home

4 – kg put on at home

 

0.16 – thickness of my new Macbook Air in inches (4mm)

10.7 – version of Mac OS running on the Macbook Air

2.3.4 – version of updated Android running on my Samsung Galaxy S and Nook Color

26 – apps downloaded from Mac App store

 

8.83 – percentage increase in my stock portfolio value

5.5 – estimated rate of inflation

0.5 – Bank of England base rate

240 – share price of Barclays Plc when I joined

155 – share price when I left

 

60 – miles cycled from London to Cambridge

28 – miles cycled from Cambridge to Ely and back

 

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

From “The Great Dictator”

2011
12.22
I'm sorry, but I don't want to be an emperor. That's not my business. I don't want to rule or conquer anyone. I should like to help everyone if possible; Jew, Gentile, black man, white. We all want to help one another. Human beings are like that. We want to live by each other's happiness, not by each other's misery. We don't want to hate and despise one another. In this world there is room for everyone, and the good earth is rich and can provide for everyone. The way of life can be free and beautiful, but we have lost the way. Greed has poisoned men's souls, has barricaded the world with hate, has goose-stepped us into misery and bloodshed. We have developed speed, but we have shut ourselves in. Machinery that gives abundance has left us in want. Our knowledge has made us cynical; our cleverness, hard and unkind. We think too much and feel too little. More than machinery, we need humanity. More than cleverness, we need kindness and gentleness. Without these qualities, life will be violent and all will be lost. The airplane and the radio have brought us closer together. The very nature of these inventions cries out for the goodness in men; cries out for universal brotherhood; for the unity of us all. Even now my voice is reaching millions throughout the world, millions of despairing men, women, and little children, victims of a system that makes men torture and imprison innocent people. To those who can hear me, I say, do not despair. The misery that is now upon us is but the passing of greed, the bitterness of men who fear the way of human progress. The hate of men will pass, and dictators die, and the power they took from the people will return to the people. And so long as men die, liberty will never perish. Soldiers! Don't give yourselves to brutes, men who despise you, enslave you; who regiment your lives, tell you what to do, what to think and what to feel! Who drill you, diet you, treat you like cattle, use you as cannon fodder. Don't give yourselves to these unnatural men – machine men with machine minds and machine hearts! You are not machines, you are not cattle, you are men! You have the love of humanity in your hearts! You don't hate! Only the unloved hate; the unloved and the unnatural. Soldiers! Don't fight for slavery! Fight for liberty! In the seventeenth chapter of St. Luke, it is written that the kingdom of God is within man, not one man nor a group of men, but in all men! In you! You, the people, have the power, the power to create machines, the power to create happiness! You, the people, have the power to make this life free and beautiful, to make this life a wonderful adventure. Then in the name of democracy, let us use that power. Let us all unite. Let us fight for a new world, a decent world that will give men a chance to work, that will give youth a future and old age a security. By the promise of these things, brutes have risen to power. But they lie! They do not fulfill that promise. They never will! Dictators free themselves but they enslave the people. Now let us fight to fulfill that promise. Let us fight to free the world! To do away with national barriers! To do away with greed, with hate and intolerance! Let us fight for a world of reason, a world where science and progress will lead to all men's happiness. Soldiers, in the name of democracy, let us all unite! Hannah, can you hear me? Wherever you are, look up Hannah! The clouds are lifting! The sun is breaking through! We are coming out of the darkness into the light! We are coming into a new world; a kindlier world, where men will rise above their hate, their greed, and brutality. Look up, Hannah! The soul of man has been given wings and at last he is beginning to fly. He is flying into the rainbow! Into the light of hope, into the future! The glorious future, that belongs to you, to me and to all of us.

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Dear Steve

2011
10.06
Thank you for all the "dings" you have brought to the universe. Thank you for all well designed products that work out of the box. Thank you for delivering revolutionary products time and again, from the original Mac to Pixar movies, iPod, OS X, iPhone, Macbook Air, iPad and more in the pipeline. Thank you for making business cool again – user experience instead of bottom line, no debt instead of capital efficiency. Most of all, thank you for telling the world that it's all right to think different.

You will be missed.

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]

Password storage 101

2011
09.03
4. I have decided to write a basic tutorial because I have been shocked multiple times in the past few weeks knowing how many large organizations keep their users' passwords. It's easy to assume that website operators would have basic knowledge in computer security, but I have found such assumption false.

This post is mainly for website operators. For average users, I offer two pieces of advice:

1. Ignore advice to use a non-repeated strong password that's at least 8 characters long, contains special characters etc., you won't be able to remember 50 different passwords in your head. Instead, use a moderately strong password, such as your initials+date of birth, or full name of your favorite actress that can be remembered. On when to repeat the same password, see advice 2.

2. Beware that many companies and governments don't store your password safely. A database administrator in the company or a hacker who gains access to the database may be able to see your password in the form of plain text (i.e., what you have entered into the form). A good (enough) test for that is to register your account with a random temporary password, and click the "Forget my password" link. If they send you an email with your password, be very careful! The best practice is probably to write down the password somewhere convenient. Instead, if they email you with a link to reset password or a temporary password to log on, then it probably is safe, and you can use the same password with caution.

Now, for operators of services that require logging in,

1. Never store your users' passwords in plain text!

The reason is simple, unscrupulous database administrators and hackers who gain access to the database will be able to pretend to be your users. Worse yet, your users trusted you enough to use the same set of login details for all her services, all her accounts would be vulnerable to impersonation. Remember that the firewall doesn't even need to be breached as people from within the company will be able to view the data as part of their daily job. Imagine a disgruntled employee post all details of your clients on Wikileaks.

Also, use lots of common sense, and do not blindly rely on security consultants (especially not one who ask you to do stupid things). It will be you who suffer reputation loss when bad things happen.

2. Never encrypt users' passwords

Same reason as reason 1, your employees and hackers know how to decrypt. Security by obscurity has proven again and again to not work.

3. Never apply hashing algorithm directly on the password

Good effort, but not good enough. Since employees and hackers know how the password is processed, they can use a Rainbow table to compare matches using brute force attack. It's likely that a few days or a few months are needed to produce the rainbow table, but all 30 million passwords will be recovered together. If a common hashing algorithm is used, there may well be a rainbow table freely available on a magical place called the Internet.

4. Use a long, randomized salt

If the same encryption salt is used across all accounts, we encounter the same problem described in advice 3 – the hacker can generate his own rainbow table for your site. Whenever a new account is created or password reset, generate a new long, random salt, and store the salt in the database as well (it's not meant to be secret), and now we are onto something.  When storing the password to the database, apply the hashing function to the plain text password appended to the salt, i.e., hash(passwd.Append(salt)) or equally valid, append the hash of the password to the salt, then hash again, i.e., hash ( hash(passwd).Append(salt)). Now, a rainbow table cannot be generated. The problem is that a password can still be recovered in a few days or months if a simple fast hashing function is used, but it takes 30 million times a few days or months to recover all those passwords for your 30 million customers. Not bad, but long way to go.

5. Use a slow hashing algorithm

By using a collision resistant hashing algorithm (read: not MD5, possibly not SHA-1 either. I would personally use SHA-256 or better), the main worry is brute force attack. The aim is to use the slowest possible (and still sensible) way to generate the hash. There are algorithms designed specifically for this purpose, bcrypt is a good example. A good way is to apply hashing algorithm multiple times. For instance, hashedPw = hash(passwd.Append(salt)); for (int i=0; i<1000000; i++) hashedPw = hash(hashedPw);
Be careful of cycles. Remember that if the hashing algorithm takes 1ms, a hacker can try 1000 passwords a second. If it takes 200ms, he can only try 5. And a difference of 199ms makes no difference to the user. Do not try to use sleep() to slow down in an artificial way, the hacker doesn't need to put that in his code. Read on if you worry about the extra server load.

6. Use a challenge-response protocol

Don't validate the hash at the server! First, you'll need super-computers to keep up with the large number of users, and second, even if you are rich to buy the super-computers, there may be a eavesdropper ready to steal your user's password during transmission. Use challenge-response authentication instead. The server generates a random string, and encrypts it with the hash. Since the string is one time, the encryption technique can be one that's fast and simple (e.g., DES). If the random string is "apple", the server send encrypt(hash, "apple") to the client. The client's computer then does the computation of hash from the password, decrypts the message, and sends back "apple" to the server.

7. Other miscellaneous points

Invest in a good firewall to keep the users' information safe. Information other than password can still be valuable to a crime organization.
Allow unlimited characters since after all, storage doesn't matter because you are only saving the hash which has fixed length.
Allow every possible character on the planet, support unicode because there is no reason not to.
Limit the number of failed log-in and exponentially increase the time out between each failed log-in to prevent brute force attack.
Read the whole post again, double check to make sure you have done everything mentioned, and only then, consider forcing your users to use secure password.

8. Centralize risk

If you are not sure if you understand all those mentioned and have implemented them correctly, don't create your own log-in page. There are people who know and understand how to manage their users' information, and are willing to help. Almost all your users would have an account with an OpenID provider. It's easy to add OpenID to your site! 
If you can't secure your users' information, definitely use OpenID. Even if you can, still consider using OpenID because it's so much easier.

Posted via email from ramblings of a comsci student

[Slashdot] [Digg] [Reddit] [del.icio.us] [Facebook] [Technorati] [Google] [StumbleUpon]