Show all threads Hide all threads Show all messages Hide all messages |
Tips for the question | Myrcella | 1006. Square Frames | 21 Aug 2018 07:51 | 1 |
This problem bothered me a lot. So I decide to write something about it to help other people to solve it more quickly. --------------------------------------------- 1.unsigned char or getchar()(which returns int) must be used to deal with the input --------------------------------------------- 2.When you're testing the program you write, maybe you will find that your PC can't run correct answer(even your code is right)(at least on my local PC... My accepted code always output 0 be cause char such as ┌ is always regarded as two char(s?). So here is how I check my program. ---------------------------------------------------------- This is the original sample: .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. ...........┌─────┐................................ ...........│.....│................................ ....┌──────│.....│..........┌─┐................... ....│......│.....│..........│.│................... ....│......│.....│..........└─┘................... ....│......│....┌│────┐.............┌─┐........... ....│......└─────┘....│.............│.│........... ....│......│....│.....│.............└─┘........... ....│......│....│.....│.........┌──┐.............. ....└──────┘....│.....│.........│..│.............. ................│.....│.........│..│.............. ................└─────┘.........└──┘.............. .................................................. .................................................. And I changed it to the figure below: .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. ...........+,,,,,+................................ ...........*.....*................................ ....+,,,,,,*.....*..........+,+................... ....*......*.....*..........*.*................... ....*......*.....*..........+,+................... ....*......*....+*,,,,+.............+,+........... ....*......+,,,,,+....*.............*.*........... ....*......*....*.....*.............+,+........... ....*......*....*.....*.........+,,+.............. ....+,,,,,,+....*.....*.........*..*.............. ................*.....*.........*..*.............. ................+,,,,,+.........+,,+.............. .................................................. .................................................. In this case my local PC gave the right answer. You just need a little change to make it work (i.e. change the ascii) |
finally accepted (G++ 4.9 C++11) | Serhiy Ivanov | 1915. Titan Ruins: Reconstruction of Bygones | 21 Aug 2018 03:58 | 2 |
This task almost pisses me off. I was finally accepteed after writing my own input/output via fgetc/fputc. Both stream and printf/scanf lead to TLE on test 42. To be onest i still beleive that stream is faster than printf/scanf... But i really wonder which IO uses those guys/girls who accepted with less than 0.2 or something... i don't think it's only about IO. i suppose they used not linked list (or just list in c++), but array with 2 iterators + didn't copy the data when there are already more then n - #of_moves elements in array/list |
Is the 1-st test like explanation test? (+) | bstu_student | 1223. Chernobyl’ Eagle on a Roof | 21 Aug 2018 03:51 | 1 |
Try to check some different algos and take WA1, but answeres for 1-10 and 2-5 is correct. P.S. have AC Edited by author 22.08.2018 03:10 |
'Time limit exceeded' in Python 3.6 | az | 1086. Cryptography | 20 Aug 2018 22:28 | 2 |
It looks like a very simple problem. In pure C, but not in Python! :) 'Time limit exceeded' despite using precomputed tuple of primes (first 100 and each 100th or 50th), Eratosthenes' sieve, optimizations, wheel factorization etc. Time is 2.10-2.30 regardless of method !!! WTF??? On my PC it finds a prime very fast: ----- Enter the number... 14999 14999-th prime number is 163819 Elapsed time is 0.0010540485382080078 ----- On my computer and python implementation (Intel i3, Linux Fedora 27/ CPython 3.6.4) average time per prime is about 1 ms o less. How to solve the problem in this strangely slow Python implementation? Edited by author 10.03.2018 05:38 def prime(n): for i in range(2, n): if n % i == 0: return False return True
k = int(input()) for i in range(k): n = int(input()) count = 0 for f in range(2, 100): if prime(f) == True: count += 1 if count == n: break print(f) I have same problem |
How to read the input? | Myrcella | 1006. Square Frames | 20 Aug 2018 21:08 | 4 |
I found that my program could't deal with ┌┐└┘ correctly. A sample of input is wanted. Please help. Thanks in advance. I haven't solved this problem yet. The table that you see right after "The frame consists of the following characters:" statement tells you how you should read these special characters. I tried to generate the sample input, but not sure if it is correct since these are unprintable characters (atleast with my local PC encoding) and I cannot really verify it. Nevertheless, here is my attempt to generate it. It looks rugged, but that is because of encoding issues. You should probably output it on your own PC with the program below. .................................................. .................................................. .................................................. .................................................. .................................................. .................................................. ...........ÚÄÄÄÄÄ¿................................ ...........³.....³................................ ....ÚÄÄÄÄÄij.....³..........ÚÄ¿................... ....³......³.....³..........³.³................... ....³......³.....³..........ÀÄÙ................... ....³......³....Ú³ÄÄÄÄ¿.............ÚÄ¿........... ....³......ÀÄÄÄÄÄÙ....³.............³.³........... ....³......³....³.....³.............ÀÄÙ........... ....³......³....³.....³.........ÚÄÄ¿.............. ....ÀÄÄÄÄÄÄÙ....³.....³.........³..³.............. ................³.....³.........³..³.............. ................ÀÄÄÄÄÄÙ.........ÀÄÄÙ.............. .................................................. .................................................. and the program that output it. It reads squares as in output sample and draws a board. struct square { int x, y, a; square() = default; square(int x, int y, int a) : x(x), y(y), a(a) {} }; void solve(std::istream &in, std::ostream &out) { std::vector<square> squares; int n; in >> n; for (int i = 0; i < n; ++i) { int x, y, a; in >> x >> y >> a; squares.emplace_back(x, y, a); } unsigned char board[20][50]; for (int i = 0; i < 20; ++i) { for (int j = 0; j < 50; ++j) { board[i][j] = '.'; } } for (square sq : squares) { board[sq.y][sq.x] = 218; // top-left board[sq.y][sq.x + sq.a - 1] = 191; // top-right board[sq.y + sq.a - 1][sq.x] = 192; // bottom-left board[sq.y + sq.a - 1][sq.x + sq.a - 1] = 217; // bottom-right for (int x = sq.x + 1; x < sq.x + sq.a - 1; ++x) { board[sq.y][x] = 196; // top edge board[sq.y + sq.a - 1][x] = 196; // bottom edge } for (int y = sq.y + 1; y < sq.y + sq.a - 1; ++y) { board[y][sq.x] = 179; // left edge board[y][sq.x + sq.a - 1] = 179; // right edge } } for (int i = 0; i < 20; ++i) { for (int j = 0; j < 50; ++j) { out << board[i][j]; } out << '\n'; } } int main() { solve(std::cin, std::cout); } As for reading it. I think you used char, while you need unsigned char or int for this problem. You can use getchar() that returns int or read into unsigned char s[SIZE]
Edited by author 20.08.2018 20:13 Edited by author 20.08.2018 20:13 Edited by author 20.08.2018 20:13 Edited by author 20.08.2018 20:19 Edited by author 20.08.2018 20:26 Edited by author 20.08.2018 20:34 Thank you for such long explaination! I will try it again. The problem is solved successfully. Thank you very much! |
What does "the length of the frame side" mean? | Myrcella | 1006. Square Frames | 20 Aug 2018 19:40 | 7 |
I don't understand it well... As the frame defined by the tripple (X, Y, A) will have such vertices: (X, Y) (X, Y + A - 1) (X + A - 1, Y) (X + A - 1, Y + A - 1) Thank you (for answer my question again)!8D The figure given is very "ugly" so that I didn't realize that it's a square! Edited by author 20.08.2018 17:33 (Maybe we can make a friend OvO. My codeforces id is the same as my id here. Thank you for your kind suggestion, but I am not a big fan of such things. Could you answer my another question please? How to read the input?(The problem has been posted) This has really bothered me a lot... |
Please check this test for me. | Ade | 1903. Unidentified Ships | 20 Aug 2018 16:39 | 4 |
The test lasts 8 sec on my PC. But I got AC in 0.1 sec. I want to know if my PC is too slow or my compiler optimization not working. Thanks, Ade input: first line: 5000 2500 second line is : 1500 "1", 2000 "2", 1500 "3" third line is: 2500 1250 output: 14243163 My AC program also gives this result. I don't think the tests for the problem are very hard. Using Haskell my program solves this in about 0.5 secs but gets an AC in .031 secs (which I think is the lowest time you can get now), so they could definitely make the problems harder. I don't know, my program passes this test in 0.001341s. on my local PC. I got AC in 0.015s. The tests for this program are probably just fine. The Haskell program could be compiled without optimizations or someone has a wooden PC. |
TLE №11. Python 3.4 | Darkness | 1100. Final Standings | 20 Aug 2018 16:27 | 1 |
I really don't know why I cant reach optimal time. It's always more than 1 sec. Here's my code: n = int(input()) data = [[] for k in range(101)] for i in range(n): ID, tasks = map(int, input().split()) data[tasks] += [ID] for i in range(100, -1, -1): for j in data[i]: print(j, i) Meanwhile, I tried to reach time less that 1 sec by not using sorting but as I can see it's not working =( Edited by author 20.08.2018 16:29 |
"Length of the frame side" in output | e05 | 1006. Square Frames | 20 Aug 2018 09:07 | 3 |
Is it height or width of frame? Edited by author 27.05.2015 16:11 |
WA62 | ura | 1593. Square Country. Version 2 | 19 Aug 2018 02:00 | 1 |
WA62 ura 19 Aug 2018 02:00 Do you know what's the test 62? |
My solution in Python 3 took 0.078 seconds and 516 KB with recursion. Can you do it faster? | Dhruv Somani | 1685. Orthography | 18 Aug 2018 18:46 | 2 |
My solution in Python 3 took 0.078 seconds and 516 KB with recursion. Can you do it faster? you can try to to it with stack instead of recursion |
WA7 | alexge50 | 1325. Dirt | 18 Aug 2018 15:24 | 2 |
WA7 alexge50 21 Nov 2015 20:59 Can anybody that had WA7 give me some hints? Thanks Maybe that's because you didn't calculate the right shortest-path with the least boots changed(that is, your first number of the output is wrong, but the other one is right). I've got WA7 because I used only one bfs to calculate both values. 2 bfs should be used. (BTW, some of my classmates said only one bfs could also work??? I'm not sure about this. |
help me with case 8 | iakwal | 1514. National Park | 18 Aug 2018 14:30 | 1 |
what is case 8 like,i just can't solve it with divede and conquer... |
Can anybody tell me the algorithm to solve this question? | Myrcella | 1013. K-based Numbers. Version 3 | 18 Aug 2018 13:05 | 4 |
I have solved 1009&1012 using dp. My algorithm is O(n). Obviously it can't pass this problem's test. I think maybe there are some ways to make it quicker but I can't figure out. When I was searching in internet for solutions, I found that they are all for 1012. I'm a Junior high school students and my math is poor (for this question) TAT. Can anybody help me?? THx in advance. You should try to look up on the Internet how to find Fibonacci number with matrix exponentiation. The level of material should be accessible to a high school student if you are willing to spend couple of hours getting comfortable with new notations/definitions. There's not much theory behind this. You also need to know how to do fast exponentiation (i.e. in O(lon n) instead of O(n)) and use Long arithmetics (like BigInteger in Java). Thanks! Luckily I have known about knoledge about quickpow. Very helpful segguestion!XD Thank you again. I think I gain a lot after solving this question! I nearly knew nothing about matrix in the past. |
I have WA#1!!! | {AESC USU} Evgeny Kurpilyanskij | 1171. Lost in Space | 18 Aug 2018 07:11 | 2 |
My program passed sample But I HAVE WA#1! My output: 8.6000 4 EDWS Please give me some hint! Edited by author 17.05.2007 19:32 My program passed sample But I HAVE WA#1! Don't know if still relevant =), but the first test is different from sample. It's a single-level test. Edited by author 18.08.2018 08:24 |
Xn+1==(sqrt(5*Xn*Xn+4*(-1)^n)+Xn)/2 | Shen Yang | 2079. Memory leaks | 17 Aug 2018 21:26 | 5 |
first for bound=1e5,using matirx power to compute x0,x1 x[bound],x[bound+1] ,x[2*bound],x[2*bound+1]..... upper bound is 2*p using map to record (x[i*bound],x[i*bound+1]) I use this formula and discrete log algo to find candidate of xn+1 then continue to compute xn-1 xn-2 .... until we find (xi,xi+1) in the map then it is valid otherwise it is invalid complex : sqrt(p*log(p)) Edited by author 02.12.2017 15:17 Could you do me a favor to explain the meaning of this problem? My teammates and me are working on this but we can hardly get the point. Thx for helping anyway. p.s. Chinese would be better XD 给定 斐波那契 的某一项 %p的值x,求它的下一项 %p的所有可能值 |
TL 57 give me some hard test data | Vitalii Arbuzov | 1589. Sokoban | 17 Aug 2018 14:59 | 6 |
Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine. Can anyone give test cases that he consider to be hard. Thanks! I've found one test that takes about 20 seconds to process. It looks quite simple but for my greedy approach it's real hell ######## #......# #------# #*****-# #------# #$$$$$$# #-----@# ######## Now it takes about 3 seconds to process this test but still TL 57-62... Other not bad test: ######## #.....-# #--##--# #-*----# #--#-#-# #$$$$$$# #-----+# ######## Edited by author 01.05.2011 00:06 Edited by author 01.05.2011 02:34 It looks hardly possible to pass this problem in Java. I have really good solution but depending on configuration I always get TL 56,57 or 62. Maybe I've missed cool truncation? I store situation in one long variable in bit representation. In this case it's easy to check if all blocks are on their places (just do binary &) Also I use 3 different heuristics to filter deadlock situations (Block with unreachable destination, stuck block not on destination, strongly connected area without man inside and with amount of blocks greater then amount of destinations) Also I use priority queue and process turns wich moves blocks closer to closest unblocked destination than it was in previous turn. I turn off heuristics automatically if they are not effective in current situation. (it looks effective on some tests but it doesn't actually help to pass 62 :D ) I'm pretty sure that even simpler C++ solution can pass all tests. Java, Java, why you are so slow?... Time limit is too strict. Admins, is it good idea to add this problem to list of problems that one can have problem with using Java? Guys... If you have good ideas of how to improve don't hesitate to write them here. Thanks, Vitaliy Edited by author 01.05.2011 02:31 My method needs a plenty of memory to store information, although got a Memory Limit Exceeds, but it can give out a solution to all the hard data in discuss in less than 0.1s. however, I still found some data that make my program run very slow(up to 2s), and even can not provide a solution(the solution exists). ######## #.O....# #####OO# #.@$OO$# #$O$O$O# #OO$O$O# #.$OOO.# ######## ######## #.O.O..# #####OO# #.@$OO$# #$O$O$O# #OO$O$O# #.$OO..# ######## ######## #......# #.OOO$@# #.O$OO$# #$O$O$O# #O$$O$O# #.$OOO.# ######## ######## #......# #.OOO$O# #.@$OO$# #$O$O$O# #O$$O$O# #.$OOO.# ######## can any one who passed this problem share some more outstanding ideas about how to optimize the algorithm? Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine. Can anyone give test cases that he consider to be hard. Thanks! ###### ## . # # * # # # .$ # # #$## ## @ # ##### my personal favorites: ######## ##.* $.# # * . # # *. # ## $.$ # # $*$$$# #.. @# ######## and next is hard only if you don't use any estimate func: ######## #. # #$ $ $ # #@ $ $ # # $ $ # # ****# #......# ######## Edited by author 17.08.2018 15:25 |
strange recursion | Gleb | 1152. False Mirrors | 17 Aug 2018 12:04 | 1 |
Recursion solution - tl5, recursion with non-asymptotic optimization - ac 0.046 |
Some hints and wa17 | Gleb | 1748. The Most Complex Number | 16 Aug 2018 18:45 | 1 |
I precalculated this numbers by algo like bfs, the last most complex numbers have 92160, 96768, 98304, 103680 divisors. Wa17 - max test. I have wa17 because of wrong right border in binary search. Check your program, may be it hepls you. Also you can visit https://oeis.org/A002182 |
Why WA#4 C++ | Burdin Artyom`~ | 1601. AntiCAPS | 16 Aug 2018 18:07 | 2 |
#include <bits/stdc++.h> using namespace std; int main() { string s; int pe = 0; while(getline(cin, s)) { for (int i = 0; i < s.length(); i++) { if (s[i] == '.' || s[i] == '!' || s[i] == '?' || (s[i] == '-' && i )) { pe = 0; } if ((s[i] - '0' + '0' >= 65 && s[i] - '0' + '0' <= 90) && pe != 0) { s[i] = s[i] - '0' + 32 + '0'; } if (pe == 0 && s[i] != ' ' && s[i] != '.' && s[i] != '!' && s[i] != '?' && s[i] != '-') { if (s[i] - '0' + '0' > 90) { s[i] = s[i] - '0' - 32 + '0'; } pe = 1; } } cout << s << '\n'; } } Edited by author 16.08.2018 18:05 Edited by author 16.08.2018 18:05 Ohhhhh..... I find my wrong... -HI - HI WA: -Hi - Hi AC: -Hi - hi |