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

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 23:07:09 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

for every prime number

Pget list of positionsi, where a[i] is divisible byP,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))

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.

How to solve L?

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. :)

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

Get power of parent of that leaf ( x )

Sorry for my English, hope you understand me.

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-6

Second Tree:

1-2, 1-3, 2-4, 2-5, 5-6

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

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.

How do you compute hashes of subtrees?

how to solve

K,E,H,F?(div2)Can anyone share their solution for problem G?