Axial-Tilted's blog

B Think-cell round 1
By Axial-Tilted, history, 9 months ago, In English

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)

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

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)

→ Reply
»
9 months ago, # |
  Vote: I like it -53 Vote: I do not like it

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

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Bro, the blog asks for ways to efficiently write a checker for problem B, not the solution for problem B

    → Reply