Tima's blog

Grand Prix of SPb 2015
By Tima, history, 9 years ago, In Russian

Прошел четвертый этап XV Открытого Кубка по программированию. Как решать задачу D?

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

»
9 years ago, # |
← Rev. 7   Vote: I like it +5 Vote: I do not like it

for every prime number P get list of positions i, where a[i] is divisible by P,
Let's denote positions as p.

So, we need to find, (j, i) such that p[i]-p[j] is maximised and next condition is hold
* p[i] — p[j] + 1 <= 2 * (i — j + 1)
or p[i] — 2*i <= p[j] — 2*j + 1

By using interval tree, for one prime, time complexity is O(|p|log(|p|))
Overall time complexity: O(n*log^2(n))

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When working with a prime P[i], I always built the segtree with the vectors related to that prime. And started to find the maximum index. It was a nice problem to solve during the contest time.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 10   Vote: I like it +5 Vote: I do not like it

    Find centroids of the first tree, can be one or two centroids, try both.
    Find centroids of the second tree. If there are two centroids try both.
    We will try all combinations of centroids. Let's denote centroid of the first tree as v and centroid of the second tree as u.

    Now, we will assume that the vertex v is the vertex u in the second tree.

    We try to compare two subtrees recursively,

    bool isSame(v, u);

    Here, subtree u in the second tree should have one more vertex than subtree v.

    Now, we will compute hashes of subtrees of children u and v, after that try to match two arrays of hashes, there should remain exactly one non-matching subtree from both tree. Check them recursively.

    P.S. I may miss something. :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hi! Please can you tell why we cannot do that:

      1. Find all powers of first tree ( A )
      2. Find all powers of second tree ( B )
      3. Sort both of them in non-increasing orded.
      4. Iterate through all leaf ( power == 1 ) from second tree and check next condition:

      5. Get power of parent of that leaf ( x )

      6. Find first power which equal x and descrease it by 1
      7. Sort B again
      8. Compare two arrays A and B if they are equal we have leaf number and remember minimum of that's numbers
      9. If A!=B increase first power in B which equal x-1 by 1.
      10. Next iteration

      Sorry for my English, hope you understand me.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 8   Vote: I like it +5 Vote: I do not like it

        Shortly, your proposition is: If degree sets of both trees are equal, then you conclude that trees are also equal? If I understood correctly, this should be Counter Example: Counter Example

        First Tree:
        1-2, 1-3, 2-4, 2-5, 3-6

        Second Tree:
        1-2, 1-3, 2-4, 2-5, 5-6

        Be the way, how to upload a picture to Codeforces?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Yes, I suggest it. Thank you for your answer. But this part is hard for me because I cannot find some counter examples.

          Anyway, thank you much.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      How do you compute hashes of subtrees?

      → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

how to solve K, E, H, F ?(div2)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share their solution for problem G?

→ Reply