venti's blog

By venti, history, 4 weeks ago, In English

While solving this problem from CSES — Hamming Distance — I was surprised to see that my O(N^2) solution passed where N = 2e4. The solution wasn't pruned so I'm sure it must've taken ~ N^2 operations.

What exactly is a good estimate on number of operations allowed? I believed 3e7 operations was a good estimate, but clearly this isn't the case, so what is the actual threshold?

Read more »

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

By venti, history, 2 months ago, In English

Hi, I was trying to solve atcoder's ABC191 problem D

Problem statement - Given X, Y, R that define a circle centered at (X, Y) with radius R, find the number of grid points whose x- and y-coords are integers, that lie within or on the circle.

Constraints are: |X|, |Y|, R < 1e5 (X, Y, and R can be floating point values upto 4 decimal places)

Approach used -

The equation of a circle is (x-a)^2 + (y-b)^2 = R^2 for a circle centered at (a, b)

So I figure the qn wants me to solve the integral solutions to (x-a)^2 + (y-b)^2 <= R^2

I isolate (y-b)^2 and iterate over all candidate values of x from [-a-R-1, a+R+1] and compute the lower and upper bound of y and add them all up and output them.

For some reason this fails on some tests — I observed this is also pretty different from the editorial approach. Is there something fundamentally wrong with my idea/code?

Code -

a, b, r = [float(i) for i in input().split()]
'''
(x-a)^2 + (y-b)^2 <= r^2
=> (y-b)^2 <= r^2 - (x-a)^2

k = r^2 - (x-a)^2
y <= sqrt(K)+b
y >= b-sqrt(K)
'''
ans = 0
from math import floor, ceil
for x in range(-int(a)-int(r)-2, int(a)+int(r)+3):
    k = r*r - (x-a)**2
    if k<0:
        continue
    ans += max(0, 1 + floor(k**0.5 + b) - ceil(b-(k**0.5)))
print(ans)

Read more »

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

By venti, history, 6 months ago, In English

Reading through this DP blogpost by zscoderhttps://codeforces.com/blog/entry/47764

In the "open and close interval" section, the blogpost explains this problem — https://codeforces.com/contest/626/problem/F

The explanation says -

"Suppose there are j open sets. When we add a[i], the sum a[i] - a[i - 1] will contribute to each of the j open sets, so we increase the current imbalance by j(a[i] - a[i - 1])."

But doesn't this imply that all j open sets contain a[i-1]?

Shouldn't the correct net increase in imbalance be - sum(a[i] - max(cur_open_set)) // (assuming we somehow tracked the max for each cur_open_set)

But for my equation to be equal to j*(a[i]-a[i-1]), all the current open sets would need to have a[i-1] in them. So how does this work?

Basically I'm unable to understand the transition of the 3rd state in the DP equation in the blogpost. If anyone can help clarify my misunderstanding or explain it in a different way, I'd be grateful!

Please help! Thanks!

Read more »

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