Блог пользователя Axial-Tilted

B Think-cell round 1
Автор Axial-Tilted, история, 9 месяцев назад, По-английски

how would you write a checker for problem B from the contest Think-cell round 1 with complexity less than n^2 ?

in others words given a permutation of size n determine weather there exists 2 indices i and j (1 <= i,j <n) i != j , where p(i) devides p(j) and p(i+1) devides p(j+1)

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

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

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

→ Ответить
»
9 месяцев назад, # |
← Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

Iterate over all $$$1\le i\le n$$$ — all values $$$1, 2,\dots, n$$$ appear exactly once as $$$p_i$$$. For each value of $$$p_i$$$, there are $$$\left\lfloor n/p_i\right\rfloor$$$ distinct values of $$$p_j$$$ such that $$$p_i$$$ divides $$$p_j$$$. You can check all of these to make sure none of them satisfy the condition. In total, there are $$$O(n \log n)$$$ pairs $$$(i, j)$$$ we need to check (harmonic series)

→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится -53 Проголосовать: не нравится

just write a 2-level permutation i.e. 4 1 3 2 it is the same problem as K-Lever Permutation you can verify it by yourself by writing some permutations and trying to prove it. Keep in mind if n is odd then the second value will be 2 and if n is even then second value will be 1. then simply write n, sec, n — 1, sec + 1 ... and so on n-times

→ Ответить