Chen_ChaoRui's blog

By Chen_ChaoRui, 11 years ago, In English

As we know, during the contest CodeForces Round #189 Codeforces Round 189 (Div. 1) few participators solved problem 319D. 319D - Вам знакомо это слово?

And almost all of the algorithms they used are brute force. At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. Just like these: C++ 3951251 Pascal 3957673

But I thought this problem as for D was authored for some algorithms more difficult like Suffix Automaton or Suffix Arrays. Like this: 3952463

The complexity of these algorithms are better than brute force, but they caused more time when they are using. I think the 6 seconds time limit was for this.

Also we may solve this problem using Hash. It is a very good algorithm for problems about strings. It is easier than suffix algorithms and its complexity can be great. Like this: 3958099

Maybe we can make some testdatas to let brute force gets Time Limit Exceeded. Sorry for my poor English. After all, thanks for the problem authors, Round #189 was a good contest.

Full text and comments »

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

By Chen_ChaoRui, 12 years ago, In English

Maybe something was wrong with 55A - Flea travel The input of the second sample and the test 2 are the same, but the answers are opposite. 3126932 Please give it a check, thank you.

Full text and comments »

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

By Chen_ChaoRui, 12 years ago, In English

Happy New Year for everyone! It is Chinese new year today. But I'm still working on my computer, preparing for so many exams. This year, CodeForces helps me a lot. For the coming new year, I hope everything will be all right. Bless all.

Full text and comments »

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

By Chen_ChaoRui, 12 years ago, In English

Maybe something was wrong with problem 79B 79B - Разноцветное поле 2997091 2997120 2997127 2997138 2997142 I got Judgement failed for many times. Please give it a check, thank you.

Full text and comments »

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