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

Автор WARush143, история, 8 лет назад, По-английски

Hi,

I'm currently solving the problem Vacation ( http://main.edu.pl/en/archive/ontak/2010/wak ). I find these problems where every subarray of length n has to satisfy some property very challenging. I believe its DP, but I would appreciate anyones help on this problem.

Thanks

Полный текст и комментарии »

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

Автор WARush143, история, 8 лет назад, По-английски

Hi,

I'm solving this POI problem: http://main.edu.pl/en/archive/oi/15/kup . Basically, given an integer k(1 ≤ k ≤ 109) and an N by N square grid(1 ≤ N ≤ 2000) of non-negative integers, you have to find some rectangle in the grid such that its sum is between k and 2k, inclusive.

I can come up with O(n3) solution using prefix sums and monotonicity, however to make the problem fit the time limit I need something faster. By google translating the editorial, I think it's divide and conquer, but I couldn't understand the details as the translation was very bad. I would appreciate any help on this problem :D

Полный текст и комментарии »

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

Автор WARush143, история, 8 лет назад, По-английски

Hi all,

I was solving this problem — https://community.topcoder.com/stat?c=problem_statement&pm=14357

I have reduced it to counting number of non-intersecting pair of polygons, but how do I do this? I have looked at other competitor's codes, and they involve fixing two points and counting clockwise and counterclockwise rotations with a third point, but I don't understand how and why this is used. Would appreciate any explanations!

Thanks

Полный текст и комментарии »

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

Автор WARush143, история, 8 лет назад, По-английски

Hi community!

Today I am interested in this problem:

Given a directed graph, define f(v) to be the number of nodes i such you can reach i from v by moving along edges. For which values of v is f(v) maximum?

I can come up with the O(n2) algorithm, but I wonder if there is an O(n) algorithm.

Thanks!

Полный текст и комментарии »

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