Hi,
I came across the following question a couple of days back -
"There are n women sitting at positions (0, 1), (0, 2), . . . , (0, n) in
the plane, and there
are n men sitting at positions (1, 1), (1, 2), . . . , (1, n). Each woman
is interested in
communicating with only a subset of the men
A sorted array A[1...n] composed of distinct integers
=> A[i] < A[i+1]for i = 1..n-1
=> A[i]-i < A[i+1]-ifor i = 1..n-1
=> A[i]-i <= A[i+1]-(i+1) for i = 1..n-1
Let B[i]=A[i]-i for i=1..n, then B[1..n] is sorted in non-decrease
order. A[i]=i <=> B[i]=0.
Do a binary
do binary search ... if A[i]http://groups.google.com/group/algogeeks?hl=en.
we are given a sorted array A[1...n] , composed of distinct integers,
(the values can be negative). We want to determine if there is an
index i such that A[i] = i.
Give an O(logn) algorithm to solve this problem , and justify its
correctness
--
You received this message because you are subsc
You are given an array A of n distinct integers , expressed in binary.
Each integer is in the range [0,n] .As there are n+1 values in this
range, there is exactly one number missing .As a single operation, you
may access the jth integer(A[i][j]) . Note that it would take O(nlogn)
time to read the f
Suppose n=2^k, a(0), a(1), ..., a(n-1) are the n teams
1. If there are 1 team, then no matches, 0 days needed;
If there are 2 teams, arrange 1 match for them, 1day needed.
2. Split the n teams into 2 groups of equal size, ie.
a(0),a(1),...,a(n/2-1) and a(n/2),a(n/2+1),...,a(n-1).
3. Constru
@ ashish .. each team should play the other team at least once.
in merging that thing does not happen.
On Thu, Apr 8, 2010 at 9:42 AM, Ashish Mishra wrote:
> Can it be done in more or less like merge sort way
> i.e 1. divide array into half
> 2. keep on doing it till u have two element lef
Can it be done in more or less like merge sort way
i.e 1. divide array into half
2. keep on doing it till u have two element left
3. arrang match between two and return winner
On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» wrote:
> Can any one help me with this problem
>
>
> Its a divide and co
You 've got n teams and nC2 ways of conducting the matches with specified
constraints
that's n/2(n-1). So, each day you need to conduct n/2 matches such that, no
team repeats within a day, no match that was previously held repeats. Since
the problem has an unique solution, you can either brute forc
Following are the recurrences:
T(n)=2T(n/2)+1
T(2)=1
T(n)=n-1
=O(n)
1 is added because winner of both the sides will compete at most 1 once.
for Time table u can form a tree
x1 x2 x3 x4 x5
\ / \ / /
x1 x3 /
\ \ /
\ x5
\ /
x1
Here are fou
Can any one help me with this problem
Its a divide and conquer problem where, there are n teams and each
team plays each opponent only once. And each team plays exactly once
every day. If n is the power of 2, I need to construct a timetable
allowing the tournament to finish in n-1 days...
An
11 matches
Mail list logo
