Блог пользователя Pentagon

Автор Pentagon, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, you can. A simple, straighforward approach.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +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.

»
11 лет назад, # |
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...

  • »
    »
    11 лет назад, # ^ |
    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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 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.

»
11 лет назад, # |
  Проголосовать: нравится 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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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