Show all threads Hide all threads Show all messages Hide all messages |
WA 19 | Lightless [Samara SAU] | 1963. Kite | 24 Feb 2018 01:28 | 1 |
WA 19 Lightless [Samara SAU] 24 Feb 2018 01:28 |
Why I get a TLE #6 ? | Yang Tianyi | 1018. Binary Apple Tree | 23 Feb 2018 06:47 | 4 |
Just like what I have said,I got a TLE and execution time is 1.029. Who can help me? Now I get an AC Just change "if(!y)" into "if(!y||!x)" |
About TLE and Recursion | † Ленин † [Yaroslavl SU] | 1018. Binary Apple Tree | 23 Feb 2018 06:45 | 5 |
I got TL#6. After that just a little bit updated my solution: int max( int pos, int len ) { ..if ( ch[pos][len] ) ....return dp[pos][len]; --- ....ch[pos][len] = 1; ....dp[pos][len] = res; ....return res; --- } and got AC in 0.015s. Edited by author 23.03.2010 20:30 I get TLE in #6 too , can you explain in detail? Well, I checked my solution and it didn't seem that could exceed the time limit... Weird... I've got TLE #6 too. Can you explain in detail??I'm afraid i can't understand..... oh,now I get AC.Just a little mistakes. |
WA at #1 ?? Try this data... | arena_zp | 1018. Binary Apple Tree | 23 Feb 2018 06:14 | 6 |
6 4 1 2 20 2 5 100 2 3 20 6 3 70 4 1 10 by the way : before you use the dynamic programming on the tree structure, be sure you have build the tree correctly. That's why I got WA. Source Code is available at : ecnu_zp@yahoo.cn I guess this test is incorrect, because of statement: " any biparous branch splits up to exactly two new branches", but node 3 has only one branch. As I can see here is 2 possible trees. 1 and 3 can be root 6 \ 5 3 \ / 4 2 \ / 1 4 \ 5 1 \ / 6 2 \ / 3 Edited by author 20.12.2015 15:47 wrong test case, there will always be zero or two children of any node. |
can anyone explain me how to do it??? | Kirill | 1878. Rubinchik's Cube | 21 Feb 2018 15:08 | 1 |
explain me the way of doing it or give a solution Edited by author 21.02.2018 16:21 |
Test case 2 | Wei Zhang | 2034. Caravans | 20 Feb 2018 22:49 | 1 |
What is the second test case? |
More test cases | azikar24 | 1210. Kind Spirits | 20 Feb 2018 00:09 | 1 |
Make sure your graph is more than 1296 and try these 3 2 1 2 0 1 5 0 * 3 1 8 2 3 0 1 -5 0 2 25 0 * 2 1 8 2 22 3 -15 0 2 19 3 -50 0 ans = -20 =========================== 4 2 1 2 0 1 5 0 * 4 1 8 2 3 0 1 -5 0 2 25 0 1 22 2 -3 0 * 3 1 8 2 22 3 -15 0 2 19 3 -50 0 4 -1 2 -5 0 * 4 1 -8 2 18 0 1 -5 0 2 -19 3 -22 0 1 12 0 ans= -39 ============================== 2 2 1 2 0 1 5 0 * 4 1 8 2 3 0 1 -5 0 2 25 0 1 22 2 -3 0 ans = -3 ========================== 4 2 1 2 0 1 5 0 * 4 1 81 2 23 0 1 56 0 2 25 0 1 22 2 -31 0 * 3 1 8 2 22 3 -15 0 2 19 3 -50 0 4 -1 2 -5 0 * 4 1 82 2 18 0 1 59 0 2 39 3 52 0 1 112 0 ans = -2 |
solution hints | imaginary friend | 1303. Minimal Coverage | 17 Feb 2018 04:30 | 1 |
1) greedy works here, although it's not that much obvious how *correct* greedy should look like 2) 5th test case, that didn't pass for me: 12 -3 10 -2 8 -1 16 0 0 Edited by author 17.02.2018 04:30 |
bugurt & advice | imaginary friend | 2098. Lada Priora | 15 Feb 2018 03:30 | 1 |
the only idea/key take-away of this problem is to properly combine calculation of integer and floating point numbers Edited by author 15.02.2018 03:31 |
Почему не принимать все же верно frePascal 2.6 | Dok32 | 1000. A+B Problem | 14 Feb 2018 23:35 | 3 |
var a,b,c:real; begin read(a,b); writeln(a+b); end. Edited by author 14.02.2018 23:36 Edited by author 14.02.2018 23:36 |
WA6 | Lightless [Samara SAU] | 2089. Experienced coach | 14 Feb 2018 01:02 | 1 |
WA6 Lightless [Samara SAU] 14 Feb 2018 01:02 Try this: 2 2 1 2 1 2 Ans: Yes 1 2 |
How to fix WA 2 | Aditya Paliwal | 2093. All Roads Lead to Snowdrift | 13 Feb 2018 21:09 | 1 |
It is okay to use an edge if the next cleaning for this edge begins at the exact moment when you have crossed the edge. In other words a road is cleaned during the open interval (s_i, f_i). |
No subject | IT | 1617. Flat Spots | 13 Feb 2018 16:03 | 2 |
Edited by author 12.03.2016 20:21 n = int(input()) a = [] summ = 0 for i in range(n): a.append(int(input())) b = list(set(a)) for i in range(len(b)): c=a.count(b[i]) if c > 3: summ+=c//4 print(summ) |
eps | Orient | 1369. Cockroach Race | 13 Feb 2018 15:32 | 4 |
eps Orient 24 Jan 2018 02:03 Epsilon to compare squared distances must be exactly 1.0 / (1 << 24) (at least for M*N algo). Even 23 and 25 leads to WA. (std::numeric_limits< float >::epsilon() / 2) is absolute accuracy needed overall. You can invent twofold float-then-double algorithm to sieve bad points beforehand. For single precision algorithm part you have to use 20.1f (20 + small constant) "epsilon" to compare squared distances in case if you use <= or >= operator (say, vcmpge_oqps or vcmple_oqps instructions) and 28.2f (28 + small constant) in case of strict inequality. Surely you can invent adaptive algorithm to infer relative accuracy needed in particular test case, which takes into account max abs differences of input point coordinates. epsilon should be explicitly specified in the problem statement, it is not hard to make a test to break even simplest O(n*m) double precision solution. I totally agree. The problem should be reformulated in integers or other way to make use of arbitrary precision numbers. Also 10000*100000 is too small dimensionality to encourage participants to make submissions of O((N + M) * log(N + M)) solutions due to high constant factor of latter. Stupid algorithm with randomization and trivial vectorization is faster (and extremely easier to implement) then clever algorithm with Voronoi and point location. |
Why this DP solution doesnt work? | Dmitriy | 1353. Milliard Vasya's Function | 13 Feb 2018 06:22 | 8 |
I thought that this problem is so easy. After many tries to solve that I should say: that is not so easy and I cant solve it! Please, if you DP-master tell me where I'm wrong. So, the state is dp[sum][length] += dp[sum - digit][length - 1], for each digit 0..9. The base is dp[1..9][1] = 1. I've got WA#10: My program for 10 output: 43756 (correct answer: 43749) I can't find a little bug ;( [code] for s := 1; s <= S; s++ { for l := 2; l <= 9; l++ { for d := 0; d < 10 && s - d > 0; d++ { if dp[s - d][l - 1] == 0 { continue } dp[s][l] += dp[s - d][l - 1] if d == 0 { dp[s][l]++ } } } } [/code] You don't need to store previous positions: for (int position = 2; position <= 9; position++) for (int sum = 81; sum > 0; sum--) for (int digit = 1; digit <= 9; digit++) if (sum >= digit) ways[sum] += ways[sum - digit]; because you have to start l at one and eliminate continue and s - d >= 0 No. You are wrong here. I've found my error, it was a dp base. Thx for all. Guys, what are you doing in New Year? Hahaha |
Wrong Answer || Compiler: GCC 7.1 | Meraj al Maksud | 1409. Two Gangsters | 13 Feb 2018 04:59 | 3 |
I don't understand what's wrong with my code. Help me pls. Thnx in advance. #include<stdio.h> int main(){ int L, H; scanf("%d%d", &L, &H); printf("%d %d ", 10 - L, 10 - H); return 0; } It said not more than 10 cans... thus there could be less than 10 cans Once Harry and Larry shoot a common can... you gotta consider that too... |
What is in 4 test? | Ilya | 1875. Angry Birds | 13 Feb 2018 02:19 | 1 |
|
WA 5...Please give some tests..Thx~ | Scau_Ly | 1508. Japanese Puzzle | 11 Feb 2018 18:38 | 2 |
I use Dynamic Programming..and i made several tests myself, my code could calculate the right answer = =...sorry for my poor English Simple tests: 1) 5 2 2 2 ????? ans:XX.XX 2) 4 2 2 2 ???? ans:Impossible 3) 15 3 2 1 2 ??X?.?.......X? ans:.?X?.X.......XX 4) 15 5 2 1 2 1 2 ??X?.?.X.?.?.X? ans:Impossible 5) 5 0 XXXXX ans:Impossible 6) 5 3 1 1 1 X.X.X ans:X.X.X 7) 5 2 1 1 .?.?. ans:.X.X. 8) 18 5 3 1 1 3 1 .???.X?.??..?XX?.? ans:.XXX.X..??..?XX?.X |
asm tips | Orient | 1369. Cockroach Race | 11 Feb 2018 13:26 | 2 |
Make two separate arrays for x and y coordinates of cockroaches. Don't use horizontal instructions in tight loops. Perform all the develop and debug in 32-bit mode (evidently GCC/Clang on server has -m32 key). x86-64 has RIP-relative addressing, there would be bottlneck when you go back to 32-bit build and try to backport from 64-bit one. First loop for each sweet is straitforward. Don't use `displacement(base,index,scale)` addressing. Always run all over the `base` part. Finally it may give about a couple of hundred ms. In second loop for each sweet you may use BSF instruction to get least significant bit offset (remeber, judge runs on Sandy Bridge arch). Use LEA to calculate simple index arithmetic. Here is mine: size_type R = 0; asm ( "vbroadcastsd %[dmin], %%ymm5;" "dloop:" "vcmpgt_oqpd %[d](,%[i],8), %%ymm5, %%ymm6;" "vmovmskpd %%ymm6, %%eax;" "test %%eax, %%eax;" "jz rnext;" "rloop:" "bsf %%eax, %%edx;" "lea 1(%%edx,%[i]), %%edx;" "mov %%edx, %[results](,%[R],4);" "inc %[R];" "lea -1(%%eax), %%edx;" "and %%edx, %%eax;" "jnz rloop;" "rnext:" "add $4, %[i];" "cmp %[M], %[i];" "jl dloop;" : [R]"=b"(R) : [d]"m"(d), [dmin]"m"(dmin), "0"(R), [results]"m"(results), [M]"r"(M), [i]"c"(0) : "cc", "memory", "%eax", "%edx", "%ymm5", "%ymm6" ); Custom IO gives about 300+ ms. I hope M*N solutions finally will loose their ACs someday (at least until hardware will be updated to AVX512-compatible). It turns out, that there are possible two way to solve this problem (both M*N) in addition to naïve one (1400ms). 1.) Read all sites, then for each query point do find all the preliminary neighbours using float coordinates (it is almost two time faster in terms of membory bandwitdth, then if use double). This is a "float" sieve. Then for all sites passed "float" sieve perform similar "double" sieve. It get about 500ms (for me from 1.45s to 950ms). Test #16 is still hardest. Prefetch instructions in long runs gain up to 100ms. First loop (precalc of squared float distances) can be unfolded 4 times by query points (vbroadcastss from fixed memory location works fast in loop, you should not occupy dedicated ymm register for these). Second loop, where squared distances compared against least distance (+ eps of course), found in previous loop, can be unfolded 4 times (you can occupy all 32 bit of some register using bit shift (ror, rol) after vmovmskps). I think it allow to better utilize branch prediction mechanism. This approach can be beaten by simple test: cloud of sites in one corner in 10x10 square and cloud of query points in opposite aslo in 10x10 square both in general position (not matters much). Or wiser: query points placed on quarter of circle with center in one corner and radius of 20000, sites on another quarter of circle with center in the same corner and small radius or vice versa. Or even: two distant strait lines: one with query points and another with sites. 2.) You can solve the problem in single loop using just doubles with randomization. If your random numbers hit right sites, then you can probably make even fastest solution (but it is too improbably). I can't find counterexample for this randomized approach. I am very interested in Progbeat's solution details. It seems (by memory consumed) he used approach very similar to mine. It would be great if we'll exchange our solutions somehow =). |
Как вибирать из двух одинаковых по длине ответов? | Bazeev Damir`~ | 1651. Shortest Subchain | 11 Feb 2018 10:40 | 1 |
17 1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9 1 2 8 9 1 2 3 9 ?????????????????????????????????????? |