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

Автор adurysk, 11 лет назад, По-английски

Programming & Algorithms Group and SDSLabs invite you to Algophobic, a 5 hour ACM ICPC style individual coding contest. The contest will take place on 7th March from 7pm to 12 am on codevillage.sdslabs.co

The contest is open for everyone!!

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I cant see the captcha when I try to submit my code.

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

From 7 pm to 12 am... in what timezone?

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is there any other way to log in than with FB? Because I surely don't see it.

And URL links don't exist just because they look pretty, but so that people didn't have to copy-paste a link from the text...

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The contest is live now.Sorry for the inconvenience caused.

»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nice contest!

Have anyone ideas, how to solve problem "Starks and Tiles"?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Hey, I set the problem.Here goes a small hint-Try using mobius inversion formula. http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

      It's a funny situation, when a grey coder is helping a red coder :D

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is the complexity of each query in your algorithm? Some more hints will be appreciated. :)

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    I think I have the solution. I am too lazy to code it and check, so let me know if I missed something :D

    Suppose we have a function f(n) satisfying , then the required sum is and so, . Note that where and . So, we can answer each query in O(max(m, n)) time if we precompute f(n) for all 1 ≤ n ≤ 1000000.

    By mobius inversion, . If vp(n) ≥ 3 for some prime p, then at least one of μ(d) or is 0. Assume that is not the case, then let . The values of d which do not contribute 0 are precisely those values of the form for ci ≤ 1. Also, denote . Then since |μ(d)| = 1 for all such d. But we have obtained by applying mobius inversion to (which is a standard result of Gauss). So, .

    Now, we can precompute the least prime divisor array for each number in overall linear time and use it to factorize fast enough to compute the above f(n). The complexity of precomputation is but I think it runs much better because the numbers for which we have to actually compute the f value are cube-free numbers.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I wrote this solution on the contest, but it works 8 seconds on maxtest and gets TL.

      Maybe, there is very magic way, how to write this optimal... but it looks like author's solution is different, and much more faster.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The precomputation is the most expensive part and it takes only 2 × 107 operations in the worst case and each query is linear. I really see no reason for this to TLE :(

        Maybe, I should code it sometime later :P

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Precomutation is quick. We have 100 queries in the test and this is the problem. 10^8 of some multiplications, divisions, in long type... works long enough :(

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the editorials be published ?

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Here is my editorial for Starks and Tiles.Each query is taking O(sqrt(n)) time complexity. (http://goo.gl/0XFZMm)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Exactly the same idea as I and enot110 did except that the ending was pretty neat. Thanks for the cool problem, you should set more problems, perhaps a really mathy cf contest :D