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