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

Автор rishup132, история, 6 лет назад, По-английски

Hello Codeforces.

RECursion, the coding community of NIT Durgapur, is organizing coding contest RECode 4.0 which will be held on 13 November at 16:00 UTC. We invite you all to participate in the contest.

The contest will be held on Hackerrank platform. The contest consists of 6 problems to be solved in 2 hours. There are exciting prizes for overall winner and college winner.

The RECode 4.0 is over, Ranklist is as follows:

  1. Teo Moroianu
  2. Jeffrey Ho
  3. Kerim Kocekow
  4. Uwi Tenpen
  5. Farhod Farmon
  6. Teimurazi Toloraia
  7. Saharsh Luthra
  8. abishek a
  9. Nishant Arya Kumawat
  10. Victor Forbes

UPD : Editorials

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

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

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

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

I am beginner. Can i participate in this contest??

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

Is it rated?

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

What you mean by institute winners?

Institute winners for only NIT Durgapur, or institute winners for every institute?

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

What does winners mean here? Only rank 1?

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

Do you guys have any idea on this?

Edit: For those who wanted to read, there was a random guy who reported a question name something like "How to solve 'Watari Queries'?" before the starting of contest.

Quite good, huh?

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

How to solve E(Apple and Ryuk)?

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

    Let ai = 1 if there is an apple in position i, and 0 otherwise. The problem becomes, for each 0 ≤ d ≤ N - 1 calculate .

    If we set two polynomials and then the coefficients of A(x)B(x) from n to 2n - 1 are exactly the desired solution. The product polynomial can be computed by FFT.

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

      I think bitset is much easier. For ith number, answer is popcount of (a) & (a >> i).

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

Can you provide editorial or solution for problem D,E and F

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

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

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

3rd question was really nice.

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

How to solve the last question(the gcd queries question)?

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

Did anyone solve Evil Group in some way other than the editorial?

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

    Sure,there is a solution with N * log(N) * log(A[i]) for precalculation and Q * log(N) for answer queries. First let's try to find for every i biggest j which j ≤ i and gcd(j, i) = 1 and it is always monotonic. That is why we can use here two-pointer to find j for every i. Personally I used Sparse table to find gcd of given range to answer in O(log(A[i])), but you can also use segment-tree instead of it(it will take O(log(N) * log(A[i]))). After finding j for every i(let's call j as p[i]), it is easy to answer queries in offline. Just go from 1 to n and every time increase for every i the range between 1 and p[i](you can use lazy propagation to increase range or you can easily use Fenwick tree instead of it). Then for every i, just answer all queries which R = i, which answer will sum of range (L, R).