## 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:
**2332**

### 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:
**1942**

### 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:
**804**

### 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:
**1942**

### 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:
**1942**

### 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:
**1942**

### 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:
**15346**

### 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..

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:
**15346**

### 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.

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:
**1905**

### 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)

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:
**1801**

### 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:
**24335**

### 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:
**1168**

### 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?

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:
**6265**

### 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...

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:
**6265**

### 10207... please 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 sa...

- Sat Oct 30, 2004 6:37 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10210 - Romeo and Juliet !
- Replies:
**8** - Views:
**4995**