i solved it using special sweep method, but can by solved by quad tree also.
2010/2/17 Piyush Verma 114piy...@gmail.com
any algorithm to solve this problem...
ACM uses a new special technology of building its transceiver stations.
This technology is called
Modular Cuboid Architecture (MCA)
EASY!
2010/2/10 Rohit Saraf rohit.kumar.sa...@gmail.com
There are n men. And you have been given say m information's like :
m_i was born after m_j died
m_i talked to m_j sometime
You need to find the consistency of the sets of information in O(n+m).
-Rohit
--
You received this
longest path can be solved in acyclic directed graphs.
so check your case if it is not that.
2010/1/15 Vivek S s.vivek.ra...@gmail.com
@chitta koushik
No, That might lead to negative edge cycles!
2010/1/15 chitta koushik koushik.infin...@gmail.com
How abt negating values and using same
LOL search for dominance in graph.
2009/10/7 ankur aggarwal ankur.mast@gmail.com
Given a graph..
Find the minimum number of coloring (Marking) required to node such that
every node in the final graph is connected by at least one of the
colored(marked) node.
ex:
AB
AC
BD
BE
CF
So at each step you can move any number of beads form some betwwen some
pairs (in particular more than one) of adjecent vertices?
It seems to be complicated problem.
IMHO it is about some routing strategy than graph flow.
If you do reduction to edge capacit, than the maximum flow and longest path
, the ford fulkerson algorithm and others
...
On Wed, Sep 30, 2009 at 3:46 AM, Miroslav Balaz
gpsla...@googlemail.comwrote:
So at each step you can move any number of beads form some betwwen some
pairs (in particular more than one) of adjecent vertices?
It seems to be complicated problem
this
.
Max flow - min cut theorem , the ford fulkerson algorithm and others
...
On Wed, Sep 30, 2009 at 3:46 AM, Miroslav Balaz gpsla...@googlemail.com
wrote:
So at each step you can move any number of beads form some betwwen some
pairs (in particular more than one) of adjecent vertices
each number except one is there only once, and one number that repeats can
repeat power of two times. 2,4,8,16.
the best solution is to use trie, it is linear in number of bits of input.
But It is interresting if there is solution using unit cost arithmetics.
Or by using randomized algorithm, and
What you mean by unicode supprot?
I think only problem is that characters that look the same may have
different encodings.
So it is enough in each compare to use the function that resolves above
problem.
I made 3 suffix tree implementations and it is easy to change string type in
that.
But my
__bitcount(a ^ b), or use bitset32
or
int x=0;
int y=a^b;
while(y) {x++;y=y-1;}
return x;
2009/8/17 Pramod Negi negi.1...@gmail.com
i guess XORing A and B and count the no of set bits will do.
On Sun, Aug 16, 2009 at 11:09 PM, richa gupta richa.cs...@gmail.comwrote:
Given two integers A
I think the teoreticaly easiest solution is to have two balanced binary
search trees interlinked. on for finding by string, second for keeping count
second can keep subtree sizes, and every time you check the position and if
it changes then you can update list, you do not have to make more
Just substract 3 till grater than 2 if you end with 0 it is divisible
othervise not, or you can binary search the result
division by 2 is just shift.
2009/8/14 Yogesh Aggarwal yogesh.aggarwa...@gmail.com
@arun : we are not supposed to use / operator. but in ur algo u r using /
or % has to be
NP-COMPLETE
2009/8/14 fundoonick fundoon...@yahoo.co.in
Problem:
I have a set of positive integers. I have to divide it into 2 sets such
that the difference of the sums of both sets is minimum.
For ex, the given set of +ve integers is: 1,2,3,4
I divide it into 2 sets {1,4} and {2,3} such
Ok your question have some little catch hidden.
But first let me was the question.
Does each vertex has at least one forbiden color?
because if you can have no forbiden colors you end up with clasical
3-coloring problem which is NP-Complete.
The catch is that if P=NP then everything nontrivial is
as arrays have fixed size
Also fibonacci heaps support union of heaps.
Arun,
On Sat, Aug 8, 2009 at 1:32 AM, Miroslav Balaz gpsla...@googlemail.comwrote:
No there si no such function.
The best solution would be not to use priority queue, but other design.
If it wont work you can try to use
No there si no such function.
The best solution would be not to use priority queue, but other design.
If it wont work you can try to use splay tree. But it has big overhead.
Theoreticaly best would be fibbonaci heap but it heas even bigger overhead
than splay tree.
2009/8/7 mirosuaf
demonstration.
but I must know two things if you enjoy:
1) are that I must show that the distance between A and B equals the
distance between f (A) and f (B)?
2) are that the algorithm is to explain or not?
and thank you
On 18 juil, 16:29, Miroslav Balaz gpsla...@googlemail.com wrote
such errors there.
2009/7/15 mimouni mimouni.moha...@gmail.com
you can consult in: http://www.wbabin.net/science/mimouni2e.pdf
and I finished on implimentation schedule a php (to find the labels
for a graph exceeds 5000 vertices).
On 14 juil, 19:25, Miroslav Balaz gpsla...@googlemail.com wrote
And also you should answer the main question , how will you find the
automorphism function?
Or how would you use the theorem only to decide if there exists an
isomorphism?
2009/7/16 Miroslav Balaz gpsla...@googlemail.com
I think that there is logical error, in the proof what do you think about
LOL program it yourself, nobody will do work for you here. We can only help
someone by giving advice, or discussing interesting topics.
2009/7/12 Davood Vahdati davoodvahdati2...@gmail.com
Dear sirs and madams :
I Wan't C++ Source Code program About thos questions in Acm
2004-2005Problems
LOL, you should heve some ordering of elements, and only cnstruct
nondecreasing sequence
like nuber are like ordered by liek a value, and you can like order any
finite set like you want.
2009/7/9 lad4bear lad4b...@gmail.com
Thanks for all the help guys.
And Geoff, sorry to be a pain but can
It is also so easy, but maybe requires more lines of code
you only need count number of used number for each 1..n
and then...(repeat recursive approach)
ONE LINE SOLUTION IN C++
ok use next permutation from STL, read how it works for other language
and initialize array 11223344, and do while
I think maybe someone is good at algorithm, but has no time to learn that
linux stuff.
I can help you, install Vista again, on that partition where there is no
Mandriva, then you need tu run some LILO conf maybe is enough, you can have
it from any other bootable linux CD. but i am only algorithm
I know a question for genuis
if P=deterministic polynomial time
NP=neondeterministic polynomial time
then NP-P= ?
2009/6/3 석문기 smgs2...@gmail.com
Qestion is not for genius;;;
Easy question .
*From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On
Behalf Of *Aminooo~
a + b =a(a+b) is that comutative?
2009/6/2 Arun prasath aruntendulkar2...@gmail.com
144
On Tue, Jun 2, 2009 at 3:00 PM, Aminooo~ amin...@gmail.com wrote:
*Dear Friends,*
* *
*A question for the genius, the one who solve the problem will write the
name in the attached file.*
*IF;
Does anybody know how to simulate semaphore by binary semaphore?I think it
is easy, but i cant find it on internet. thanks
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Of course , and i didnt find it there.
2009/5/31 Ajinkya Kale kaleajin...@gmail.com
did you try the wiki :
http://en.wikipedia.org/wiki/Semaphore_(programming) ?
On Sun, May 31, 2009 at 4:57 PM, Miroslav Balaz
gpsla...@googlemail.comwrote:
Does anybody know how to simulate semaphore
and that polygons are convex?
2009/5/25 Ralph Boland rpbol...@gmail.com
On May 24, 5:05 am, Albert albert.xtheunkno...@gmail.com wrote:
Hi,
I'm 15 years old and I'm interested in algorithms, data structures,
computational geometry and general coding. What sort of projects could
I
Miroslav Balaz wrote:
you should register on www.topcoder.com!!!
and according to your skill you should try to solve some problems
fromhttp://www.spoj.pl/or acm.sgu.ru
Okay, but I'd like an idea of real-world programming and not just
trying to solve hard problems under timed conditions
I thing you dont understand what we are all saying.
//There are two ways how to optimise the codec.
//1. disable all porn videos, and illegal movies
//2. do not output anything on screen
The codecs are all about mathematics, there is no programming at all...
If some theory gives you an
you should register on www.topcoder.com !!!
and according to your skill you should try to solve some problems from
http://www.spoj.pl/ or acm.sgu.ru
If you were from Slovakia or czech i'd recomend you www.ksp.sk
2009/5/24 Albert albert.xtheunkno...@gmail.com
Hi,
I'm 15 years old and I'm
the link is not working http:// ilpubs.stanford.edu:8090/750/1/2003-29.pdf
2009/5/6 UKuser spiderc...@yahoo.co.uk
As per my previous post, is there anybody who can explain section 3 to
me from the PDF mentioned in this link:
http://groups.google.com/group/algogeeks/t/6ccc544529b01d10
Any
This is very old problem, and the solution is well known.
2009/5/1 Dave dave_and_da...@juno.com
This algorithm doesn't work.
Try A = 2, 6, 10, 14, 18, 22, 26
and B = 4, 12, 20, 28, 36, 44, 52
with k = 6.
You find x = A[6] = 22 (assuming 1-based arrays) or 26 (assuming 0-
based arrays)
...@googlegroups.co
On Tue, Apr 28, 2009 at 9:40 AM, Miroslav Balaz
gpsla...@googlemail.comwrote:
ok, now seriously, wtf is that? Is that in what language it is? And what
does CALL DA_WRITE_HALO(A, (/CYCL, CYCL/), (/1, 1/))
When you can ask me without cussing at me I will answer you.
2009
ok, now seriously, wtf is that? Is that in what language it is? And what
does CALL DA_WRITE_HALO(A, (/CYCL, CYCL/), (/1, 1/))
2009/4/28 Martin Michael Musatov marty.musa...@gmail.com
PROCESSORS P(NP, NP)
RANGE X(N), Y(N)
DISTRIBUTE X ONTO P(BLOCK, *)
DISTRIBUTE Y ONTO P(*, BLOCK)
SHADOW
nice reasoning, but this is something for what books are. It is more
numerical mathematics that algorithms
for example if you want sin(f(x)) to be precise up to 100 digits, how
precise should be f(x) ?
2009/4/6 alex zch051383471...@gmail.com
I have got some ways to settle Fibonacci numbers
no that is just asymptotic recursion.
the answer is between n^2 and n^2log n
of coure the answer is n^2;
T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2
T(n) B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n
n
n/2 n/2
n/4 n/4
:18 PM, Miroslav Balaz gpsla...@googlemail.comwrote:
no that is just asymptotic recursion.
the answer is between n^2 and n^2log n
of coure the answer is n^2;
T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2
T(n) B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n
It is possible to do that with only O(n) invications, i answered it already
to this group...
2009/4/1 DragonZsnakE dragonzsn...@gmail.com
( n cards are there initially )
we pick out the first card in random it takes n-1 comparisons to figure out
its Equivalence card -n-1 steps
Two
BAN
2009/3/28 saha.dipan...@gmail.com saha.dipan...@gmail.com
Please give me an algorithm for this problem---
Show that if an edge(u,v)is contained in some MST, then it is a light
edge crossing some cut of the graph.
i need a solution very urgently...
plz help..
That is not true, there are carmichaels numbers that are 32bit...,
but there is another priamlity testing algorithm, that is log n, and uses
something like fermat therorem, that you can do form 2,3,5 and it works
under 20 000 000.
I dont remeber how the test is done, but maybe it is that you do
Yes this is classicalproblem,
it can be reduced to Min-cost max-flow. But there are other algorithms. you
can find answer here
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=hungarianAlgorithm
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=minimumCostFlow1
2009/3/19, libicocco
I was looking in VIJAY VAZIRANI Approximation Algorithms, but from the Table
of contents , it seems that such algorithm is not there.
But you should try searching algortihm for finding maximal independent set
of fixed sized boxes or unit sided it is somewhat dual, and there is
good
of real life applications for the problem, like garbage
collection, a version of postman problem, gas system construction.. I am
looking for applications for the problem in networks, if any one can help.
On 3/14/09, Miroslav Balaz gpsla...@googlemail.com wrote:
NP what?
2009/3/13 Amina
exponent inputs are
1, 2, 3, 4, 5, 6, 7, 8
and there are so many partition problems, which maximum partition
produce the result, [1,2,7,8] [3,4,5,6]?
thanks
Miroslav Balaz wrote:
so the permanent is like determinant but without sign in summand.
I have found something interesting in your
, Miroslav Balaz gpsla...@googlemail.com wrote:
Do you have polynomial algorithm for that problem?
We don't need one another NP-copmlete problem. There is enough of them.
And there are more interresting problems for which we don't know
reduction.
The rule of thumb is, that if you pick random
can you also provide description of bdhg,cbg or hyperlink to them.
Is this question hard? I am not graph expert.
2009/3/7 Monty praveensonare...@gmail.com
the hamiltonian circuit (HC) problem remains NP-complete when
restricted to chordal bipartite graphs (cbg) and becomes polynomial
when
of course, you cannot assume that array is in ascending order, it is in
non-decreasing order however not in ascending
and you should swap order here :(a[mid+1] key||mid==high)
2009/3/4 Kapil navka...@gmail.com
just fixing a bug
what if you write bin_search as this
//assumption array is in
tells n sorted array...
On Wed, Mar 4, 2009 at 4:55 PM, Miroslav Balaz gpsla...@googlemail.comwrote:
of course, you cannot assume that array is in ascending order, it is in
non-decreasing order however not in ascending
and you should swap order here :(a[mid+1] key||mid==high)
2009/3/4
cout ((int)((int*)upperbound(a,a+5,k)-a))/4-1;
2009/3/1 sharad kumar aryansmit3...@gmail.com
#includeiostream.h
int main()
{
int a[5]={3,3,3,6,7};
int k;
cink;
int i=0,j=1,c=0;
for(;i5;i++)
{
if(a[j-1]!=a[i] a[i]!=k)
j++;
else
c=i;
}
coutc;
return 0;
}
On Sun, Mar 1, 2009 at
=mid;
else if(a[mid]key)
start=mid;
else
return mid;
}
int search(int a[],int key,int n)
{
int p=binsearch(a,0,n,key)
if(p=0)
while(a[p]==key)
p++;
return p-1;
}
On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz gpsla...@googlemail.com
wrote:
cout ((int)((int
think Mr. Balaz ?
2009/2/20 Miroslav Balaz gpsla...@googlemail.com:
I thing you the only choice, is binary search tree, but it is the most
obvious one. It imposible to make it independent form cards universe,as
far
as i know
but it can be made int time O(log(nmU)),where U is number of cards
This is not algorithm problem, it is homework problem do it yourself.
I see there one problem, and it is how large is N
I suggest you to represent sets as pairs(cardID,repeat number )
that means for each card you remember number of how much you have of that
card, and when there is zero, it means
Hmm, it is strange that you are discusing such a basic thing. You should not
post your homework here, but maybe some research problems.
This is so easy stuff, that many people may make mistake when explaining it.
But if node has right child, then the successor is minimum of that subtree.
But if
I think it is secret, because the general idea is simple, but implementation
is issue, because speed can be limiting factor.
Maybe they use som specific aspects of language, for exmple statment
delimiters like,semicolon in C++,java, or newlines in VB to simplify
parsing, and error recovery.
I
darthcontin...@gmail.com
Are you on something...? Not on TO something but ON something??
No more than 1-2 of the objects at the TOP level, and each layer is
LARGER than the first.
On Jan 19, 7:16 am, Miroslav Balaz gpsla...@googlemail.com wrote:
LOL, according to your definition
you will use stack, and you have 2 kind of values in stack, one is visit
node first time, and second is wisit node for second time
when first time: you put visit this node for second time and then you put
visit nododes for first time to stack for all descendands
when second time: you calculate
OK, I think the only known solution is that trivial, it can be proved that
it have complexity of O(sqrt(n)),
solution
k=2
iterate {
if(k divides n) return unlucky
if(kn) return lucky;
n=n-n/k;
k=k+1;
}
after x iteration the n will be at most n/x;
2009/1/7 Miroslav Balaz gpsla...@googlemail.com
ok that was bullshit, the number of lucky numbers is about 10^9
2009/1/7 Miroslav Balaz gpsla...@googlemail.com
You should generate all the lucky numbers, less than 10^18, there shouldy
not many of them. maybe 50. And then just submit program using hardwired
array.
2009/1/6 Rahul Kushwaha
You should generate all the lucky numbers, less than 10^18, there shouldy
not many of them. maybe 50. And then just submit program using hardwired
array.
2009/1/6 Rahul Kushwaha rahul.kushw...@gmail.com
can anybody tell me which is best and correct solution
On Tue, Jan 6, 2009 at 12:30 AM,
the code is wrong and unsafe, because you use char buffer[MAX], what is
local varieable defined on stack. it is only valid while the modify
procedure is executing
You only have the option to use global or static variable, or second
parameter, or allocate memory on your own using new, or malloc
:37 am, Miroslav Balaz gpsla...@googlemail.com wrote:
i think that, you could just simulate the tournament, ande before each
weak
you sort players by number of played matches, and if this numer is same
then
by name.
And after you have them sorted,you just assign an oponent to first
player
Of course it is , because both problems are NP-COMPLETE.
But the transformation is non-trivial, it only comes from the definition fo
NP-Completeness
2008/12/16 Golabi Doon golabid...@gmail.com
Hello folks,
I am trying to solve a non-standard TSP problem with no success so
far. I would
i think that, you could just simulate the tournament, ande before each weak
you sort players by number of played matches, and if this numer is same then
by name.
And after you have them sorted,you just assign an oponent to first player,
in such way that you choose the one the first one with whom
i think it will not perform good, if you have cards like this 1 2 3 4 5 5 5
5
the supposed solution is, keep one counter and one candidate
first , the candidate is the first element, and counter is 1
if the next card equals candidate increase the count to 1, else decrease it
if counter is zero you
ok, and when n is not even, you need to test explicitly the last element
with the whole cards.
2008/12/10 Miroslav Balaz [EMAIL PROTECTED]
I thik it is wll known classical problem,or there is some similar well
known problem, you need O(n) comparisons.
Randomized
pick eight random cards
I thik it is wll known classical problem,or there is some similar well known
problem, you need O(n) comparisons.
Randomized
pick eight random cards and compare then to each other.
and you have very low probabilty that you always choose bad card.
Deterministic.
just compare 1 and second, third and
Fibbonaci heaps are not the fastest way in practice, they are only
theoreticaly faster for large enough n.
I heard about some techniques where they are only integer numbers.
2008/12/7 TheTravellingSalesman [EMAIL PROTECTED]
I was about to start implemening max flor min cut and shortest path
you are mistaken, you dont understant do repead until semantics
until stops the loop when expresions is TRUE
2008/11/27 Roman Yakovenko [EMAIL PROTECTED]
Hi. Second edition of Introduction to Algorithm defines the
following algorithm
HOARE-PARTITION(A, p, r)
1 x ← A[p]
2 i ← p - 1
3
it is possible to avoid duplicate solution, but i dont know if it is the
same effective, and i am not sure if it is correct;
you consider first coordinates in row mayor order, and first uncovered cell
must be covered by some top left corener of remaining pentomino.
from here i am not sure if you
On Wed, Nov 26, 2008 at 4:03 PM, Geoffrey Summerhayes [EMAIL PROTECTED]wrote:
On Nov 25, 6:34 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Hello,
I'm trying to write an algorithm counting all possible ways (symmetry
included) a grid of dimensions NxM can be covered with a prescribed
, and the algorithm never
generates the same vector twice
On Wed, Nov 26, 2008 at 9:27 PM, Geoffrey Summerhayes [EMAIL PROTECTED]wrote:
On Nov 26, 1:40 pm, Miroslav Balaz [EMAIL PROTECTED] wrote:
It is too slow, i replied with better solution , bu i dont know how this
forum works.
I
I dont thing if that problem is requiring backtracking algorithm, pleas try
better description of the real case.
how are those sets defined? if they are defined by enumerating its elements,
you can compute intersection in O(n) if they are sorted.
On Thu, Nov 6, 2008 at 2:32 PM, Luciano Pinheiro
for eash ith person in this tree.
Thank's You.
2008/11/6 Miroslav Balaz [EMAIL PROTECTED]:
I dont thing if that problem is requiring backtracking algorithm, pleas
try
better description of the real case.
how are those sets defined? if they are defined by enumerating its
elements,
you
Because NEXP means non-deterministic exponecial , what is another class of
problems, but NEXP problems are not so common in practice tahn NP problems.
The answer to your question is that, because for each NP problem there
exist deterministic polynomial time algorithm, that can verify whether a
75 matches
Mail list logo
