woke up and first thing i do is check my codeforces account and there you have it, specialist. up we go, we up.
now lets discuss about the contest, i was rlly scared just before the contest but was pretty relaxed cuz of my prep and
after seeing the question was pretty happy cuz problem statements were small :D .
first problem: Farmnpiggie and Subset sum . this was really easy as its supposed to be first problem :P you just had to make sure that i*ci is never odd. means for every odd indexes you have to make sure
there is even number and for every even index keep any odd number on it. I was thinking of going with multiples of 2 but cuz of the constraints n<=50 and pi<=n, you have to go with
i-1 and i+1.
2nd problem: Ezraft and Array this problem was Number theorish (reminded me of my David Burton days). So first you had to see the invariance:
a1+a2+ ... an =sum= x1*a1=x2*a2=x3*a3.. =xn*an . Which means that sum is just Lcm of a1 to an, but still we cannot create subsequence from just this.
a1+a2+.... an = LCM;
this looks oddly similar maybe seen somewhere?
dividing lcm to both lhs and rhs
a1/lcm + a2/lcm + .... an/lcm = 1;
this becomes--> 1/x1 + 1/x2 .... 1/xn = 1;
this is famously seen in many NT inequality problems to break down complex inequalities further. but we are hooking for sequence so lets not dive there.
we have to break down 1 into number of fractions which sounds like Egyptian Fractions, there are many known tricks to dissolve fraction into further fractions . There is no restriction on n so best one right now looks
1/a = 1/a + 1/a*(a+1) . but this has a severe problem with our contraints which is output<=10^17 .but a*(a+1)==a*a {for large number}. a^2 grows rlly fast it surpases 10^17 in n<=50;
to optimise this you can for odd n try 1/a = 1/2*a + 1/3*a + 1/6*a ;
but this also overflows the contraint. so you have to look further.
as we look deeper into the optimisation case we just have to figure out to expand this from odd n to all n as it looks like under constraint.
try splitting the last number into 1/2*a + 1/2*a add appending into the sequence {let a be the last number in the sequence here its 6};
but we are getting one 1/2*a extra how do we deal with this? by induction::
let 1 = sum(1/xi) we can transform this to -->
1= 0.5 + 0.5*sum(1/xi).
0.5*sum(1/xi) == sum(1/2*xi); xi doubles as we go down the n and we get 0.5 extra.
the set becomes {2*x1, 2*x2, ...2*xn, 2}.
for n+1. the set becomes {4*x1, 4*x2 .... 4*xn, 2*2, 2}. and so on and so on.
we have already got x1 x2 x3 for the set which is {2,3,6}. the denominator sequence becomes {2,4,8,12,24,48...}. just doubling after 12.
atlast just take the lcm of total sequence and do : ai = lcm/xi.
follow my everyday blogs, youre going to witness my life ramming and unfolding infront of your eyes!!
© 2026 My Simple Blog