Search found 519 matches

by sclo
Mon Mar 24, 2008 2:11 am
Forum: Volume 114 (11400-11499)
Topic: 11429 - Randomness
Replies: 4
Views: 1511

11429 - Randomness

For this problem, how would one find the optimal solution?
Let g = lcm(b1,b2,...,bn).
If R>=g, then the problem is pretty trivial.
I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.
by sclo
Mon Mar 24, 2008 2:05 am
Forum: Volume 114 (11400-11499)
Topic: 11424 - GCD - Extreme (I)
Replies: 25
Views: 6911

Those are different, faster methods for 11424/11426. Hello, Would it be possible to have some hints about your faster method for this problem ? I use sieving to compute the values of the phi function, and sieve as well (as you described above) to compute sum(i=1,n-1, gcd(i,n)) for n=1..N, so my tot...
by sclo
Mon Mar 24, 2008 2:00 am
Forum: Volume 114 (11400-11499)
Topic: 11432 - Busy Programmer
Replies: 12
Views: 4839

f74956227 wrote:I still can't find the recursive relationship...ORZ
Hint: figure out what this line does:

Code: Select all

for(int i=1; i<=d; i++) if(n-i>=0) ret+=f(m,n-i,d,!k);
I'm not saying what are m,n,d, or k, you have to figure it out.
by sclo
Fri Mar 21, 2008 1:16 pm
Forum: Volume 114 (11400-11499)
Topic: 11406 - Best Trap
Replies: 8
Views: 3448

There is no use of N . I first got WA when I considered that the cone has to be strictly inside the room. But later commenting out that part, the code got AC. I still WA!! is there any trick? or maybe my agorithm is wrong? can you give me any hints? THX!! Suppose we don't care about N, then the cir...
by sclo
Wed Mar 19, 2008 9:19 am
Forum: Volume 114 (11400-11499)
Topic: 11420 - Chest of Drawers
Replies: 11
Views: 5036

Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.
by sclo
Mon Mar 17, 2008 10:31 pm
Forum: Volume 114 (11400-11499)
Topic: 11423 - Cache Simulator
Replies: 3
Views: 1547

11423 - Cache Simulator

I keep getting TLE for this problem. I see that some people did it in less than 2 secs. We're given that there are at most 20000 lines, and at most 30 cache simulations, an at most 10^7 data references. For each data reference, my algorithm takes O(1) time (about 12 operations), so I don't see why i...
by sclo
Fri Jan 18, 2008 9:25 am
Forum: Volume 113 (11300-11399)
Topic: 11357 - Ensuring Truth
Replies: 12
Views: 4367

RC's wrote:I got TLE for this problem.
Is there any fast method to solve this problem ?
I use backtracking to determine if it is possible to evaluate the function and if one solution can generate 'TRUE' then i stop the backtrack..
Hint: there is a non-backtracking way to solve this problem
by sclo
Thu Jan 17, 2008 9:38 am
Forum: Volume 113 (11300-11399)
Topic: 11392 - Binary*3 Type Multiple
Replies: 14
Views: 4970

I did similar approach, except it doesn't matter if k is divisible by 3 or not. I basically compute 333...3 mod k for each length
by sclo
Mon Jan 14, 2008 11:39 am
Forum: Volume 113 (11300-11399)
Topic: 11392 - Binary*3 Type Multiple
Replies: 14
Views: 4970

11392 - Binary*3 Type Multiple

I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?
by sclo
Mon Jan 14, 2008 10:53 am
Forum: Volume 113 (11300-11399)
Topic: 11393 - Tri-Isomorphism
Replies: 6
Views: 2745

I'm pretty sure that any graphs with no edges are isomorphic to itself.
by sclo
Fri Jan 04, 2008 12:05 am
Forum: Volume 113 (11300-11399)
Topic: 11374 - Airport Express
Replies: 15
Views: 6667

my idea was to first find the sp from start to all other vertices (say its d0[]) and end to all other vertices( say it is d1[]). then for each edge(u,v) in the commercial express i checked wheather i hav a smaller d0 + w(u,v) + d1[v] lenght(i cheked it for bothe (u,v) and (v,u) ), if a smaller leng...
by sclo
Mon Dec 31, 2007 7:37 am
Forum: Volume 113 (11300-11399)
Topic: 11374 - Airport Express
Replies: 15
Views: 6667

I did an 'exhaustive' bfs for this one with int optimize[501][2]; . - optimize[a][0] means the least cost from source to node a without using any commercial edge and - optimize[a][1] means the least cost from source to node a by using a commercial edge. I had trouble in printing the path since a li...
by sclo
Sat Dec 15, 2007 12:18 pm
Forum: Volume 112 (11200-11299)
Topic: 11234 - Expressions
Replies: 15
Views: 7247

Re: Time Limited Exceeded (TLE)

jjtse wrote:Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?
You are copying string all the time, your algorithm is slow because of that.
by sclo
Sun Dec 09, 2007 9:05 am
Forum: Volume 110 (11000-11099)
Topic: 11091 - How many Knight Placing?
Replies: 5
Views: 2468

Brilliant! Let me try that. But how did you come up with such a good method? Whenever you have to compute something modulo a number, and usual methods are too slow, it's a pretty good hint that matrix multiplications may be the way to do it. So it's pretty much by experience. So the methods I tried...
by sclo
Sat Dec 08, 2007 3:21 am
Forum: Volume 110 (11000-11099)
Topic: 11091 - How many Knight Placing?
Replies: 5
Views: 2468

Hint: you can derive a dp based on all configurations of the leftmost 2 columns.
Once you have derived the dp, you can rewrite the dp in terms of a matrix multiplication. Once you do that, you can use the fast algorithm for computing matrix powers to compute the result.

Go to advanced search