Common Board| Show all threads Hide all threads Show all messages Hide all messages | | eps:: 1e-5 is AC, 1e-9 WA... | Shen Yang | 1853. Laser Technologies | 28 Feb 2017 15:57 | 3 | what's the principle of the solution? i've tried to construct laser-lines one after another with the smallest distance, and then to find dots of intersections line[i] and line[i+1], then find intersection of line[i+1] and line[i+2] and after that find the distance between dot[1] and dot[2], dot[2] and dot[3] and so on. But that's a big problem: line[i] can intersect line[i+1] in dot[1], that can later occur outside of the figure, formed with intersects of line[i+1000] and line[i+1001]. What's the solution? you can try to find intersection point of lines x1,y1, x2,y2 x1+dt*cos(theta1),y1+dt*sin(theta1),x2+dt*cos(theta2), y2+dt*sin(theta2) x1=fx1+t*cos(theta1),y1=fy1+t*sin(theta1) x2=fx2+t*cos(theta2),y2=fy2+t*sin(theta2) point (fx1,fy1) and (fx2,fy2) is the point on the convex polygon you can the intersection point x(t),y(t) by limit dt--->0 then length of args is sqrt((dx/dt)^+(dy/dt)^2) dt ,you can find the Primitive function of sqrt((dx/dt)^+(dy/dt)^2) and compute the integral by O(1) | | Different approaches to solve the task | mberdyshev | 1330. Intervals | 28 Feb 2017 05:09 | 1 | 1. Segment tree. 2. Fenwick tree. 3. Partial sums (b[i] = SUM(a[0], ..., a[i])). 4. Sqrt decomposition. Hope, it helps to understand how to solve this task. Edited by author 28.02.2017 15:25 | | Different approaches to solve the task | mberdyshev | 1126. Magnetic Storms | 28 Feb 2017 04:54 | 1 | 1. Modification of a deque, which allows to find a min element in O(1). 2. Segment tree. 3. Min/max heap (was too slow for me). 4. Sparse table. 5. Sqrt decomposition. Hope, it helps to understand how to solve this task. Edited by author 28.02.2017 15:25 | | ugly algo: | Shen Yang | 1363. Halftones | 27 Feb 2017 07:26 | 1 | first using Heuristic search, a[x][y]<255-a[x][y] first search 0, else first serach 255, times>1e5 break; if ok==false using random search, if(rand()%2==0) first search 0 else first search 1, if you use rand()%2==1 first search 0 it will tle... | | problem with w7 | mhg | 1017. Staircases | 26 Feb 2017 20:10 | 3 | for accepting you should consider something like long long int as input and ... but w7 is something different can anybody help for this... I got WA #7 as well.. not sure what went wrong anyone has the input n and expected output? Thanks Ok, I figured it out. Internal cache values should be long long for storing large count. For n = 500 answer = 732986521245023 | | Probably weak tests | Sirko | 1452. Pascal vs. C++ | 25 Feb 2017 08:03 | 1 | My AC solution runs about 10 seconds for test case 1, 2, ...., 2000 on my laptop (it's an old one, though, maybe that's the reason). | | WA 12 | Sirko | 1513. Lemon Tale | 23 Feb 2017 15:51 | 2 | WA 12 Sirko 23 Feb 2017 14:25 Could anyone give a hint about Test 12? What does it look like? Some possible overflow, etc. My program returns correct answer on 10000 10000 test. @Admins, can you please provide me with JUST an answer for this test? If so, my e-mail: dostoyevsky_at_ukr.net. Thanks a lot. Got AC. Made a mistake in printing long number — need no print leading zeros for non-top parts of number | | WA16 pascal | GruzdevaDaria`~ | 1893. A380 | 23 Feb 2017 14:59 | 1 | whats wrong? program fly; const okn='window'; ser='neither'; proh='aisle'; var i,r,n,bb:integer; s,s1:string; m:char; begin readln(s); n:=length(s); m:=s[n]; s1:=s; delete(s1,n,1); val(s1,r,bb); if r<3 then if (m='A') or (m='D') then writeln(okn) else writeln(proh) else if r<21 then if (m='A') or (m='F') then writeln(okn) else writeln(proh) else if r<65 then if (m='A') or (m='K') then writeln(okn) else if (m='C') or (m='D') or (m='G') or (m='H') then writeln(proh) else writeln(ser); end. | | WA #12 | anisca22 | 1611. Decimation | 22 Feb 2017 23:51 | 1 | WA #12 anisca22 22 Feb 2017 23:51 Give me a test or something... | | Вопрос о значении теста | XI | | 22 Feb 2017 21:20 | 1 | За что отвечает тест 5? Задача 1005 "Куча камней" никак его не пропускает Edited by author 22.02.2017 21:21 | | Tests request | Al.Cash | 2076. Vasiana | 22 Feb 2017 17:22 | 3 | I'm stuck at WA2 and would really appreciate some good test, at least for the case of a rotated parabola. I think giving only one really easy sample is a bad tone in this kind of problems. this is not a hard problem ,but how to deal with so huge numbers up to 1e20 without precision error?? | | What 's on Test 2? Help me plz | quangduytr | 1726. Visits | 22 Feb 2017 07:54 | 1 | #include <bits/stdc++.h> using namespace std; struct duy{ long long x,y; }; duy a[100005]; bool cmp1(duy a, duy b){ return a.x>b.x; } bool cmp2(duy a, duy b){ return a.y>b.y; } long long n,dem=0,t=-99,s[100005][2],duoi[100005],res=0; double q; int main() { cin>>n; for(long long i=1; i<=n; i++) cin>>a[i].x>>a[i].y; sort(a+1,a+n+1,cmp1); for(long long i=1; i<=n; i++){ if(a[i].x==t) s[dem][2]++; else{ dem++; s[dem][1]=a[i].x; s[dem][2]=1; t=a[i].x; } } duoi[dem]=0; for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2]; for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]); sort(a+1,a+n+1,cmp2); dem=0; for(long long i=1; i<=n; i++){ if(a[i].y==t) s[dem][2]++; else{ dem++; s[dem][1]=a[i].y; s[dem][2]=1; t=a[i].y; } } duoi[dem]=0; for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2]; for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]); q=((double)((double)2*(double)res))/((double)((double)n*(double)(n-1))); cout<<roundf(q*1)/1; } | | help me\ PASCAL wrong answer test:2 | Олександр | 1001. Reverse Root | 21 Feb 2017 14:22 | 2 | var b:array[1..4] of int64; i:integer; begin for i:=1 to 4 do read(b[i]); for i:=4 downto 1 do writeln(sqrt(b[i]):0:4); end. You think there are 4 and only 4 numbers in the input. Could you quote task fragment declaring it? Edited by author 21.02.2017 14:22 | | TLE #21 | Najmaddin Akhundov | 1510. Order | 20 Feb 2017 21:00 | 5 | TLE #21 Najmaddin Akhundov 12 Dec 2014 12:56 I got TLE, but when i used Visual C++ 2010 I hot AC. It worked for me, I hope it will work also for you Thank you so much for the tip. Worked fine for me as well. Task is compiler-independent. Here are successful GCC runs in my recent successful runs: 7147656, 0.249 sec - using printf/scanf; 7147682, 0.28 sec - using IO streams and std::ios_base::sync_with_stdio(false). I also had the same mistake, use "ios_base::sync_with_stdio(false);" and get AC | | few tests | Михаил Аршинов | 1122. Game | 19 Feb 2017 08:17 | 2 | WBBB BBBW WBWB BBBB 101 010 101 2 BBBB BBWW BBBB WWBW 010 111 010 3 can you explain your examples | | WA #5 | Accepted | 1306. Sequence Median | 18 Feb 2017 20:26 | 4 | WA #5 Accepted 2 Mar 2013 12:05 I use priority queue,the memory that I used is 236 KB,but I still WA at test 5,but I don't know why... You need use unsigned int. could someone tell me why ? Edited by author 18.02.2017 05:40 Edited by author 18.02.2017 05:40 2^31-1 can be stored into signed int. But, when length of input is even, you need to value average, so (probably) add 2 values and receive integer overflow. It doesn't mean you must use unsigned. You can avoid overflow in any other way. | | still TLE | Mehedi Hasan | 1086. Cryptography | 18 Feb 2017 20:16 | 4 | Looks like you re-valuate a[] for every input number. Why? It can be valued once, before "while(t--) {...}" cycle. Formatting is weird a bit. Why? To prevent reading? Looks like you re-valuate status[] for every input number. Why? It can be valued once, before "while(t--) {...}" cycle. What do you think, why this comment is the same with previous one? Have you read previous one? | | TLE with bfs | sukhad | 1119. Metro | 18 Feb 2017 03:53 | 1 | I am using bfs to solve the problem but still getting TLE. Can anyone suugest the cause? | | for those who use graph & recursion approach | Anton | 1119. Metro | 18 Feb 2017 03:51 | 4 | My graph consists of vertexes, which are points, that allow diagonal crossing. Edge (a, b) exists if and only if (a) strictly south-west from (b). Since graph is built, simple dfs easily helps solve the problem ( length of the longest path in the graph - it's diagonal part of result path ). To avoid TLE#10 in this approach, memorization should be used. I know, it's not the best approach, but since constraints are relatively low, it does work. My AC - 0.015 164 КБ. I think, Longest increasing subsequence - is better in general case. how you use longest increasing subsequence in this problem ? To avoid TLE#10 in this approach, memorization should be used. Thanks, it helped me) I added functools.lru_cache() decorator for my Python program and got AC :) Shouldn't we use bfs as we require the shortest path? | | As a fixed time solutions on the server? | BrainBreaker | 1222. Chernobyl’ Eagles | 17 Feb 2017 22:46 | 3 | I got AC. My time is 0.001s (This problem #1222) - Objected-oriented progarmming, call methods, cycles in cycles... But my time of Problem #1000 (A+B) (int + int) - 0.015s Why? :))) Rounding. You can get times of 0.001, 0.015, 0.031, 0.046, 0.062 etc (the step is around 15.5). And, of course, 0.015 wouldn't mean you have exactly that time; it would rather mean that you have somewhere between 0.002 and 0.015. Or around that. Thanks. Possible time interval of 15 ms, I saw a long time ago. Just do not understand, he can not keep within the 1 ms solution like С++: ----------------------------------- #include <iostream> using namespace std; int main() { int a,b; cin>>a>>b; cout<<(a+b)<<"\n"; } ----------------------------------- or Pascal: ----------------------------------- var a,b: integer; begin readln(a,b); writeln(a+b); end. ----------------------------------- I think it should work many times faster than 1 ms. Time spent on the input and output? P.S. Today I passed the task of "1000 A + B Problem" of 0.001s. But usually - 0.015s. :) Hypotesis: The program may start at the beginning or end of the interval timer - and depending on this time will be different. If TLE < 0.014, repeat Submit, while not AC! ))) |
|
|