brute force will be TLE for 3rd one …
I mean square-root brute.
then please tell me efficient approach or what modification can i do ?
No idea. It took 1 hour to understand C . They could have written it in simple manner also. I don’t like too much math stuff, so no idea.
Someone use euler sieve other use prime sieve then i don’t know what he/she did?
OK @samarthtandon can u help?
Editorial is out on cf…
I only passes the small one…not full so no idea…
as 1st can be easily done with sieve
if you know the number of factors of N:
if N is even than -> no of even factors = no of factors of N/2
no of odd factors = no of factors of N - even
if N is odd than-> even = 0, odd = factor of N
1 Like
I already pass test 1 , but i want sol . which passes all the test cases
I will try to explain as much as possible:
Basic idea:
Given L and R, iterate from 1 to {\sqrt{R}}
For each {i} in range ({1, \sqrt{R}}):
find all find all multiples of {i} in range({L,R}) and update it in OddList and EvenList.
Then iterate from L to R to find how many have abs(odd - even <= 2)
By OddList I mean, an array of size {R-L+1} where {OddList[i]} represents how many odd multiples the number {L+i} has.
My solution to problem B :-
Apply Gaussian to the 2nd equation and you are done…to check if solution exists or not.
Where to learn about gaussian and diophantine?
Can you please share your code
Diophantine takes integer values for all unknowns, but the value of x(according to the equation in the picture) can be decimal value.
So I guess it wont be Diophantine.
Correct me if I am wrong.
And can you provide the code for the second question’s solution?
I am talking about Gaussian…Diophantine was a mis-spell. Yes, I have the AC code. Will post it tomorrow.
1 Like
I solved Q1 using Union Find.
class Dset:
def __init__(self,n):
self.sets=[i for i in range(n)]
self.distinct_sets=n
self.size=[1 for i in range(n)]
def union(self,x,y):
size=self.size
sets=self.sets
px=self.find(x)
py=self.find(y)
if px==py:
return 0
self.distinct_sets-=1
if size[px] > size[py]:
sets[py]=px
size[px]+=size[py]
else:
sets[px]=py
size[py]+=size[px]
return 1
def find(self,x):
sets=self.sets
while sets[x]!=x:
sets[x]=sets[sets[x]]
x=sets[x]
return x
for t in range(int(input())):
n,m=list(map(int,input().split()))
s=Dset(n+1)
ans=0
for __ in range(m):
a,b=list(map(int,input().split()))
ans+=s.union(a,b)
dis=s.distinct_sets
dis-=2
ans+=dis*2
print("Case #{}: {}".format(t+1,ans))
Can you please provide your code for problem 2?