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

Автор 72VanVector_SevNTU, 13 лет назад, По-английски

Hi to all. I want to discuss some problems from the last contest on codechef, which had just been over. There are given some tasks and ten days to solve them.

I,m interested in Prob E. Sine Partition Function especially. Tried to solve it using combinatorics and DP but recieved TLE (as I expected). I didn't use trigonometrical identities and I must mention that the precision of the output is rather weak, that could be useful, I guess. Will be glad to see your ideas.

Also it would be interesting to get some hints to  Prob F. Repeated String. I've got AC with very dummy algo as time limit make it possible. I've seen other solutions verdicts, they were rather fast.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Repeated String: Try to build suffix array and calculate least common prefixes of adjacent elements of the array.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Repeated string - let F(x) be the biggest count of equal substrings of length x in initial string. It can be easily proved that  F(x) ≥ F(x + 1), so we can use dichotomy with bounds left = L, right = H.
F(x) can be calculated in time using hashes and balanced tree or in O(n) time using hashes and hash-table.
So, the whole complexity will be or .
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Оффтоп.
Буквально час назад на этом сайте Антон Райчук поменял себе страну с UA на CA.
Как-то печально...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Оффтоп.

    Вы может знаете (или ещё кто-то прочитавший этот коммент), получают ли в этом раунде топ10нониндиан футболки? И ещё где можно указать размер футболки? И ещё сколько она идёт? :)

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так а что печального, если он учится в канадском универе?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, мне казалось, что страну указывают по гражданству, а не по текущему местопребыванию. Так что, думаю, гражданство он уже поменял или твердо намерен это сделать.
      Хотя, конечно, это его дело...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это действительно его личное дело.
        Более печальным является, наверное, тот факт, что работа IT-специалистов в стране UA не оценивается такой же зарплатой, как в CA...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
As I have just found the explanation for all the problems already appeared.