Комментарии
|
-3
can u mail it to me too.my email is shivmitra.mishra@gmail.com
|
|
0
yes but we dont know what those divisors are..so we have to loop through the sqrt(n) values to get to those divisors...so it should be 46000*30*5000=6900000000(unless we find some way in which we can get divisor in O(n^1/3) if its possible then enlighten me :) .. |
|
0
thanx..i got this from wolfram mathworld http://mathworld.wolfram.com/OrderedFactorization.html ..some nice recursive formulas are given there for this thing..
|
|
0
i tried to get a formula for 2 days but could not get..i also think there could be some formula for it so i wasnt tying DP and in the end got AC using DP..but there should exist a formula and that would be a lot cooler way to do this problem..
|
|
0
got it ACed..thanx...i never believed it could work.. i thought we have to work out some formula to get it ACed ..thanx..
|
|
0
but that still is too much for x<2^31 and 5000 such test cases..is their any other way to reduce computation further.
|
|
0
F(1) would not necessarily come d(n)-1 times ..
e.g. F(24)=F(1)+F(2)+F(3)+F(4)+F(6)+F(8)+F(12) =F(1)+F(2)+F(3)+F(1)+F(2)+F(1)+F(2)+F(3)+F(1)+F(2)+F(4)+F(1)+F(2)+F(3)+F(4)+F(6) now when F(4),F(12), F(6) will be expanded the number of times F(1) in the equation would not remain d(n)-1 . |
|
0
what to do after prime factorization ... i had to get F(x)..how does prime factorization helps in finding F(x)..
|
|
0
also space problem is there..
|
|
0
can u elaborate on how to use recursive dynamic with balanced trees??
|
|
0
but the DP would be something like O(n*sqrt(n)) or O(n^4/3)..its too much for input as large as 2^31..
|
|
0
thanks..got it..
|
|
0
n^3 or better..
|
|
0
how to solve it for identical rooks then???
|
|
0
the problem is, in my counting method the same configuration is not counted z! times but it is counted < n! times..but i can not figure out a general formula for the repetitions..
|
|
0
i didnt understood ur approach exactly...can u explain a bit more..
my problem is that i hav to find rmq queries of a segment in log n time and i should be able to change the values of the interval also in log n time... |
|
0
i m doing this-
set<pair<int,int> >s; for(set<pair<int,int> >::iterator it=s.lower_bound(make_pair(x-h,0));it!=s.upper_bound(make_pair(x+h,0));it++) { //processing here; } bt giving me lots of errors... |
|
0
can u explain a bit more abt what is coordinate compression??
|
|
0
thanx...
|
|
0
i got AC in 7.44 sec.. jst took the declaration of map inside the while loop and removed list.clear() statement..
bt the bst solution in this prob is 0.66 sec..hw to achieve time of under 2 sec... thnx in advance... |
|
0
here is the code ..previous one was incorrect.. int main() { map<int,int>list; int t; scanf("%d",&t); while(t--) { list.clear(); int n; scanf("%d",&n); int tmp; VI sum(n+1); list[0]++; int64 ans=0,val; FOR(i,1,n) { scanf("%d",&tmp); sum[i]=tmp+sum[i-1]; val=list[sum[i]-47]; ans+=val; list[sum[i]]++; } printf("%lld\n",ans); } } |
|
0
here is my code tht i chnged a bit still getting TLE
int main() { map<int,int>list; int t; scanf("%d",&t); while(t--) { list.clear(); int n; scanf("%d",&n); int tmp; VI sum(n+1); a.pb(0); list[0]++; int64 ans=0,val; FOR(i,1,n) { scanf("%d",&tmp); sum[i]=tmp+sum[i-1]; val=list[sum[i]-47]; ans+=val; list[sum[i]]++; } printf("%lld\n",ans); } } |
|
0
here is my code tht i changed ...
int main() { map<int,int>list; int t; scanf("%d",&t); while(t--) { list.clear(); int n; scanf("%d",&n); int tmp; VI sum(n+1); a.pb(0); list[0]++; int64 ans=0,val; FOR(i,1,n) { scanf("%d",&tmp); sum[i]=tmp+sum[i-1]; val=list[sum[i]-47]; ans+=val; list[sum[i]]++; } printf("%lld\n",ans); } } this got TLE and AWPRIS's code got AC in 6.13 sec.. as for as i can see their is no reason why i get TLE.. plzz tell why i m getting TLE ... |
|
0
@it4.kp may be i need to sort the blocks using some criteria and thn i can save myself frm chcking all the pairs..am i right??
|
|
0
@cip.cip3ggg i know tht N is very big.bt i thought tht was the only way to do it..
@it4.kp thnks..i'll try to find a new algo..if i fail to tht i'll see ur code..thnks fr the help... |
|
0
very nice tutorial....
|
|
0
thanx buddy...jst hoping some day i can master DP....thnx...
|
|
0
thanx...bt can u explain it a bit abt the recursion relation we get in this(cutting sticks) case....
|
|
0
i thought the problem is well known...i have updated the text...
|
|
0
i was solving problem of cutting sticks frm UVA.....i used some method tht was wasting lot of memory...i came to read tht this problem is exactly similar to the matrix chain multiplication problem bt i cant figure out the similarity between the two....can anyone help....the approach i used was to have all 1<<n subsets as the "states" of DP...obviously its space requirement is tooo high...
thnx in advance...... |