### Pentagon's blog

By Pentagon, 8 years ago,

Hi everyone :) ! I choose some problems from CODEFORCES and TIMUS.I invite you to participate in this contest.I will be glad if you join this contest :) http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38811#overview

• +6

 » 8 years ago, # |   0 Can we write solution of "Problem U(Line Painting)" with segment tree ???
•  » » 8 years ago, # ^ |   0 Yes, you can. A simple, straighforward approach.
•  » » » 8 years ago, # ^ |   0 Regarding to Problem U(Line Painting) Could you explain solution with more detail? Thank you beforehand.
 » 8 years ago, # |   0 I thought but i didn't find solution. Could you explain solution of this problem please?
•  » » 8 years ago, # ^ |   +1 Compress coordinates to at most [0..2N). Build a segment tree over them; one query is a range update (set color of range) on it. Convert the result into an array, find consecutive white segments in it and (remembering how the coordinates were compressed) choose the longest one. Time: . It's really just about knowing the data structure.Of course, a bruteforce instead of a segment tree (but with coordinate compression) would also pass.
 » 8 years ago, # | ← Rev. 2 →   0 Who think we can use KMP in "Problem D(Newspaper Headline)"? I think we can do this problem with KMP.But i dont 100 % believe...
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 It's about a subsequence, not a substring, so no KMP here.The problems there are all easy, they can be solved without any serious algorithms. D is just about optimizing the straightforward LCS-like solution.
•  » » 8 years ago, # ^ |   0 I don't know how you would like to use KMP, but I think it could be too slow if both strings are very long and the output is very big. (e.g.: s1="abbb...bbb", s2="aaa...aaa"). I thing KMP have O(|s1|*|s2|) complexity in this input because the shortest string which met the requirements have that much character.
 » 8 years ago, # |   0 "Problem J(Lucky Numbers)" solve with bitwise operation...
 » 8 years ago, # |   0 How can i solve Anansi's Cobweb(Timus)? here is link to problem http://acm.timus.ru/problem.aspx?space=1&num=1671. Thanks beforehand
•  » » 8 years ago, # ^ |   0 The best approach is union-find on the operations in reverse order.
•  » » » 8 years ago, # ^ |   0 thanks, i got AC :)
•  » » » 9 months ago, # ^ |   -10 can you elaborate it. i could not find solution for this problem anywhere.
•  » » » » 3 months ago, # ^ |   0 finally i solved itApply the union operations(M) which are not in Q(coz those threats won't be removed even after Q operations) , then do the operations Q in reverse order ,
 » 8 years ago, # |   0 Could someone send the code of problem U(Line Painting)?