| Show all threads Hide all threads Show all messages Hide all messages |
| care about -0.0 | eycia | 1942. Attack at the Orbit | 29 Jun 2026 18:05 | 2 |
Sure (on input) WA3 was due to that |
| Little question | 2rf | 1479. Scheduled Checking | 29 Jun 2026 14:20 | 4 |
If the test is: 4 6 1 2 1 3 1 4 2 3 2 4 3 4 then all created routes are as follows: 1 - 2 - 3 - 1 1 - 2 - 4 - 1 1 - 3 - 4 - 1 2 - 3 - 4 - 2 1 - 2 - 3 - 4 - 1 1 - 2 - 4 - 3 - 1 1 - 3 - 2 - 4 - 1 Am I right? Indeed I was right, the answer for this test is 6. Can this problem be solved faster than in O(2^n * n^3)? (LLM-written response, always verify) You can improve the usual DP by one n. Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree: max(longest cycle length, max_v number of simple cycles containing v) Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last. Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2. This gives O(n^2 * 2^n) time and O(n * 2^n) memory. Edited by author 29.06.2026 14:21 |
| Fractional part detection | bsu.mmf.team | 1942. Attack at the Orbit | 29 Jun 2026 12:46 | 5 |
I used this code: double x, y; cin >> x >> y; x *= 1000; y *= 1000; int X = (int)x, Y = (int)y; But this code doesn't work properly. For example, if x = -1.001, then X will be -1000 (in some cases one unit is lost). How to avoid this in C++? To solve this problem I had to read whole string and then parse it :) My method got AC: cin >> a; A = (int)(a*1000.000001); I use (g++11) double a; scanf("%lf",&a); p[j] = (int(a*1000.000001) + 100000) % 1000; "a*1000" gives WA "cin >> a" gives TL45 even with "cin.sync_with_stdio(false)" Edited by author 29.06.2026 18:03 This task use some architectural float issues. So we need minimize to use real numbers. I try many times, but get AC only with manual parsing: x,y = sys.stdin.readline().strip().split() xs,ys = x.split('.'), y.split('.') x = int(xs[1]), y = int(ys[1]) if xs[0][0]=='-': x=-x if ys[0][0]=='-': y=-y I use float number only one time - in last line, in sqrt. |
| Unclear problem statement | Denis Koshman | 1542. Autocompletion | 29 Jun 2026 06:35 | 4 |
1) What should be output when there are no words starting with input string? 2 successive empty lines in the output are weird, so I ask. 2) If input contains some word exactly as it is, should I place this word in the output? I.e. does the verb "start" allow equality as well? Ok, my AC solution treats equal strings as starting and it will output two blank lines in case of empty result between two non-empty ones. What about ten empty results between two non-empty ones? |
| somebody tell me the algorithm please | Irakli Khomeriki | 1479. Scheduled Checking | 29 Jun 2026 05:04 | 2 |
|
| Test | Igor Parfenov | 1429. Biscuits | 28 Jun 2026 15:47 | 1 |
Test Igor Parfenov 28 Jun 2026 15:47 It turned out, that totally incorrect implementation can pass all previous tests in discussions. Input 3 0 0 5 10 0 5 2 4 5 Output 6 Edited by author 08.07.2026 19:22 |
| easy bfs | 👑TIMOFEY👑`~ | 2029. Towers of Hanoi Strike Back | 28 Jun 2026 10:59 | 2 |
just read some titles abot hanoi tower and learn some algorithm like floyd and u 100% will can solve this problem no need for BFS, simple O(N) cpu, O(1) ram solution |
| number size is more then 64 bit | Anushavan | 1309. Dispute | 28 Jun 2026 08:10 | 3 |
If I enter for example 150000 I get overflow , (y-1)x^5 passes limitation of any type. Do I need to create new type to keep ((10^8)^5)size value ? Or anything else I have to do with values, expression? I solved it with that g-function. int g(int x, int y, long long m=9973){ long long lx=x, ly=y, lx2=(lx*lx)%m, lx3=(lx*lx2)%m, lx5=(lx2*lx3)%m; return ( ((ly-1)*lx5)%m + lx3 - (lx*ly)%m + (3*lx)%m + (7*ly)%m) % m; } You don't need long long if all inputs are within 9973 |
| WA 29!!! | Lebedev_Nicolay[Ivanovo SPU] | 1463. Happiness to People! | 28 Jun 2026 07:54 | 6 |
WA 29!!! Lebedev_Nicolay[Ivanovo SPU] 29 Apr 2009 22:36 Can anybody give me test for WA #29??? Will anybody answer my question??? Will anybody answer my question??? Maybe in year or two. Forum is not for instant answers. It is rather knowledge base. There is no answer to your question in the base yet. Maybe answer will appear but 99% that _you_ will first find the bug and post yourself test for the bug here than someone get wa29 and post test for it. At last, I've solved it)))) If you have WA29 try this test: 8 6 1 2 5 4 1 2 1 6 1 2 1 2 3 1 2 4 1 5 6 1 6 7 1 6 8 1 Answer is : 13 3 3 2 4 Edited by author 28.06.2026 08:01 |
| Broken problem | Igor Parfenov | 1144. The Emperor's Riddle | 26 Jun 2026 20:31 | 1 |
I suspect (but still not sure) that this problem is not solvable, and you have to implement the same incorrect solution, as author did. |
| To Admins: test #14 | Dmi3Molodov | 1806. Mobile Telegraphs | 26 Jun 2026 14:19 | 1 |
do not use many nodes if there is no path between them! PLEASE... It is necessary to compare the speeds of algorithms for finding an existing path, rather than the speeds of algorithms for finding the fact that there is no path. P.S. And the computing capabilities of the russian Anka are simply amazing! :-) |
| Non-precise solution is required (incorrect statement) | Igor Parfenov | 1509. Domino Recognition | 26 Jun 2026 03:10 | 2 |
It is not written in the statement explicitly, but the solution has to be non-precise. The epsilon can be determined only by random submissions. It is possible to solve the problem 100% precisely, using only integers, but it will give WA 4. Thank you! I used EPS = 1e-2 and got WA #49 I used EPS = 1e-3 and got AC There is this sentence in the problem statement: "The coordinates are accurate to 0.0001." This makes me think EPS should be larger than 1e-4. How much larger? Hard to tell without submitting. Also, this sentence makes me think that the coordinates are not precise, therefore a solution using only integers would be expected to fail. One more thing: Since it's guaranteed that at least one solution always exists, I believe the only case where EPS = 1e-2 / EPS = 1e-3 can make a difference is the N = 2 case. |
| Question | Igor Parfenov | 2061. OEIS A216264 | 25 Jun 2026 15:11 | 1 |
Question Igor Parfenov 25 Jun 2026 15:11 Where can I exchange those 3332 Rubicoins I have been mining for 6 hours 20 minutes? Hint: don't forget to use multiple CPU cores and compile with optimizations. |
| Smallest possible automaton | Yury_Semenov | 1999. The secret module | 25 Jun 2026 14:50 | 2 |
My solution produces an automaton with 2n^2 + n states, but what is the smallest possible size? Is it still ~n^2? Edited by author 14.02.2024 16:19 My solution produces an automaton with exactly 2n^2 + 1 states. Can it be done better? I don't know, but if I had to guess, I would say no. However, for a particular input automaton, some of the states of the output automaton may be unaccessible, thus they could be removed and the problem could be solved with even fewer states. But, there are input automatons where all the states of the output automaton are accessible, thus the upper limit of my solution is 2n^2 + 1 states on the worst case. |
| WA7 | rohit | 1254. Die Hard | 24 Jun 2026 11:33 | 4 |
WA7 rohit 12 Apr 2011 03:18 What's special in test 7 ? I tried all the tests given here and I get right answer. My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same. Anything wrong with my method ? Re: WA7 Erop [USU] 2 May 2011 22:47 may be some problems with precision? Re: WA7 Velea Alex 26 Aug 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(n*m*k) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. ) with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :( my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : ) i will keep in touch with this thread :-S I tried it this way - i.e. propagate all with 1, then with sqrt(2) from current frontier to upcoming edges, but here is the thing: distance 0 leads to 1 and 1.4 (all still fine and sorted) distance 1 leads to 2 and 2.4 (all still fine and sorted) distance 1.4 leads to 2.4 and 2.8 (all still fine and sorted) distance 2 leads to 3 and 3.4 (all still fine and sorted) distance 2.4 leads to 3.4 and 3.8 (all still fine and sorted) distance 2.8 leads to 3.0 and 4.2 (WOOPS! - 3.0 will be placed after 3.4 and 3.8) so I did Dijkstra, but with super-optimization. Instead keeping all nodes in a heap, I kept a heap on unique distances (as of A+B*sqrt(2)), and for each such distance I kept bidirectional list of nodes with that distance as currently reached. This makes edge relaxation O(1) - remove from current list, and add to another. So it's O(N*M)+O(K*log(K)) where K is number of different distances, and there are not so much on the way. Although I checked with asserts, there are cases when you have like 8 or even 16 upcoming frontiers even during first 6 tests. Relexations start happening with test 5, but only test 7 leads to WA on them with too greedy approach. Edited by author 24.06.2026 11:43 |
| First test is correct? | coder | 2188. They are charging the cannon... WHY?! | 24 Jun 2026 11:16 | 1 |
Why for D = 8 answer is 10? Why 9 is not answer ? indexes : 0 1 2 3 4 5 6 7 8 9 10 prefix-sum of a[1..10]: 0 7 11 18 18 23 29 33 37 42 46 prefix-sum of b[1..10]: 0 5 8 13 14 16 19 22 29 31 31 diff : 0 2 3 5 4 7 10 11 8 11 15 t = 9, diff 11, t = 10 diff = 15 and minimum t which diff >8 is 9. |
| WA 33. What is this wrong? | Vsevolod Kondrashin | 1820. Ural Steaks | 23 Jun 2026 16:43 | 2 |
a,b=map(int, input().split()) if a==1: print(2) exit() if (a*2)//b<a*2/b: print(a*2//b+1) else: print(a*2//b) Edited by author 23.06.2026 16:44 |
| wa 22 and then mysteriously AC: don't know why? | Radi Muhammad Reza | 1325. Dirt | 23 Jun 2026 12:17 | 3 |
when trying to update from (ux,uy) to (vx,vy) i was checking if (vx,vy) was already popped from priority_queue. this got me wa 22 many times. later, just out of frustation i removed the check and let (vx,vy) be updated even after it was once popped. and u know what, mysteriously got AC. of course, there has to be some logical explanation behind that. please explain anyone? Thanks in advance. I followed by your advice, and also suprised! Consider this test 4 5 1 1 4 5 11111 22221 21111 22222 You may get caught by situation that '2' at (3,1) gets way longer walking path from '1' at (3,2) than from '2' at (2,1). I remedied this by traversing both fronts in parallel, so it's still O(N*M) BFS w/o heaps or sorting. Edited by author 23.06.2026 21:29 |
| A test | Sergei Barannikov | 2109. Tourism on Mars | 23 Jun 2026 10:16 | 2 |
A test Sergei Barannikov 12 Jun 2020 04:25 4 1 3 1 4 2 4 1 2 4 The correct answer is 1. Thanks :) Forgot to traverse ALL cities between L and R |
| very easy problem if think right | coder | 2195. Binary Trees | 22 Jun 2026 18:49 | 1 |
Hint: convert first tree some middle special case tree , and from this make isomorph to target tree. |