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

Автор pop3, история, 3 года назад, По-английски

Can you please suggest problems which are based on segments, intervals, line sweep (for intervals etc), like this one. How to find such problems on codeforces or other judges? Thanks!

Полный текст и комментарии »

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

Автор pop3, история, 3 года назад, По-английски

Suppose for a function f(x) , for different values of x , f(x) is a bool value yes(y) or no(n) as:-

$$$nnnnnyyyyynnnnn$$$

Also suppose the check function in bsearch returns (-1) if its in the left 'n' block , (0) if its a 'y', and (1) if its in the right 'n' block.

So I need to find the largest value of x for which f(x) is yes(y). Is it doable by binary search?

(Usually we have f(x) varying as $$$yyyyyynnnnnn$$$ or $$$nnnnnnyyyyyy$$$ and in that we can easily use bsearch.)

Полный текст и комментарии »

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

Автор pop3, история, 4 года назад, По-английски

Given array of n elements. Find the number of pairs i, j (1 ≤ i < j ≤ n) such that gcd(ai,aj) = 1.

Constraints are: 1 ≤ N ≤ 30000,  1 ≤ a i ≤ (10^8). TL = 0.6s

One user has explained the solution here but I am not able to understand how subsets are used in the solution and the time complexity part.

If someone can please explain, it would be of much help. Thanks in advance!

Полный текст и комментарии »

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