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.

## Search found 519 matches

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

- Mon Mar 24, 2008 2:05 am
- Forum: Volume 114 (11400-11499)
- Topic: 11424 - GCD - Extreme (I)
- Replies:
**25** - Views:
**7016**

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

- Mon Mar 24, 2008 2:00 am
- Forum: Volume 114 (11400-11499)
- Topic: 11432 - Busy Programmer
- Replies:
**12** - Views:
**4883**

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

Code: Select all

`for(int i=1; i<=d; i++) if(n-i>=0) ret+=f(m,n-i,d,!k);`

- Fri Mar 21, 2008 1:16 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11406 - Best Trap
- Replies:
**8** - Views:
**3474**

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

- Wed Mar 19, 2008 9:19 am
- Forum: Volume 114 (11400-11499)
- Topic: 11420 - Chest of Drawers
- Replies:
**11** - Views:
**5096**

- Mon Mar 17, 2008 10:31 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11423 - Cache Simulator
- Replies:
**3** - Views:
**1578**

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

- Fri Jan 18, 2008 9:25 am
- Forum: Volume 113 (11300-11399)
- Topic: 11357 - Ensuring Truth
- Replies:
**12** - Views:
**4439**

- Thu Jan 17, 2008 9:38 am
- Forum: Volume 113 (11300-11399)
- Topic: 11392 - Binary*3 Type Multiple
- Replies:
**14** - Views:
**5038**

- Mon Jan 14, 2008 11:39 am
- Forum: Volume 113 (11300-11399)
- Topic: 11392 - Binary*3 Type Multiple
- Replies:
**14** - Views:
**5038**

### 11392 - Binary*3 Type Multiple

I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?

- Mon Jan 14, 2008 10:53 am
- Forum: Volume 113 (11300-11399)
- Topic: 11393 - Tri-Isomorphism
- Replies:
**6** - Views:
**2771**

- Fri Jan 04, 2008 12:05 am
- Forum: Volume 113 (11300-11399)
- Topic: 11374 - Airport Express
- Replies:
**15** - Views:
**6808**

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

- Mon Dec 31, 2007 7:37 am
- Forum: Volume 113 (11300-11399)
- Topic: 11374 - Airport Express
- Replies:
**15** - Views:
**6808**

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

- Sat Dec 15, 2007 12:18 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11234 - Expressions
- Replies:
**15** - Views:
**7346**

### Re: Time Limited Exceeded (TLE)

You are copying string all the time, your algorithm is slow because of that.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?

- Sun Dec 09, 2007 9:05 am
- Forum: Volume 110 (11000-11099)
- Topic: 11091 - How many Knight Placing?
- Replies:
**5** - Views:
**2484**

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

- Sat Dec 08, 2007 3:21 am
- Forum: Volume 110 (11000-11099)
- Topic: 11091 - How many Knight Placing?
- Replies:
**5** - Views:
**2484**