SRM 537 div2 clear

p925, find prerequisite chain and compute each element individually.
ans = sum of each a[i]
ans for a[i] = 1.0/length of prerequisite chain, if loop, then 0.0

latex save/squeeze spacing

http://www.eng.cam.ac.uk/help/tpl/textprocessing/squeeze.html

algorithm environment
http://en.wikibooks.org/wiki/LaTeX/Algorithms_and_Pseudocode#The_algorithm_environment

display math
http://www.math.uiuc.edu/~hildebr/tex/displays.html

notes on linked list

Things that are simple and easy for arrays might get messy in linked list and debugging is harder.

Some tips:

1. know the primitives

delete after prev: prev->next = prev->next->next
if you need prev->next, save the pointer.
it is usually simpler to have a dummy node so you always have a valid prev pointer.

insert p after prev: p->next = prev->next; prev->next = p;

2. maintain a tail pointer if necessary
for(p=head; p->next != NULL; p=p->next) ;
tail = p; // since p->next is NULL after loop terminates, p is tail now
when recursion, consider returning both head and tail pointer, otherwise you might have to walk through the list one more time to reach tail pointer.

3. have a conceptual picture
when doing things like reverse list, sort list, split into odd even, it is usually easier to have separate heads of lists, and you remove nodes from the input list, and grow lists in the output list.

an example is sorting, say selection sort.
you keep removing max node from input list, and insert into head of output list.

4. check NULL whenever you want to dereference using ->

5. do initialization properly, if you need to get min node or max node, initialize the minval and ptr2minval with the first node.

6. draw a picture to help with the links.

7. walk the list with two pointers make the code simpler, an example is mergesort when you need to split the list into two halves.
for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
p2 = p1->next; p1->next = NULL; p1=head;
it is easy to show that when length is even, then we cut after pos=(n/2)-1 with length n/2 in each half,
when length is odd, the first half ends at pos=(n-1)/2 with length=(n+1)/2
since p1 always walks floor((n-1)/2) steps.
and for mergesort, the merge step ends with appending p1 or p2 to output list and it is simply tail->next = p1 or p2

SRM 537

This SRM has cash award so it attracted a lot coders. I have to wake up at 6:00am and register myself.

p275 is easy. Given A, B positive integer, and X positive integer, count number of positive Y != X such that (X,Y) can generate all linear combination of (A,B), and we only accept A*a + B*b for a,b>=0. If there are infinitely many Y, return -1.

First it is easy to see when -1 occur. Only when X divides both A and B, then we do not need Y at all. Easy check, A % X == 0 && B % X ==0. I ended up coding a gcd, which is a bit overkill.

Then we need to enumerate all possible Y's since A, B and X are all small, at most 200. Notice that for Y to be valid, (X,Y) has to be able to generate A and B, and if that is true, then (X,Y) can generate all integers representable by (A,B). For this purpose Y cannot be bigger than max(A,B) so we only try Y=1 to max(A,B). For each Y, we check whether both A and B are representable.

ans=0;
for Y=1 to max(A,B)
aok = bok = false;
for(a=0; a*X <= A; ++a)
if ((A-a*X) % Y == 0) // A is good
aok = true;
for(b=0; b*X <= B; ++b)
if ((B-b*X) % Y == 0) // B is good
bok=true;
if (aok && bok)
ans++;
return ans;

p500 is a DP problem, and everybody knows that. The problem is:
given ducks[N] which are ducks in room 0 to N-1, with N at most 50.
there are two spells, spellOne[i] makes ducks[i] turn into ducks[i] xor spellOne[i]
spellTwo[i] will move ducks[i] into ducks[spellTwo[i]] and it is a permutation.
In each day spellOne and spellTwo occur with prob=0.5. After K days, with K at most 50, what is the expected number of ducks in room[0].

We all know linearity of expectation, but we cannot really apply xor to doubles. Now what?

The trick is to consider each bit of an integer separately, as ducks[i] is at most 10^9, so 30 bits suffices. We know the operation of xor if we have only one bit.

Now we have a DP[k][i][b] means probability of ducks in room[i] being 1 after k days, when only bit b is considered. And the transition is

DP[k][i][b] +=
// spellOne
if spellOne[i] is one at bit[b]
0.5 * (1.0 - DP[k-1][i][b])
else
0.5 * DP[k-1][i][b]
// spellTwo
DP[k][spellTwo[i]][b] += 0.5 * DP[k-1][i][b]

In the end we combine all bits
for b=0 to 30-1
ans += (1<<b) * DP[K][0][b]
return ans;

p1000, asks for longest circular dominos and I did not quite understand the problem, the solution is mincost flow, though.

Got a rating boost by solving p250, boosted from 1332 to 1409.

bst to doubly linked list

// =========================================================
// 
//       Filename:  bst2list.cpp
// 
//    Description:  convert a bst to a linked list
// 
//        Version:  1.0
//        Created:  03/15/2012 10:21:02 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/15/2012, LI YAN
// 
// =========================================================

#include <cstdio>
using namespace std;

struct node {
    int val;
    node *left, *right; // for bst, it is lchild and rchild, for doubly linked list, it is prev and succ
};

node* bst2list(node *root)
{
    if (root==NULL) return NULL;

    node *subleft = bst2list(root->left);
    node *subright = bst2list(root->right);

    root->left = root->right = root;
    node *head, *tail, *ltail, *rtail;
    head=root;
    if (subleft) {
        ltail = subleft->left; tail=head->left;
        ltail->right = head; head->left = ltail;
        subleft->left = tail; tail->right = subleft;
        head = subleft;
    }
    if (subright) {
        tail=head->left; rtail = subright->left;
        tail->right = subright; subright->left = tail;
        head->left = rtail; rtail->right = head;
    }
    return head;
}

void print(node *root)
{
    if (root==NULL) return;
    print(root->left);
    printf(" %d", root->val);
    print(root->right);
}

void printlist(node *head)
{
    if (head==NULL) return;
    node *p=head;
    do {
        printf("%d ", p->val);
        p=p->right;
    } while (p!=head);
}

int main()
{
    node a[100];
    for(int i=0; i<10; ++i) {
        if (2*i+1<10) a[i].left=&a[2*i+1]; 
        else a[i].left = NULL;

        if (2*i+2<10) a[i].right=&a[2*i+2];
        else a[i].right = NULL;
    }
    // expected: true
    int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 280};
    // expected: false
    //int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 350}; 
    for(int i=0; i<10; ++i) {
        a[i].val = v[i];
    }

    node *root=&a[0];
    puts("input");
    print(root); putchar('\n');
    puts("convert to list");
    node *head=bst2list(root);
    printlist(head); putchar('\n');
}

check binary tree being binary search tree

// =========================================================
// 
//       Filename:  bstcheck.cpp
// 
//    Description:  check whether a binary tree is a binary search tree (BST)
// 
//        Version:  1.0
//        Created:  03/15/2012 10:14:03 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/15/2012, LI YAN
// 
// =========================================================

#include <cstdio>
using namespace std;

struct node {
    int val;
    node *left, *right;
};

// check left, check right
// also need min and max of this subtree
//
bool checkbst(node *root, int &vmin, int &vmax)
{
    if (root==NULL) return true;
    int a1, b1, a2, b2;
    vmin=vmax=root->val;
    if (root->left != NULL) {
        bool bleft = checkbst(root->left, a1, b1);
        if (!bleft) return false;
        if (b1>root->val) return false;
        vmin = a1;
    }
    if (root->right != NULL) {
        bool bright = checkbst(root->right, a2, b2);
        if (!bright) return false;
        if (a2<root->val) return false;
        vmax = b2;
    }
    return true;
}

void print(node *root)
{
    if (root==NULL) return;
    print(root->left);
    printf(" %d", root->val);
    print(root->right);
}

int main()
{
    node a[100];
    for(int i=0; i<10; ++i) {
        if (2*i+1<10) a[i].left=&a[2*i+1]; 
        else a[i].left = NULL;

        if (2*i+2<10) a[i].right=&a[2*i+2];
        else a[i].right = NULL;
    }
    // expected: true
    int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 280};
    // expected: false
    //int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 350}; 
    for(int i=0; i<10; ++i) {
        a[i].val = v[i];
    }

    node *root=&a[0];
    int x, y;
    print(root); putchar('\n');
    bool c = checkbst(root, x, y);
    if (c) puts("true");
    else puts("false");
}

list flatten

// listflatten.cpp
//
#include <cctype>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

const char lparen = '(';
const char rparen = ')';

struct node {
    bool atomp;
    int  val;
    struct node *sub;
    struct node *next;
};

struct node *
parse(char *str)
{
    if (!*str) return NULL;
    char *p = str;
    while(isspace(*p))
    {
        p++;
    }
    assert(*p == lparen);
    char *q;
    int lcnt = 1;
    for(q=p+1; ; q++)
    {
        if (*q == rparen)
            lcnt--;
        else if (*q == lparen)
            lcnt++;

        if (lcnt == 0)
            break;
    }
    assert(*q == rparen);
    *q = '\0';

    struct node *newnode = (struct node*)malloc(sizeof(struct node));
    for(p++; isspace(*p); p++)
        ;
    int val = 0;
    bool atomp = false;
    if (isdigit(*p))
    {
        atomp = true;
        while(isdigit(*p))
        {
            val = val * 10 + *p-'0';
            p++;
        }
    }
    newnode->atomp = atomp;
    newnode->val   = val;
    newnode->sub   = parse(p);
    newnode->next  = parse(q+1);

    return newnode;
}

typedef pair<struct node*, struct node*> pnn;

pnn flatten(struct node *head)
{
    pnn ret; ret.first=ret.second=NULL;
    if (!head) return ret;

    pnn subpair  = flatten(head->sub);
    pnn nextpair = flatten(head->next);
    head->sub=head->next=NULL;

    struct node dummy;
    struct node *subhead = subpair.first;
    struct node *subtail = subpair.second;
    struct node *nexthead = nextpair.first;
    struct node *nexttail = nextpair.second;
    struct node *tail = &dummy;

    // set up new head
    if (head->atomp) { tail->next=head; tail = tail->next; }
    if (subhead) { tail->next = subhead; tail = subtail; }
    if (nexthead) { tail->next = nexthead; tail = nexttail; }

    if (tail==&dummy) { ret.first=ret.second=NULL; }
    else { ret.first=dummy.next; ret.second=tail; }
    return ret;
}

void print(struct node *head)
{
    if (!head) return;
    cout << "( ";
    if (head->atomp)
        cout << head->val << " ";
    print(head->sub);
    cout << ") ";
    print(head->next);
}


int main()
{
    char list[] = "(1 (21 (339) ()))(410)(()(123))";
    //char list[] = "(1(3 ()))(2)";
    //char list[] = "(())";

    struct node *head = parse(list);
    print(head);
    cout << endl;
    cout << "flatten list\n";
    head = flatten(head).first;
    print(head);
    cout << endl;
}

swap odd even position in linked list

#include <cassert>
#include <cstdio>
using namespace std;

struct node
{
    int val;
    node* next;
};

node* swap(node *head)
{
    node dummy;
    node *prev, *curr, *u, *tmp;
    if (head==NULL) return head;

    prev=&dummy;
    for(curr=head; curr!=NULL && curr->next!=NULL; ) {
        u = curr->next;
        tmp = u->next;
        prev->next = u;
        u->next = curr;
        prev = curr;
        curr = tmp;
    }
    prev->next = curr;
    return dummy.next;
}

void print(const node *head)
{
    for(const node *p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}
int main()
{
    const int N=101;
    node v[N];
    
    for(int i=0; i<N; ++i) {
        v[i].val=10*i;
        if (i<N-1) v[i].next=&v[i+1];
        else v[i].next=0;
    }

    node *head=&v[0];
    puts("input");
    print(head);

    head = swap(head);
    puts("swap even odd");
    print(head);

}

sorting linked list

// =========================================================
// 
//       Filename:  listsort.cpp
// 
//    Description:  
// 
//        Version:  1.0
//        Created:  03/09/2012 04:06:26 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/09/2012, LI YAN
// 
// =========================================================
//
// notes:
// 1. insert into head does not need dummy node
// 2. insert into tail needs a dummy node to make code simple, there is no tail
// node in an empty list anyway
// 3. delete from head does not need dummy node
// 4. maintain a tail pointer if you need to insert at tail
// 5. it often helps use two pointers walking the same list
// 6. be careful in off-by-one
// 7. know the primitives, insert/delete at ptr->next and at head or tail
// 8. check NULL before dereference use -> or *p

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <utility>
using namespace std;

struct node {
    int val;
    node *next;
};

node* insertsort(node *head)
{
    if (head==NULL || head->next==NULL) return head;

    node ahead, bhead; // dummy ahead is not necessary since we only delete from head
    node *p1, *p2, *u;
    ahead.next=head; bhead.next=NULL;

    for(p1=&ahead; p1->next!=NULL; ) {
        u = p1->next; p1->next = p1->next->next;
        for(p2=&bhead; p2->next!=NULL; p2=p2->next) {
            if (u->val > p2->next->val) break;
        }
        u->next = p2->next;
        p2->next = u;
    }
    return bhead.next;
}

node* selectsort(node *head)
{
    if (head==NULL || head->next==NULL) return head;

    node dummy; dummy.next=head; // use dummy head to simplify delete from head
    node *curr, *ptr, *u, *newhead=NULL;
    int vmax;
    while(dummy.next->next != NULL) { // keep going as long as list has >=2 items
        curr=ptr=&dummy; u=ptr->next; vmax = u->val;
        for(ptr=ptr->next; ptr->next!=NULL; ptr=ptr->next) {
            u=ptr->next;
            if (u->val > vmax) { curr = ptr; vmax = u->val; }
        } 
        ptr=curr->next;
        curr->next = curr->next->next;
        ptr->next=newhead;
        newhead=ptr;
    }
    dummy.next->next = newhead;
    return dummy.next;
}

// code from this point on inspired or learned from Robert Sedgewick
node* mergesort(node *head)
{
    node dummy;
    node *left, *right, *ptr, *p1, *p2;

    if (head==NULL || head->next == NULL) return head;
    for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
    left=head; right=p1->next; p1->next=NULL;

    //printf("p1 %d p2 %d\n", left.next->val, right.next->val);

    p1=mergesort(left);
    p2=mergesort(right);

    dummy.next=NULL;
    for(ptr=&dummy; p1!=NULL && p2!=NULL; ) {
        if (p1->val <= p2->val) { ptr->next=p1; ptr=p1; p1=p1->next; }
        else { ptr->next=p2; ptr=p2; p2=p2->next; }
    }
    ptr->next = (p1==NULL) ? p2 : p1; // this appends remain of p1 or p2 in one stmt
    return dummy.next;
}

// quick sort with Lumoto partition
// returns (head, tail) of sorted list
pair<node*, node*>
quicksort(node *head)
{
    node dummy;
    node *low, *high;
    node *pivot, *ptr, *u, *newhead, *newtail;
    int n, k, i;

    if (head==NULL || head->next==NULL) return make_pair(head, head);

    for(n=0, ptr=head; ptr!=NULL; ptr=ptr->next, n++) ;

    k=rand()%n;
    dummy.next=head;
    for(i=0, ptr=&dummy; i<k; ++i, ptr=ptr->next) ;
    pivot=ptr->next; assert(pivot);
    ptr->next=ptr->next->next;

    low=high=NULL;
    for(ptr=&dummy; ptr->next != NULL; ) {
        u=ptr->next; ptr->next = u->next;
        if (u->val <= pivot->val) { u->next = low; low=u; }
        else { u->next = high; high=u; }
    }
    //printf("low %d high %d\n", low.next->val, high.next->val);
    pair<node*, node*> pp1, pp2;
    pp1 = quicksort(low);
    pp2 = quicksort(high);

    if (pp1.first != NULL) newhead = pp1.first;
    else newhead = pivot;

    if (pp2.second != NULL) newtail = pp2.second;
    else newtail = pivot;

    if (pp1.second != NULL) pp1.second->next = pivot;
    pivot->next = pp2.first;

    return make_pair(newhead, newtail);
}

void print(const node *head)
{
    const node *p;
    for(p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}

int main()
{
    srand((unsigned)time(NULL));
    int a[] = {10, 3, 4, 5, 1, 9, 8};

    int n=sizeof(a)/sizeof(int);
    node v0[10], v1[10], v2[10], v3[10];
    node *head;
    for(int i=0; i<n; ++i) {
        v0[i].val = v1[i].val = v2[i].val = v3[i].val = a[i];
        if (i<n-1) { v0[i].next = &v0[i+1]; v1[i].next = &v1[i+1]; v2[i].next = &v2[i+1]; v3[i].next = &v3[i+1]; }
        else { v0[i].next = v1[i].next = v2[i].next = v3[i].next = 0; }
    }

    puts("v0[]"); print(v0);
    puts("insertion sort:");
    head=selectsort(v0);
    print(head);
    putchar('\n');

    puts("v1[]"); print(v1);
    puts("selection sort:");
    head=selectsort(v1);
    print(head);
    putchar('\n');

    puts("v2[]"); print(v2);
    puts("merge sort:");
    head=mergesort(v2);
    print(head);
    putchar('\n');

    puts("v3[]"); print(v3);
    puts("quick sort:");
    head=(quicksort(v3)).first;
    print(head);
    putchar('\n');
}

my facebook interview experience

So far I have failed 3 facebook phone interviews in the past 3 years, fairly consistent, huh. It seems I am now in a position that any time I was interviewing with facebook, my nerves will be so tense that I could not think or write code as I would have done otherwise, and collabedit, which is an excellent online tool, makes me feel bad as well.

The most recent one is particularly frustrating and the problem is simple, write a function to sort a linked list. OK, so what do you do? I didn't prepare this one, I have to admit, but chances are very small that you have prepared some problem and it did get asked, plus it amounts to cheating, although I do recommend to prepare as many interview problems as you can find. I am not particularly good at linked list manipulation and recursion, which are fundamentals.

So my first idea is to do selection sort, and I even had a neat idea to repeatedly get the max element and then you can insert into the front which is way easier than insert to the tail. The interviewer said OK when I asked whether he wants a more efficient way, which I am not sure at that moment, although I did mention heap and binary search tree. I know merge sort and quick sort, and shell sort, but didn't quite think they are applicable to linked list.

So I started coding, almost immediately I am a bit lost. Seems the list is changing and the loop condition is not as simple as for i=0 to N-1, and I need to keep track of one node ahead of the node I want to delete. I had something barely works and the interviewer asked why I have some repeated code. I told him that I need them to keep track of pred of curr node that was about to delete. Then everything is practically over. And the thank you letter is just a matter of time, although I did realize that merge sort is doable and told me so. He asked about quick sort, but Hoare's partition cannot be implemented on a linked list, Lumoto's will, but has a penalty into O(n^2) when the list has a lot of duplicates, plus it is a bit tricky to get any quick sort implemented correctly. If that was facebook wanted, then their engineers have to be superb.

When offline, selection sort seems not that hard and I have most correct ideas, although to get it right take some effort.

struct node {
int val;
node *next;
};

node* selection_sort(node *head)
{
if (head==NULL || head->next==NULL) return head;

while(head->next) // loop as long as list has 2 or more elements
{
int maxval=head->val;
node *prev=NULL, *curr, *newhead=NULL;
for(node *p=head; p->next!=NULL; p=p->next)
{
curr=p->next;
if (curr->val > maxval) { maxval=curr->val; prev=p; }
}
if (prev==NULL) { // remove head from list
head=head->next;
}
else {
prev->next = prev->next->next;
}
// insert curr into sorted list
curr->next=newhead;
newhead=curr;
}
head->next = newhead; // deal with last element in list
return head;
}

node* merge_sort(node *&head)
{
if (head==NULL || head->next==NULL) return head;
int n, i;
node *p, *left, *right, *tail=NULL;
for(n=0, p=head; p!=NULL; n++, p=p->next) ; // count number of nodes
for(p=head,i=0; i+1next) ; // find split point, which is p->next
left=head; right=p->next; p->next=NULL;

merge_sort(left);
merge_sort(right);
// merge
while(left!=NULL && right!=NULL)
{
if (left->val <= right->val) { p=left; left=left->next; }
else { p=right; right=right->next; }
// insert into tail
if (tail==NULL) { head=tail=p; }
else { tail->next=p; tail=p; }
}
while(left!=NULL) {
if (tail==NULL) { head=tail=left; }
else { tail->next=left; tail=left; }
left=left->next;
}
while(right!=NULL) {
if (tail==NULL) { head=tail=right; }
else { tail->next=right; tail=right; }
}
tail->next=NULL;
}

you can try to write quick sort with Lumoto partition here.

Second most recent one is write a function to flatten the list.

struct node {
bool is_atom;
int val;
node *child;
node *next;
};

node* flatten(node* &head)
{
}

emacs undo redo and cursor movement

So you know that C-x u or C-_ will undo most recent change, but how to redo?
emacs keeps track of previous changes and as soon as there is a command other than undo, maybe C-f, then it thinks all previous changes are undoable.

So to redo, just type C-f or any command to interrupt the undo sequence, then the next undo will be redo.

Also for cursor movement, C-Space or C-@ will mark the current location, then C-u C-Space or C-u C-@ will return to this location. Esc-< back to top of buffer, and Ese-> to bottom of buffer.

C-x 2 gives two horizontally aligned windows and C-x 3 gives two vertically aligned windows.

Saving a position records a spot in a buffer so that you can move
back there later. Moving to a saved position reselects that buffer and
moves point to that spot.

`C-x r SPC R'
Save position of point in register R (`point-to-register').

`C-x r j R'
Jump to the position saved in register R (`jump-to-register').

To save the current position of point in a register, choose a name R
and type `C-x r SPC R'. The register R retains the position thus saved
until you store something else in that register.

The command `C-x r j R' moves point to the position recorded in
register R. The register is not affected; it continues to record the
same position. You can jump to the same position using the same
register any number of times.

SRM 536

div2 p1000
simple DP, recursion with memorization, dp[pos] is max score end at pos.
need to sort score from low to high.
caveat: score can be negative so need to use bool memo[60] to remember whether dp[pos] has been computed already. otherwise an easy 1000 problem.

my proof of Wilson's theorem

The Wilson's theorem says that (n-1)! + 1 is divisible by n iff n is prime.

The only if direction is easy. If (n-1)! = -1, then (n-2)! = 1 mod n, so each of 1,2,...,n-2 are relatively prime to n. Clearly n-1 is relatively prime to n,  then 1,2,...,n-1 are all relatively prime to n, but this can only happen if n is a prime.
The if direction is harder.


When n is prime, let 1 < a < n, then a, a^2, ..., a^n-1 will hit 1, 2, ..., n-1, so

a * a^2 * ... ^ a^(n-1) = (n-1)! all arithmetic under mod n

then a^(n(n-1)/2) = (n-1)!

From Fermat's little theorem we have a^(n-1)=1
so ((n-1)!)^2 = a^n(n-1) = 1

Because n is prime, then (n-1)! can have only trivial roots, which are +1 and -1.

If (n-1)! = -1 we are done, so we now argue that (n-1)! not equal to 1.

Suppose for contradiction that (n-1)! = 1 for some prime n.
then n-1 + (n-1)! = 0
(n-1) (1 + (n-2)!) = 0
since n-1 neq 0
we have 1+(n-2)! = 0
therefore (n-2)!=-1
so (n-1)=1 // this is false. no idea how to fix it.
but this can only be true when n=2. QED.