OJ Board

O(M logN) with probably a high constant factor...

The trick i think is,
making 2D arrays and accessing them requires more time,
than making a 1D array and then store the adjacency matrix - each row in the form of a 30 bit integer.
Also, i used a simple recursive DFS, nothing fancy.
This gave me AC in 2.64 seconds. :)

also, i suggest searching for ...

there are far too many primes to generate in the range from [2, 2^31). even if there were a method to generate these primes directly in O(1) one after the other (which by the way is not the case), storing them all would be an issue.

i suggest looking at http://primes.utm.edu/howmany.shtml to get an ...

http://www.math.tau.ac.il/~segevd/Papers/Label-Slides-25min.pdf

this presentation, points out the definition of the problem that is very similar to this problem. note that they even consider weights of colors, and the problem is stated as, optimize the selection of colors such that the weights of ...

just adding to the ideas i used (but inevitably still TLE on)
the number of nodes are limited to 30. i use bitwise to store the connectivity for each color, but updating them for each combination still required N*N iterations. so still TLE.

by the way, i found on the net that this problem is a ...

I need help with this problem. the link to it is
http://acm.timus.ru/problem.aspx?space=1&num=1500

I am trying all combinations of K and then running union-find for checking connectivity from 0 to 1 on the combination. but that is giving me TLE. please suggest a faster algorithm or any ...

thanks, i got AC now.
it was very unobvious to me that the numbers could be negative but the definition divisibility seems to fit perfectly well to them too.

wish i could have found that during the contest though..

are there any trick cases for this problem?
i make a sieve of 10 million and use this to factorise the number.
i also count how many factors there are of the number. such as for 32, there is 1 factor only so i output -1

but this kept giving me wrong answer during the contest.

one way i could do this is
find the minimum number of swaps between the original sequence and the final sequence, where the final sequence maybe any one of the (2*N) possible sorted sequences.
the step for finding the minimum number of swaps takes O(N) time.. so this algorithm would be bounded O(N^2)

you can see the problem description here...
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3764

no one solved the problem during the contest time and the problem was used again by the kanpur site for there online preliminary this year.
i can't seem to think of framing this in ...

tell me if i'm wrong, but the problem is less comparable to either the MST or Shortest Path Algorithms and more comparable to the travelling salesperson problem.. which has no other way of perfectly solving it except a brute force

the problem:
i have the weight of any number of coins...
i have also the specification of the coins in my currency as... weight and value.
i have to find the minimum possible value with which the weight can be filled...

what do you blv is the fastest way ta do it?

i'm kind of a newbie(this was like the 20th problem i cracked)...
yes i got something like accepted-actually it says a presentation error
this was the first problem for me that would require lond double and big integer... but i worked it out
thank you for the help...

well the question says "if P(i,j) is undefined print -1 with similer formatting
but for every input we output two lines right?
the first one will be -1... but what do we put in the second line?
i was able to work out the "mathematics" behind the question and am getting the outputs correct for the ...

thanks a lot for the help...
i got accepted now.
i guess the problem indeed was fixed just by substituting the value of PI...
perhaps something to do with portability of code and difference in gcc/borland(i use borland though).
Thanks a lot again