Can someone tell me in which case my solution will be wrong?
In trying to work out why my attempt during the contest didn’t work, I came up with this, which gives a shorter answer, and should be more efficient.
The differences from the solution in the editorial are:
-
Rather than using repeated sequences of {maxA, maxA-1, 1} I have only one maxA-1 and then just repeat maxA. This gives the same set of non-zero values, since gcd(maxA, maxA) == maxA.
-
I calculate in advance how many repeats I need, and hence the length of the vector, so making allocation more efficient.
-
Knowing how many repeats I have allows me to use fill() to fill the vector, rather than a loop.
Need Help, Correct me if I’m wrong
what’s wrong in this solution
what I’m doing is.
for d<=1e5-2
A = d+1, d+2
for d>1e5-2
A = 1e5-1, 1e5, 1e5, … , 2, 2, … .
for i=1 and j=1 to k(till last 1e5 in above sequence A) we always get 1e5-2
and for remaining j (where A_i = 2) we get always 1
so, I’m creating this sequence such a way that it’s sum gives d and if I’m not wrong than it’s always possible to do with above sequence.
hello, brother even I’m doing the same as you but still WA, if you know where we are getting WA then please help me too, here my solution
def ultsolve(d):
op=[]
p=(10**5)-2
while True:
if d>=p:
op.append(p+2)
op.append(p+1)
op.append(1)
d-=p
else:
op.append(p+2)
op.append(p+1)
break
print(len(op))
print(*op)
What is wrong with this and also this? can anyone help!
def solve(d):
op=[]
p=(10**5)-2
while d>0:
p=min(d,p)
op.append(p+1)
op.append(p+2)
op.append(1)
d= d-p
print(len(op))
print(*op)
Actually your solution will exceed the sequence size limit which is 10^5. Consider D=3*(10^5-2). Now, you will insert 10^5,10^5-1,10^5-1 and then D=10^5-2(According to your code). Now you will insert 2 for 10^5-2 times and the overall size of your sequence will be 10^5+1. So instead of adding 2 again and again you can simply use the approach used by the editorial. Here is your edited code which will give AC.
Thanks a lot brother, i was stuck over a long time, thanks again
I think in first code d should be strictly greater than p, i.e (d>p) not (d>=p).
For D=2*10^5-1 the size of your sequence will be 10^5+3 which exceeds the given size limit.
It is again giving me WA. btw I don’t think so, strictly greater will impact if we use or not.
Yes you are right it doesn’t matter. But a small mistake which is giving you WA is:
op.append(p+2)
op.append(p+1)
They should be:
op.append(d+2)
op.append(d+1)
It is because for d<1e5 , let suppose 5, it will give you 1e5 and 1e5-1 and their contributed answer will be 1e5-2, which will be definitely wrong.
Hope it will help you.
Hey your first code will always give 10^5-2 for all D<10^5-2, which is incorrect. And your second code doesn’t consider d=0.
I think we can make a much easier to understand construction than the editorial.Consider the elements {maxm,maxm-1,1,5,3,1}, they would contribute (maxm-1-1) + (3-1) =maxm to the answer.Since we want the answer to be equal to d, we will find how many times we can divide d by maxm and do the same step that many times. Now still some rem=d%maxm remain to be added to the answer to make it equal to d. rem is certainly less than maxm(1e5),so we can directly add {rem,rem-1,1,5,3,1} which will add (rem-1-1)+(3-1)=rem to our answer.Cases when rem=1 or 0 can be dealt separately.When rem=1,we can just insert {3,2} in our resulting vector, when it is 0,we can insert just {1}.
Implementation:-
https://www.codechef.com/viewsolution/39047715
thank man, now I got it. Check the second code also.
if we use d=0 case, then it will stuck in the while loop. You can try by yourself.
Thanks bro
Oh!! Thanks, man
Why can’t we print
d^2 d^3
min-gcd= d^2-d=d (ANSWER)