| Show all threads Hide all threads Show all messages Hide all messages |
| Colleniars? | coder | 2221. Convex Hull Treap | 17 Jun 2026 22:26 | 2 |
For this test what should be answer?
3
0 0
1 1
2 2
---
1 2 3 or 1 2 2 ? (Answer written by GPT-5.5, verified with AC solution)
The size of a convex hull is not the number of points in the set. According to the statement, if the convex hull is a segment, its size is 2.
For the whole set, the delegate is (2, 2), because it has the greatest ordinate. The convex hull of all three collinear points is just the segment from (0, 0) to (2, 2), so its size is 2.
Then Vadim takes the points to the left of the delegate: (0, 0) and (1, 1). Their delegate is (1, 1), and their convex hull is also a segment, so its size is 2.
Finally, (0, 0) is alone, so its convex hull size is 1.
So in input order the answer is 1 2 2. |
| O(n^2) why TL is so large for this problem? (-) | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 2122. Hamming | 17 Jun 2026 05:04 | 1 |
|
| WA #5 | coders1122 | 1577. E-mail | 17 Jun 2026 02:52 | 6 |
WA #5 coders1122 28 Oct 2010 20:09 see the second sample on your site.
the answer is 2. Any suggestions on improvement of the algorithm i use?
Is my approach wrong or can be fine with some tweaking?
Ravi Kiran. If in your current state s1[i]==s2[j], you should not assume states i+1,j and i,j+1. Only i+1,j+1. Thanks a lot everyone.
I got accepted with the change you suggested. Had similar problem :) This test shows the difference
aba
a
Edited by author 17.06.2026 08:18 |
| How to do this problem using segment trees? | Pushkar Mishra | 1019. Line Painting | 16 Jun 2026 11:53 | 3 |
I understand that we are only concerned with the points mentioned, and not all the points between 1 and 10^9. After forming a segment tree and making all the updates, how can we find the longest white colored segment?
Thank you. It can be solved with heap by sequentially walking on control points to add/remove active segments and tracking the latest one as of input order As for segment tree, I'd track these values
iv: longest white streak on the interval
lv: longest white streak at the begging of the interval
rv: longest white streak at the end of the interval
sv: length of segment
initially iv=lv=rv=s
now
iv = max(iv1, iv2, rv1+lv2)
lv = lv1==s1 ? s1+lv2 : lv1
rv = rv2==s2 ? rv1+s2 : rv2
But it will require lazy propagation similar to 1890 problem during painting which is quite cumbersome. The good side - it would allow "online" algorithm to give answer at every step as paiting proceeds (could be a good upgrade of a problem :)
As for this one - a simpler lazy propagation with states "0" nothing "w" completely white, "b" completely black. Upon final convergion you repeatedly forward them from parent to children while you walk downwards, and after paiting all parental colorings are reverted to "0"
Edited by author 16.06.2026 12:05 |
| The problem is easily solvable without segment tree. | Jorres | 1019. Line Painting | 16 Jun 2026 11:49 | 3 |
Also pay attention to the fact that according to the example - segment is (a;b]. I used this approach and got accepted. (O (N*N) btw :) ) Yes. Compressing coordinates and painting segments straightforwardly is enough. It's also easily solvable with heap at O(N*log(N)) |
| Some tests | 👨🏻💻 Spatarel Dan Constantin | 1840. Victim of Advertising | 16 Jun 2026 10:30 | 1 |
Some tests 👨🏻💻 Spatarel Dan Constantin 16 Jun 2026 10:30 WA #5:
2
-2000 0 -1000 0
0 -1000 0 -2000
> 367.0796326795
WA #7:
2
935 973 -16 438
867 30 196 463
> 1040.9330224527
WA #13:
2
0 7 0 8
6 10 6 1
> 12.7006778631 |
| WA 7 | Yegor | 1890. Money out of Thin Air | 16 Jun 2026 10:26 | 3 |
WA 7 Yegor 19 Dec 2011 03:58 What can cause a "wrong answer" in 7-th test? I used sqrt_decompostion and always get WA7.
what is tricky test 7?
I found my bug, I renum all vertexes, but used old indexes :) (renum all child of vertex to as id....id+k, sequencial indexes).
Edited by author 15.02.2012 18:35 Since description says p[i]<i it was tempting to assume that initial sequence is already in DFS order, but it's not necessarily so. Got RE7 when explicitly checked for this. |
| is operations of int64(pascal) slower than long long(c++)? | frost | 1518. Jedi Riddle 3 | 15 Jun 2026 17:02 | 14 |
is operations of int64(pascal) slower than long long(c++)? I really optimized my prog to got AC(I write at Pascal). Please say how you did that on Pascal
my algo O(N^3*logX)
It work fast on my computer, but not on Timus :( Me and my friend had exactly the same algorithm and optomization but my program needs 1.7 and his needs 0.3secs (we both use C++)
It is very hard to solve it in Pascal, so use C++ :) or rewrite program several times.
It appeared, that FreePascal 2.0.4 compiler, which is used on Timus Online Judge, is extremely slow at arithmetical operations, especially on Int64-operands. "Mod" and "*" operations on Int64 are very slow. We did not expect such a thing, and we are sorry. Anyway, the jury HAS correct Pascal solution, which passes the timelimit (2 seconds), so it is a question of justice only, not of jury mistakes, problem incorrectness and so on. Now the timelimit is 3 seconds, and it is more than enough to solve this problem on Pascal without special optimization trick. My straightforward solution works exactly 2 second: http://acm.timus.ru/status.aspx?space=1&num=1518&pos=1383115 The problem will be rejudged soon. The performance of FreePascal 2.0.4 compiler in comparison with Delphi 7 compiler (dcc32 15.0) is under inverstigation. If Delphi appears to be faster (and it seems to be true), it would be added on Timus Online Judge. If you know the fastest Pascal compiler, please, tell us. It will be fair for Pascal programmers, because the fastest Intel C++ Compiler is used for C++. Edited by author 19.12.2006 21:43FreePascal generates very bad code for int64 multiplicatons.
I use Delphi 7.0 and on my computer (AthlonXP 2200)
my prog works 0.9 sec in worst case, but on Timus the
same prog works 2.093 sec.
I got AC in 1.261 sec with rewritng
multiplication on Assembler. 19 authors get AC instead of TLE. 7 of them increase their score by 1 problem! My algo is also N^3*log(X), but not accepted in C++.
how to solve it?
Time limit in test case 13. anyone helps me ?
Edited by author 20.12.2006 01:17 My solution is also O(logX*N^3) but my program written on Java works so slowly...
for example, It works about 6 seconds on test
100 268435455 268435455
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
I can't even imagine how to solve it without rewriting solution using another language...
Edited by author 08.01.2007 19:20 Since the matrix consists of only zeroes and ones, you can perform half of multiplications using just +, - and >= via 32bit types. Perform only squaring via __int64 and %. This helped to make my 2.9 sec C++ solution running at 1.5 sec. - [BSU] nzamulov 15 Jun 2026 17:01
Edited by author 15.06.2026 17:02 Correct answer for the test
100 268435455 268435455
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
is 94769974, btw |
| To Admins: Wrong tests #8 | Dmi3Molodov | 1102. Strange Dialog | 14 Jun 2026 04:41 | 1 |
The total length of all strings (including the first one with the number N) exceeds the specified size of 4000000 bytes. |
| PLEASE ADD SUPPORT FOR OCAML. | Dmohan | | 13 Jun 2026 19:32 | 1 |
Hi,
Kindly add support for ocaml to execute timus problems.
Thanks. |
| To Admins: Weak tests | Dmi3Molodov | 1242. Werewolf | 13 Jun 2026 01:51 | 1 |
1) write in the assignment that family ties and victims cannot be repeated in the input, or add such tests. this is a real problem when searching for maniacs in databases.
2) write in the assignment that a werewolf cannot kill himself. |
| Please add this test. | Zayakin Andrey[PermSU] | 1202. Rectangles Travel | 12 Jun 2026 06:57 | 2 |
#include <cstdio>
int main() {
freopen("output.txt", "w", stdout);
printf("99999\n");
printf("0 0 10 100\n");
for(int i =0 ; i < 99998; ++i) {
printf("%d %d %d %d\n", (i+1)*10,0,(i+2)*10 , 100);
}
return 0;
}
My early solution get AC, but must get TL.
Edited by author 19.01.2011 16:05 Also this test
4
0 0 2 6
2 2 4 4
4 0 6 6
6 2 8 4
My AC solution gives 12 when correct answer is 8 |
| What is the answer for... | Nazar | 1202. Rectangles Travel | 12 Jun 2026 06:57 | 4 |
What is the answer for
2
0 0 3 3
3 2 5 7
Answer is -1? Yes (-) Michael Rybak (accepted@ukr.net) 15 Feb 2006 18:29 What?! Why?
^
| __
| | |
| | |
| | |
|___| | Such input gives that picture, so why there is no path?!
| | |
| |__|
|___|
----------- > Your picture has 3,1 for lower-left corner of second rectangle |
| Why this taks can not be solved with Trie? :@@ | Giorgi Pataraia [Tbilisi SU] | 1414. Astronomical Database | 12 Jun 2026 00:26 | 6 |
It's just brute-force task :) There 36 lines in my AC code versus yours 165 lines :)
Edited by author 08.03.2013 19:59 thanks, now AC with set :/ It can actually be solved with trie. My solution uses 0.4s (cin) and 20MB.
Just store a map in every node. Solved with C++ with tree of static arrays of links, without any STL structures Same here. 0.062 sec, 1.8Mb |
| Some tests | andreyDagger | 1998. The old Padawan | 11 Jun 2026 23:09 | 3 |
5 3 1
2
2
2
2
2
3
4
6
ans: 11
5 3 3
1
2
3
4
5
1
4
7
ans: 12
9 9 123
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ans: 9 Why does the last test have an answer 9? on 9th second he can't pick up the last stone, instead he drops all of them, so isn't the answer 27? |
| WA on test 6 in C++ | Mamuka Sakhelashvili [Freeuni] | 1316. Electronic Auction | 11 Jun 2026 22:45 | 5 |
I have solved this problem by Fenvic tree, at first I got WA on 5 test, then I changed int-s into long long-s and now I have WA on 6 test. If you had this kind of experience please tell me what types should I use to get AC?
Thanks. The test 6 aint about data types' ranges. იდეაში, ეგ ხო ფენვიკის ხით უნდა გავიდეს, მე ვთვლი რაოდენობას, რამდენი გაყიდვა შესრულდება და შემდეგ ვამრავლებ 0.01–ზე და ვაბეჭდინებ. და ეგრე უნდა მუშაობდეს წესით ხო? Try this test
BID 0.01
SALE 0.02 10
Answer:0.00 |
| Is there better solution then O(n^3) for each test? | vgu | 1221. Malevich Strikes Back! | 11 Jun 2026 21:35 | 5 |
How I can do it on 0.001?
Edited by author 31.10.2008 02:29
Edited by author 16.06.2009 00:42 I track w0[i][j] as length of longest horizontal stride of a[i][j]==0 starting at i,j (0 if a[i][j]==1), symmetric for w1[i][j]. Now w1[i][j] defines the length to be tested (as 2*w[i][j]+1), this is done by descending downwards. At first it seems to be O(N^3) but due to nature of the pattern you won't descend all that frequently, so I believe it's O(N^2), and it gave 0.001 AC in C++ |
| Problem description | LaVuna [NULP] | 1221. Malevich Strikes Back! | 11 Jun 2026 21:17 | 2 |
You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance:
1)
1 1 1 0 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 1
1 1 1 0 1 1 1
2)
1 1 1 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1
are desired matrices maximum width of which you must find 1st matrix is invalid (pre-last row) |
| Can we do this in O(N) ? | Nikunj Banka | 1031. Railway Tickets | 10 Jun 2026 11:52 | 5 |
My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm? heap?:D
just use lower_bound And, BTW, Yes there is.
At first I used Binary Search on each station but on the next station you can start with the previous index. code:
int canReach1 = A[i] + L1;
while (ind1 <= end && A[ind1] <= canReach1) ind1 ++; i've used dp (which is easy to notice) with some optimization. suppose we have three stations
s1 s2 s3
and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3) You can keep deque (FIFO) of pairs (max_x,total_price) if using C1 on last trip, same for C2, same for C3. All three deques will be non-descending on price (and naturally ascending on coordinate). At each step pick minimum from non-empty deques (their front element) and push new advances to their end.
Edited by author 11.06.2026 06:16 |
| WA#11 | GePo | 1291. Gear-wheels | 10 Jun 2026 04:55 | 7 |
WA#11 GePo 26 Sep 2004 20:25 What means if gear-wheel have only one cog?
Edited by author 26.09.2004 20:25 In this test have some gear not connect from other
Try this test
2
1 0
1 0
1 6
answer
6/1
0/1
Edited by author 18.04.2005 12:50 |
