## Search found 17 matches

Thu Apr 09, 2009 10:25 pm
Forum: Volume 115 (11500-11599)
Topic: 11592 - Bulb inside a Grid (II)
Replies: 2
Views: 2389

### Re: 11592 - Bulb inside a Grid (II)

O(M logN) with probably a high constant factor...
Sun Aug 24, 2008 6:53 am
Forum: Algorithms
Topic: Timus Online Judge - 1500 Pass Licenses
Replies: 6
Views: 2051

### Re: Timus Online Judge - 1500 Pass Licenses

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 "...
Thu Aug 21, 2008 5:53 am
Forum: Algorithms
Topic: Big prime
Replies: 1
Views: 855

### Re: Big prime

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 ...
Thu Aug 21, 2008 5:40 am
Forum: Algorithms
Topic: Timus Online Judge - 1500 Pass Licenses
Replies: 6
Views: 2051

### Re: Timus Online Judge - 1500 Pass Licenses

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 th...
Mon Aug 18, 2008 6:58 am
Forum: Algorithms
Topic: Timus Online Judge - 1500 Pass Licenses
Replies: 6
Views: 2051

### Re: Timus Online Judge - 1500 Pass Licenses

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 "Mini...
Sat Aug 16, 2008 3:23 am
Forum: Algorithms
Topic: Timus Online Judge - 1500 Pass Licenses
Replies: 6
Views: 2051

### Timus Online Judge - 1500 Pass Licenses

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 optimization ...
Sat Jul 12, 2008 11:28 pm
Forum: Volume 114 (11400-11499)
Topic: 11466 - Largest Prime Divisor
Replies: 29
Views: 16015

### Re: 11466 - Largest Prime Divisor

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..
Sat Jul 12, 2008 10:55 pm
Forum: Volume 114 (11400-11499)
Topic: 11466 - Largest Prime Divisor
Replies: 29
Views: 16015

### 11466 - Largest Prime Divisor

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.
Fri Sep 28, 2007 2:53 am
Forum: Algorithms
Topic: minimal swaps cyclic permutation
Replies: 1
Views: 1943

### my way of solving this

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)
Fri Sep 28, 2007 2:40 am
Forum: ACM ICPC Archive Board
Topic: problem A ICPC Kanpur Site 2006
Replies: 0
Views: 1904

### problem A ICPC Kanpur Site 2006

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 any ...
Sat Aug 05, 2006 1:23 pm
Forum: Volume 2 (200-299)
Topic: 216 - Getting in Line
Replies: 57
Views: 25014

### IMHO

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
Tue Nov 22, 2005 1:18 pm
Forum: Algorithms
Topic: help me wid dis
Replies: 2
Views: 1206

### help me wid dis

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?
Sun Mar 13, 2005 6:09 pm
Forum: Volume 102 (10200-10299)
Topic: 10207 - The Unreal Tournament
Replies: 23
Views: 6552

### thank you

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...
Fri Mar 11, 2005 6:04 pm
Forum: Volume 102 (10200-10299)
Topic: 10207 - The Unreal Tournament
Replies: 23
Views: 6552