Pentagon's blog

Training Contest
By Pentagon, 11 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we write solution of "Problem U(Line Painting)" with segment tree ???

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you can. A simple, straighforward approach.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Regarding to Problem U(Line Painting) Could you explain solution with more detail? Thank you beforehand.

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought but i didn't find solution. Could you explain solution of this problem please?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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...

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The best approach is union-find on the operations in reverse order.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone send the code of problem U(Line Painting)?

→ Reply