Блог пользователя Tadrion

Algorithmic Engagements Final 2011
Автор Tadrion, 13 лет назад, По-английски
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/


  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm wondering whether online competitors will be able to see the onsite ranking?
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to solve Coprime Numbers ??
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How do you solve Prime prime power
→ Ответить