On Binary Search

Recently failed a quixey challenge on binary search and went over the Knuth v3, although the notes below are from some code I have seen before.

Everybody knows binary search, but not good enough to write a perfect one.

Here the problem asks for something similar to c++ stl lower_bound

Given a[0..n-1] with a[0]<= a[1] <=... <= a[n-1], and int x, return pos such that if we insert x at pos, the order of a[] is preserved, that is, pos is such that
a[0]<= a[1] <=... <= a[pos-1] <= x < a[pos] <= ... <= a[n-1]
The version presented below has the invariants:

1. 1. m is a valid index, that is, 0 <= m < n
2. 2. each iteration, either l or u gets updated.
3. 3. a[l] < x and a[u] <= x. This is done by using phantom element a[-1] and a[n]
4. 4. Inside loop, l < m < n
5. 5. Outside loop, l+1=u

binsearch(a[0..n-1], int x) // returns first pos such that a[pos]>=x

l=-1, u=n 

while l+1 < u
  m = (l+u)/2
  if (a[m]

CF 182

The number is different from the actual round number, but refers to the final problem set index.

A: Shortest Path, Dijkstra.

B: easy, just add a fixed offset and you get the answer.

C: you are given an array of n int, n=10^5, and a number k, a number len, you are to compute the maximum sum (sum of int, then take abs of the sum), with the condition that you can flip at most k int in the current window of size=len. It is a typical problem with 1D array and sliding fixed-length window. You can query min in current window in O(n) time. But this problem is a bit different. This kind of problem is about what you need to remember in the past elements.

This solution is from watashi's code. When you are dealing with current window, you know you can flip signs of k numbers, and they must be same sign, all + or all -, so you need only the best k positives, and the best k negatives. But how do you update that information as the window slides to the right. Well, you need to drop one element x=a[pos-len] and you have one more element y=a[pos]. So if x is in top k, then x needs to be removed, after that you may need to put back the best one in remaining elements in a[pos-len+1] to a[pos-1] into top k. Now check y, if y can make into top k, then send y into top k, as a result the min in top k will get kicked out and you put it to the reserve. With that you can maintain a BST with count of appearance in each element. A multiset or a map comes in handy.

D: compute the number of factors between two strings, s1 and s2, with length up to 10^5. My approach is fairly complicated and I am a bit surprised to see it get AC. Basically I compute a gcd of s1 and s2, then get all factors of that gcd. To do a gcd in strings, assume s1 is longer. then keep taking s2 from s1 until it is no longer possible. Then the remaining s1, if still longer than s2, you know gcd is empty string. Otherwise let swap s1, s2 and keep going. To get all factors of gcd, simply try all factors of gcd.length() and this could take 10^5 * sqrt(10^5) = 10^7 which is fast enough, since n has at most O(sqrt(n)) factors. Actually this number is an over-estimate, as I tested numbers up to 10^7, the max is only about 500.

E: combinatorial counting and needs a DP solution. The problem statement is wrong but there are 200+ people got AC. It seems they can read the problem setter's mind to see what solution is intended. Actually that's exactly what you need to have when dealing with a DP problem.

TC SRM 541

p250: 50 ants move in grid, when two or more meet at same point, they disappear. each move at speed 1, and no two start at same position. The problem asks for number of ants remaining. Coordinates are from -1000 to 1000.

The only problem I know how to solve, basically after some limit, if two ants still not meet, they will never meet. So just iterate some fixed number of steps. The question is, what is the limit?

Since ants could meet at half way of an integer position, you need to multiply all coordinately by 2 so that they all meet in integer position. The limit is then (1000 - (-1000))/0.5 = 4000, to be safe you can use 4010 or 5000.

exod40 uses a different check, if (ox[i],oy[i]), (ox[j],oy[j) becomes (ox[j],oy[j]) (ox[i],oy[i]), that is, if two ants swap position, then they have to meet. the converse is true as well. so you can check that instead of multiply coordidates by 2.

vim line wrap or line break

When editing text files, you might want vi/vim to insert line break automatically.

:set textwidth=60

To format a paragraph, move cursor anywhere inside the paragraph, type gqip or gqap

all about bibtex and style

BibTeX and bibliography styles
http://amath.colorado.edu/documentation/LaTeX/reference/faq/bibstyles.html

http://en.wikibooks.org/wiki/LaTeX/Packages/Installing_Extra_Packages

Something called biblatex, in experiment

TCO qual 1A

Got a bit lucky and qualified in round 1A.

p250, easy if you see 2 counts are enough to win. An edge case is when there is only 1 player.

p500, if you see prime factoring, you got the problem. I am just slow in implementing it.

p1000, easy in algorithm but hard in implementation. Has some connection with 2SAT but you do not need that knowledge. I had the right algorithm but took two days to finalize the details of implementation. Guess my recursion/dfs implementation skills are terrible.

Here is my solution (offline)

#include <vector>
#include <string>
#include <iostream>
using namespace std;

#define MAX 1000
#define sz(a) int(a.size())

int bulb[60][5], state[60], tmp[60];
string initial;
vector<string> switches;

class EllysLights {
public:
int getMinimum(string _initial, vector <string> _switches);
};

bool dfs(int j, int st)
{
    tmp[j]=st;
    // check all bulbs
    for(int i=0; i<sz(initial); ++i) if (switches[j][i]=='Y') {
        int next;
        if (bulb[i][1]<0) { // bulb has one switch
            if (st == 0 && initial[i]=='N') {}
            else if (st == 1 && initial[i]=='Y') {}
            else return false;
        }
        else { // bulb has two switch
            next = bulb[i][0]; if (next==j) next = bulb[i][1];
            int target;
            if (initial[i]=='N') target = st;
            else target = 1-st;
            if (tmp[next]>=0) { // hit a visited switch
                if (tmp[next]!=target) return false;
            }
            else {
                if (!dfs(next, target)) return false;
            }
        }
    }
    return true;
}

int check(int j, int st)
{
    memset(tmp, -1, sizeof tmp);
    int ans=0;
    if (dfs(j, st)) {
        for(int k=0; k<sz(switches); ++k)
            ans += (tmp[k]==1);            
        return ans;
    }
    return MAX;
}

int EllysLights::getMinimum(string _initial, vector <string> _switches)
{
    int ans=0;
    initial=_initial; switches=_switches;
    memset(state, -1, sizeof state);
    // construct bulb
    memset(bulb, -1, sizeof bulb);
    for(int i=0; i<sz(initial); ++i) {
        int c=0;
        for(int j=0; j<sz(switches); ++j) {    
            if (switches[j][i]=='Y') bulb[i][c++]=j;
        }
    }
    for(int i=0; i<sz(initial); ++i) {
        if (bulb[i][0]<0 && initial[i]=='Y') return -1;
    }
    for(int j=0; j<sz(switches); ++j) if (state[j]<0) {
        int aa, bb;
        aa = check(j, 0); for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
        bb = check(j, 1);        
        if (bb < aa) {
            for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
        }
        ans += min(aa, bb);

//        cout << "switch " << j << ' ' << state[j] << ' ' << ans << endl;
    }
    if (ans <= sz(switches))
        return ans;
    else 
        return -1;
}

a probability problem

A robot enters a room with a large number of coins on the floor. It flips a coin if it is head, and toss a coin if it is tail. The problem asks what is the ratio of head to tail after sufficiently long time.

solution:
since we only need the ratio we might as well assume head=1-t and tail=t to begin with.
Then we work out a few iterations to see the pattern

(1-t, t)
(t/2, 1-t/2)
(1/2-t/4, 1/2+t/4)
(1/4+t/8, 3/4-t/8)
(3/8-t/16, 5/8+t/16)
(5/16+t/32, 11/16-t/32)

This should give enough evidence that whatever t you start with, the end ratio does not depend on t.
And to compute the final ratio, we can drop t and go through a few more calculations.
(21/64, 43/64)
(43/128, 1-43/128)

Now it is much clear that the sequence converges to some number. And what is the fixed point?
Let (x, 1-x) be a fixed point, one more iteration will make it 1/2*(1-x) and 1-1/2*(1-x)

Then we have x = 1/2*(1-x) and solve x=1/3, it satisfies the other equation as well. It is almost obvious that if you start with (1/3, 2/3) you next iteration must be 2/3*1/2=1/3 and 1-1/3=2/3, where you start with.

So the answer is 1 to 2.

One more problem,
you have 50 shoe laces so there are 100 ends. You randomly tie two ends until you finish tying all 100 ends. What is the expected number of cycles?

Solution:
First we work out small examples:
n=1 ans=1
n=2 ans=1+1/3, with prob=1/3 the first lace will tie at both ends so we have 2 cycles, with prob=2/3, we have 1 cycle.

Now try to generalize. Treat each end as a vertex and the lace and the tying as edges, we have each vertex having deg=2, so they form a collection of disjoint cycles. Therefore we have a one-to-one mapping from cycles in n=k-1 to n=k, assuming the k-th lace does not have its two ends tied together. In this case we have expectation = E[n=k-1], and the other case is that we have one extra cycle, that part = 1/(2*k-1) * 1,

So the answer is
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2*n-1)