pop3's blog

By pop3, history, 4 years ago, In English

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!

Full text and comments »

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

By pop3, history, 4 years ago, In English

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.)

Full text and comments »

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

By pop3, history, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it