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

Posted via email from ramblings of a comsci student

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

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

Posted via email from ramblings of a comsci student

Posted via email from ramblings of a comsci student

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.

Posted via email from ramblings of a comsci student

http://jashkenas.github.com/coffee-script/

Posted via email from ramblings of a comsci student

Fact: servers are expensive. It costs a lot of money to build a
data-center, provide power, cooling, and backup for servers, have the
personnel to maintain them etc. When you need hundreds of thousands of
them, having software that run 20% faster can have significant cost
benefits.

Also, data centers and power supply generally cannot be expanded.
Thus, companies are stuck with the number of machines that they can
use, so they have to be careful when allocating resources.

There is a saying that software development is to make it run, make it
right, make it fast. However, it is extremely difficult to optimize
after building the software due to time pressure, and users’ new
feature requests. We are therefore forced by reality to optimize
early, optimize often.

The first step after getting a problem statement is to choose a
programming language. It is necessary to choose a language that has a
good compiler such that many advanced optimization techniques are done
by it. Next, use libraries provided by CPU manufacturers, e.g., Intel
and AMD. Those libraries are built with targeted CPUs in mind, and
they provide significant speed-up for complex calculations. Then, use
data-structures that allow the fastest algorithms to be implemented.
Use a hash table instead of tree, use a binary file instead of XML.
Write multi-threaded code to take advantage of multiple CPU cores when
appropriate. Write assembly code when it’s absolutely necessary.

Even then, a general purpose CPU may just be too slow. For floating
point calculation intensive applications, give GPGPUs a try, be warned
that the high latency from CPU to GPU is a major limitation. Or better
yet, build your own specialized hardware! The large range of FPGAs
offered by Xilinx and Altera could prove life saving for many where
complicated calculations have to be performed many times.

Posted via email from ramblings of a comsci student

It’s very different working for a big company compared to working
alone or in a small team. The workflow tends to be team oriented, work
is supposed to be well documented so that the next person can take
over. After all, on average a third of the team members leave every
single year.

My biggest takeaway has to be getting real experience doing test
driven development (TDD), in which for each function, I have to write
tests before writing real code. The tests are supposed to fail, while
writing real code is supposed to make those tests pass. Unit testing
is of real help when refactoring is needed to make maintenance
possible.

After the unit tests pass on the local machine, source code is
supposed to be checked into a repository using Perforce, a version
control system similar to Subversion. The Cruise Control build server
automatically detects the change in repository, and triggers a build
project. The project is built and have unit test done on the build
server again, hopefully everything is done successfully.

Every task is assigned using a system called JIRA, which is designed
to complement test driven development. Tasks are supposed to be
simple, doing one thing at a time. Each JIRA is designed to be done in
less than a week. Developers log the amount of work done, and assign
someone else in the team to accept their implementations. Things then
have to be recorded down into a wiki like system called Confluence so
that the rest of the team know what’s going on.

Working in a team of 20 instead of anywhere between 1-5 that we are
used to in school is that task assignment becomes even more important.
It’s possible for a school project to have 5 persons doing the same
thing, but you just cannot have 20 people looking at the same piece of
code. It’s very nice to have very helpful team members who help to get
me going when I get stuck.

Posted via email from ramblings of a comsci student