Tadrion's blog

Algorithmic Engagements Final 2011
By Tadrion, 13 years ago, In English
From organizers:
"Algorithmic Engagements is the biggest Polish programming contest with about 2000 competitors every year. It consists of 6 online elimination rounds, after which top 20 contestants advance to an onsite final, held in Zielona Góra or Warsaw, Poland.
This year we’ve decided to hold an online, open contest in parallel to the onsite finals."

Date: 26.11.2011
You can read about that contest and register here: http://contest.mimuw.edu.pl/


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

13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody tell simple simple solutions to egz and bio?
In egz I understand how to solve it with 2d-segment tree, but is there something easier?

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve Coprime Numbers ??
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I don't know whether it's the most simple solution. Moreover, I think it's not, but that's how I solved:

    First of all, let's generate all prime numbers up to 3000000. Using that we can factorise numbers in O(sqrt(n)/log(n)) time.
    Lets add by one. While adding number Ai we will add to the answer number of Aj(j < i), that are coprime with Ai. Let B[p] is number of Aj that p|Aj. Let's factorise Ai. Let p1, p2...pm be the primes that divide Ai Number of Aj that are not coprime with Ai is number of Aj that one of p1, p2...pm divides Aj. Which is equal (using inclusion-exclusion formula) to B[p1] + B[p2] + ... + B[pm] - B[p1 * p2] - ... - B[pm - 1 * pm] + ... ± B[p1 * p2 * ... * pm].
    After adding Ai we need to update B, using p1, ...pm.
    Complexity - O(n * (sqrt(max) / log(max)+ 2m)), where m is the maximum possible number of primes in factorisation of the number <= 3000000, equal to 7 (in number 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510).
    This works at about 2 second on my computer on maxtest.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How do you keep B?

      I think it must has the size at least 2m, where m is the number of all primes less than 3 000 000,
      because you don't know exactly how many prime you have to use.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Nope. It has size at most 3000000, because the maximum prime product that can divide one of Ai is not greater than Ai itself, isn't it?
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It can be solved in O(max * log(max) + n). First, for each number we can find the smallest prime number which divides it. It can be done in O(max * log(max)) using the Eratosthenes sieve. 

      The answer is c(1) * m(1) + c(2) * m(2) + ... + c(max) * m(max), where c(i) is the number of elements from the input which are divisible by i. m(i) is the Mobius function. Both values can be easily calculated in O(max * log(max)).

      It works 0.5s on my computer on maxtest.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How do you solve Prime prime power
→ Reply