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

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

SPOILER ALERT: Please do not read these hints if you want to solve some problems in this contest but haven't attempted yet.

DO NOT open if you want to solve them by yourself
  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

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

For problem K, though solutions are accepted, there exist some solutions in .

One observation is that what we need to do is to match the suffix tree of S with the trie.

Assuming suffixes of string S are sorted in lexicographical order, one can observe that each node in the trie can match a contiguous subsequence of sorted suffixes.

Thus, using binary search to match a single character with these suffixes is enough, which does not require hashing.

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

For problem L, how to count the number of 4-cycles in such time complexity?

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

    Let's sort vertices in degree non-ascending order and relabel them, that is, if u is the i-th element after the sort, we relabel it as i.

    We may enumerate a, b, c, d ranged from 1 to n and check if a - b - c - d - a form a 4-cycle when a = min(a, b, c, d) and b < d. It is easy to show, for each simple 4-cycle, it will be counted exactly once.

    Actually, we can just enumerate 3 vertices to accomplish the mission. Let's set a counter cnt(w) for each vertex w. And then, do the following algorithm:

    • enumerate vertex u from 1 to n:
      • enumerate a neighbor of u, vertex v, such that u < v:
        • enumerate a neighbor of v, vertex w, such that u < w:
          • cnt(w) is set to 0.
      • enumerate a neighbor of u, vertex v, such that u < v:
        • enumerate a neighbor of v, vertex w, such that u < w:
          • detect cnt(w) 4-cycles (u - v - w - x - u, x is one of visited v);
          • increase cnt(w) by 1.

    Do you notice that v can be less or greater than x but each 4-cycle is still counted exactly once?

    Analysis of time complexity:

    1. enumeration of u is O(n);
    2. enumerations of u → v are in total O(m);
    3. enumerations of u → v → w with u < v are categorized by the degree of v:
      • if the degree of v is less than T, then for each u → v, the number of w such that v → w is less than T, so the number of this type of u → v → w is O(mT);
      • if the degree of v is at least T, then the degree of u is at least T as well, so the number of u such that u → v and u < v is at most , and thus the number of this type of u → v → w is ;
      • the minimum value of (1 ≤ T ≤ n) is , when .
    4. consequently, the total time complexity is .

    Does the aforementioned algorithm really need a threshold T?

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

      Btw, you need to store the graph using something like std::vector, otherwise the cache missing will lead to TLE like my code.

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

      Actually, f(T) = m * T + 2 * m * 2 * m / T >= 2 * sqrt(m * T * 2 * m * 2 * m / T) = 4 * m * sqrt(M) from AM >= GM inequality and in AM-GM we have equality when terms are equal so T = 2 * sqrt(M). Complexity is still the same, but if you want to be mathematically accurate, T = 2 * sqrt(M) is the right value.

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

How to solve problem E (Resistors in Parallel)?

for the given Input:

R = {1,2,3,inf,5,6,7,8,inf,10}

S1 = {1} = 1

s2 = {1,2} = 2/3

s3 = {1,3} = 3/4

s4 = {1,2,inf} = 2/3

s5 = {1,5} = 5/6

s6 = {1,2,3,6} = 1/2

s7 = {1,7} = 7/8

s8 = {1,2,4,8} = 8/15

s9 = {1,3,inf} = 3/4

s10 = {1,2,5,10} = 10/17

Ans = min(s(i)) = 1/2 

am I missing something?

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

    r8 = ∞ because 22|8. And consequently, the resistance of S8 should be , which is equal to the resistance of S2k for k = 1, 2, ....

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

      sorry, my bad! how should i proceed with this since the numbers are really large (100 digit number) and couldn't find any relation with the given hint(finding prime factors would also timeout)?

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

        With the hint, the remaining is a problem about the constructive algorithm. Try to avoid the factorization. GL!

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

The time limit of L seems too tight? I tried various ways of optimization (including fread-based input) and finally get AC in around 11.2 sec / 12.0 sec...

ps. My AC code

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

How do you prove that the greedy solution is correct in B?