a summer game puzzle, basically given a board with char, ask for a route of knights moves without intersecting itself. The concatenated string is the address of interviewstreet mountain view office.
After several failed attempts, about a dozen, with hand, I have to write a program to do it. DFS with intersection checking. Finally got accepted. Now wondering what are the mysterious gifts they claimed to give away.
Saturday, June 23, 2012
Sunday, June 17, 2012
mihai patrascu passed away at 29
A star in theoretical computer science, made fundamental contribution to data structure and lower bounds, passed away this year at age of 29.
Wednesday, June 13, 2012
achilles tendor rupture
A non-technical one. This happens when I was playing badminton, then a pop. Had surgery two days later and now in splint. The full recovery takes 6 months, so I have to be patient. All activities are kept at minimal level, including programming competition.
a graph exercise
From Dasgupta's Algorithms book.
Given an undirected graph, find a subgraph such that each vertex has at least 5 neighbors and at least 5 non-neighbors.
This is a simple problem but it took me an afternoon to figure out the algorithm.
Disclaimer: my solution may not be the most efficient, nor does it represents a consent from the authors for being correct.
The whole idea is about degree. Let deg(v) be the degree of vertex v in current graph. We know that in the final graph, all deg(v) must be
5 <= deg(v) <= n-6
the >=5 is obvious, the n-6 upper bound comes from the need to have 5 non-neighbors.
A simple observation is that if the input graph G has all vertex v with deg(v) within bound, then we are done. Otherwise there is at least one vertex violating the bound. To convert any graph G into a graph with only valid vertex (deg within bounds), we repeat the two operations until done:
1. Remove all vertex v with deg(v) <=4, until no such vertex available.
2. Remove all vertex v with deg(v) >=n-5, until no such vertex available.
op 1 is obvious, if v has deg<=4, then it can never have deg>=5 if we remove other vertices.
op 2 is for a similar reason, if a vertex has deg>=n-5, that implies it has less than 5 non-neighbors. Because we only remove vertex, removing other vertex cannot make v have more non-neighbors. So we have to remove v from the graph to make all vertices valid.
For complexity, we do at most |V| iterations, each iteration takes O(|V|+|E|) time to count deg for each vertex, for a total of (|V|^2 + |V||E|)
Given an undirected graph, find a subgraph such that each vertex has at least 5 neighbors and at least 5 non-neighbors.
This is a simple problem but it took me an afternoon to figure out the algorithm.
Disclaimer: my solution may not be the most efficient, nor does it represents a consent from the authors for being correct.
The whole idea is about degree. Let deg(v) be the degree of vertex v in current graph. We know that in the final graph, all deg(v) must be
5 <= deg(v) <= n-6
the >=5 is obvious, the n-6 upper bound comes from the need to have 5 non-neighbors.
A simple observation is that if the input graph G has all vertex v with deg(v) within bound, then we are done. Otherwise there is at least one vertex violating the bound. To convert any graph G into a graph with only valid vertex (deg within bounds), we repeat the two operations until done:
1. Remove all vertex v with deg(v) <=4, until no such vertex available.
2. Remove all vertex v with deg(v) >=n-5, until no such vertex available.
op 1 is obvious, if v has deg<=4, then it can never have deg>=5 if we remove other vertices.
op 2 is for a similar reason, if a vertex has deg>=n-5, that implies it has less than 5 non-neighbors. Because we only remove vertex, removing other vertex cannot make v have more non-neighbors. So we have to remove v from the graph to make all vertices valid.
For complexity, we do at most |V| iterations, each iteration takes O(|V|+|E|) time to count deg for each vertex, for a total of (|V|^2 + |V||E|)
Monday, June 4, 2012
children and candy problem
N children in a circle, each with some number of candies in hand, a_1,a_2,...,a_n. There is also a basket with unlimited candies.
In each round, each child gives half of his candies to the next child, if a_i is odd, he/she gets one more from the basket to make it even. The process terminates if all children have equal number of candies in hand.
The problem is: Will the process terminate?
Intuitively the answer is yes. But the proof ?
I used to have a better proof but I forgot. Here is the one I have now.
Proof by induction on max-min. Base case is diff=max-min=0, and the process stops without any round. For inductive step, notice that max of all children never increases after a round, while there is at least one min gets killed in one round.
Consider a_i which is min and a_i-1 is strictly larger than min. Then after a round, a_i will be strictly larger than min and a_i-1 stays strictly larger than min, regardless of what a_i-2 is, even if it is min. Therefore after no more than n rounds we killed all min. That is min now increased by at least 2. Applying the inductive hypothesis, we conclude that the process will terminate with max-min = 0
In each round, each child gives half of his candies to the next child, if a_i is odd, he/she gets one more from the basket to make it even. The process terminates if all children have equal number of candies in hand.
The problem is: Will the process terminate?
Intuitively the answer is yes. But the proof ?
I used to have a better proof but I forgot. Here is the one I have now.
Proof by induction on max-min. Base case is diff=max-min=0, and the process stops without any round. For inductive step, notice that max of all children never increases after a round, while there is at least one min gets killed in one round.
Consider a_i which is min and a_i-1 is strictly larger than min. Then after a round, a_i will be strictly larger than min and a_i-1 stays strictly larger than min, regardless of what a_i-2 is, even if it is min. Therefore after no more than n rounds we killed all min. That is min now increased by at least 2. Applying the inductive hypothesis, we conclude that the process will terminate with max-min = 0
Saturday, June 2, 2012
TCO 2C
My last round in TCO, and finally I got one problem correct.
p300 looks doable by just brute-force all possible choices. However search from 1 to 9999 might be too slow. A minute of thinking makes you realize that you only need to try all possible out-edge weight +1,0,-1, and that's all. The rest is just implementation which took me about 40min.
p500 and p900 all look doable, at least I understand the problem statement. The problem is, how to do it fast? Need to read the editorial, I guess.
In terms of difficulty, 2C is easier than 2A and 2B, at least it seems to me. There are quite some people finishing all 3. I have yet to make my first successful p500 submission.
p300 looks doable by just brute-force all possible choices. However search from 1 to 9999 might be too slow. A minute of thinking makes you realize that you only need to try all possible out-edge weight +1,0,-1, and that's all. The rest is just implementation which took me about 40min.
p500 and p900 all look doable, at least I understand the problem statement. The problem is, how to do it fast? Need to read the editorial, I guess.
In terms of difficulty, 2C is easier than 2A and 2B, at least it seems to me. There are quite some people finishing all 3. I have yet to make my first successful p500 submission.
interviewstreet elastic
https://elastic.interviewstreet.com/challenges/dashboard/#problems
The problems look accessible, but I only managed the last one with 50pt. It is DFS by the way.
Problem A: how to do it fast?
The problems look accessible, but I only managed the last one with 50pt. It is DFS by the way.
Problem A: how to do it fast?
Subscribe to:
Posts (Atom)
