danx's blog

By danx, history, 2 months ago, In English

Hello codefoces users.

A while ago, I solved CSES problem 2209 (https://cses.fi/problemset/task/2209) related to combinatorics involving necklaces (https://en.wikipedia.org/wiki/Necklace_(combinatorics)) with a time complexity of O(sqrt(n) + divs(n) * (divs(n) + log(n))). I believe this complexity can be further reduced to O(sqrt(n) + divs(n) * (2^(nOfPrimes(n)) * log(divs(n)) + log(n))).

Upon reading the editorial, I discovered that the official solution utilizes Burnside's Lemma and has a time complexity of O(nlogn). I was unsure if my solution was previously known or not.

After conducting some research, I was unable to find a similar solution to mine. Consequently, I considered using this problem with higher constraints in a future contest. However, I am uncertain whether this is a wise decision. Therefore, I have two questions:

  1. Is there a known solution with a better time complexity for this problem than my approach?
  2. Would it be advisable to incorporate a classical problem with higher constraints into a contest?

Thank you for your assistance.

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

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by danx (previous revision, new revision, compare).

2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can also achieve $$$O(sqrtN)$$$ using burnside lemma, by grouping terms by $$$gcd(n,k)$$$, which gives precisely the formula pointed out on wikipedia.

About incorporating a classical problem with higher constraints, I see no issue depending on the purpose of the contest. I actually added a version of it to my internal college contest: link