Search found 17 matches

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

Re: 11592 - Bulb inside a Grid (II)

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

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

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

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

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

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

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

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

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

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

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

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

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

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...
by skinnyguy
Sat Oct 30, 2004 6:37 pm
Forum: Volume 102 (10200-10299)
Topic: 10210 - Romeo and Juliet !
Replies: 8
Views: 5066

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 :D

Go to advanced search