## Search found 9 matches

- Sat Dec 13, 2014 9:04 pm
- Forum: Volume 128 (12800-12899)
- Topic: 12836 - Gain Battle Power
- Replies:
**3** - Views:
**1538**

### Re: 12836 - Gain Battle Power

Yes, now I know for sure, this is not greedy. And to optimize the dp complexity, you need Knuth optimization(may be quadrangle inequality)

- Sun Nov 30, 2014 10:10 pm
- Forum: Volume 128 (12800-12899)
- Topic: 12836 - Gain Battle Power
- Replies:
**3** - Views:
**1538**

### Re: 12836 - Gain Battle Power

I think this is a dp problem. Though the straight-forward dp is n^3, it requires a n^2 version to get accepted. I haven't got accepted yet, though. But greedy should be incorrect. I don't have any cases right now, may be someone else will post some.

- Tue Nov 11, 2014 9:36 am
- Forum: Volume 128 (12800-12899)
- Topic: 12808 - Banning Balconing
- Replies:
**1** - Views:
**780**

### Re: 12808 - Banning Balconing

Can I have some I/O for this problem?

- Thu Mar 06, 2014 12:19 pm
- Forum: Volume 126 (12600-12699)
- Topic: 12653 - Buses
- Replies:
**4** - Views:
**906**

### Re: Problem 12653(Bus Coloring)

Actually I made too silly a mistake. In the power function, I took the argument as power(Matrix M, int n) but n can be long long. This caused a loop in the function and hence the TLE.

- Thu Dec 26, 2013 6:49 pm
- Forum: Volume 126 (12600-12699)
- Topic: 12653 - Buses
- Replies:
**4** - Views:
**906**

### 12653 - Buses

I am getting TLE in this problem. My solution has complexity log(n). But it still gets TLE. I would like some I/O. Though I have tested my program myself for some large inputs near 10^15. I am not posting the code at this stage. At last accepted. I did a funny mistake. In the function of Matrix expo...

- Fri Nov 30, 2012 5:00 pm
- Forum: Volume 118 (11800-11899)
- Topic: 11889 - Benefit
- Replies:
**27** - Views:
**11026**

### Re: 11889 - Benefit

Can anyone explain me about the problem? You are given a, c, you have to find the minimum b such that Lcm(a,b)=c. So c must be divisible by a, otherwise there is no such b. Now, for a prime p dividing a or b, Lcm(a,b)= product of p^{max(e1, e2)} where e1=power of p in prime factorization of a, e2 =...

- Fri Nov 30, 2012 4:43 pm
- Forum: Volume 124 (12400-12499)
- Topic: 12431 - Happy 10/9 Day
- Replies:
**4** - Views:
**1750**

### Re: 12431 - Happy 10/9 Day

There is a solution except matrix exponentiation. Say, you want to find d*(1+b+b^2+b^3+b^4)%M. What can you do? You don't need d at first. Let f(b,n,M) gives you the remainder. We can write it as 1+b+b^2+b^3+b^4=1+b+b^2(1+b)+b^4=(1+b)*(1+b^2)+b^4 f(b,n,m)=f(b,n/2,m)*(1+b^{n/2})+b^n if n even and f(b...

- Fri Nov 30, 2012 4:34 pm
- Forum: Volume 124 (12400-12499)
- Topic: 12499 - I am Dumb 3
- Replies:
**3** - Views:
**1305**

### Re: 12499 - I am dumb 3

easy if you know something related to nim. Like bogus nim or staircase nim. But you have to sense it properly.

- Fri Nov 30, 2012 4:32 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10831 - Gerg's Cake
- Replies:
**13** - Views:
**5540**

### Re: 10831 - Gerg’s Cake

Posted an ac code. So deleted.