@psychik I’m sharing my solution… in which I added 1 only 1 time when we want to break the sequence of 9999 and no more than that. CodeChef: Practical coding for everyone
Unfortunately, I missed just one error of adding 99999 but deduction 99998 and I’m getting into WA. I hope it goes in the right way in the next contest. Anyway good problem.
I don’t think that’ll make a difference. Correct me if I am wrong.
I think for any number -
min(d+1,d+2) = d+1;
gcd(d+1,d+2) = 1;
so for d > 1e5 + 2
we push_back(1e5-1);
then we push_back(1e5);
and pb(1);
and then we deduct (1e5-2) from d and continue it until d becomes smaller than 1e5-2
after that, we just push_back d+1 and d+2.
I think this works without any exceptions.
2 Likes
Kindly see which comment I replied to.
I was not talking about the approach mentioned in the editorial, I was talking about a comment.
We can also use the fact that min(2x,3x)-gcd(2x,3x)=x to solve this problem.
Submission Link here.
Any suggestions what will be the complexity of this code?
1 Like
@bit_maniac I have done exactly same as editorial sol. but my code is giving WA.
can you tell where am i making mistake.
Your code is not handling case of (d=0).
Oh sorry buddy, My bad.
1 Like
Can you please tell why we are including 1 for every substring like p+2,p+1,1
as p+2,p+1 is also giving same answer
My submission:
https://www.codechef.com/viewsolution/39037641
@ssrivastava990 bro help please
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
1 Like
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.