Search found 9 matches
- Sat Dec 13, 2014 9:04 pm
- Forum: Volume 128 (12800-12899)
- Topic: 12836 - Gain Battle Power
- Replies: 3
- Views: 1909
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: 1909
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: 874
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: 1023
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: 1023
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: 12053
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: 1961
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: 1467
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: 6113
Re: 10831 - Gerg’s Cake
Posted an ac code. So deleted.