### Tima's blog

By Tima, history, 9 years ago,

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

• +28

 » 9 years ago, # | ← Rev. 7 →   +5 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 + 1By using interval tree, for one prime, time complexity is O(|p|log(|p|)) Overall time complexity: O(n*log^2(n))
•  » » 9 years ago, # ^ |   0 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.
 » 9 years ago, # |   0 How to solve L?
•  » » 9 years ago, # ^ | ← Rev. 10 →   +5 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. :)
•  » » » 9 years ago, # ^ |   +5 Hi! Please can you tell why we cannot do that: Find all powers of first tree ( A ) Find all powers of second tree ( B ) Sort both of them in non-increasing orded. Iterate through all leaf ( power == 1 ) from second tree and check next condition: Get power of parent of that leaf ( x ) Find first power which equal x and descrease it by 1 Sort B again Compare two arrays A and B if they are equal we have leaf number and remember minimum of that's numbers If A!=B increase first power in B which equal x-1 by 1. Next iteration Sorry for my English, hope you understand me.
•  » » » » 9 years ago, # ^ | ← Rev. 8 →   +5 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: First Tree: 1-2, 1-3, 2-4, 2-5, 3-6Second Tree: 1-2, 1-3, 2-4, 2-5, 5-6Be the way, how to upload a picture to Codeforces?
•  » » » » » 9 years ago, # ^ |   +5 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.
•  » » » 9 years ago, # ^ |   +8 How do you compute hashes of subtrees?
 » 9 years ago, # |   +13 how to solve K, E, H, F ?(div2)
 » 3 years ago, # |   0 Can anyone share their solution for problem G?