danx's blog

By danx, history, 4 months ago, In English

Hello everyone!

Below is the editorial for the informatics division of CAMA along with the solution code to every problem. We have also uploaded PDFs with the editorial both in Spanish and English on our website. The contest can be found on this gym.

The problems were prepared by Esomer, danx, Hectorungo_18, javiergm06 and Rigobertus. We would also like to thank our VIP tester BernatP for his dedication towards the contest.

A. Saving the cinema

Solution
Code

B. Operation

Solution
Code

C. Maximum profit

Solution
Code

D. jbum

Solution
Code

E. Looking for palindromes

Solution
Code

F. Harry Potter in CMS

Solution
Code

G. XOR + Constructive = Love

First of all, we would like to apologize for misjudging the difficulty of this problem. It turned out to be much harder than what we expected.

Solution
Code

H. Menorca's ants

Solution
Code

I. Fake bills

Solution
Code

J. Force Perturbation

Solution
Code

K. Óscar and his battle

Solution
Code

L. Random intervals

Solution
Code

M. The battle of Helm's Deep

Solution
Code

N. The Omer's orange tree

Solution
Code

O. Bea the maximizer

Solution
Code

P. Ski resort

Solution
Code

Full text and comments »

Tutorial of CAMA 2023
  • Vote: I like it
  • +30
  • Vote: I do not like it

By danx, history, 5 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.

Full text and comments »

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