Hi friends,please help me solve this if you have some spare time :)
a[1]-2*x[1]+x[n]=m;
a[2]-2*x[2]+x[1]=m;
a[3]-2*x[3]+x[2]=m;
. . .
a[n]-2*x[n]+x[n-1]=m;
here the array a is given and the constant m is also given,we have to find out the values of all the xi's in my approach i applied binary search on the value of x[n]..so lets suppose the assumed value of x[n]=mid then after solving the equation if i will get the value of x[n]>mid then i will reduce the mid,else increase the mid till the value of x[n] found out==mid...the problem here is that i have to find out an integral solution of the equations(if it exists)..so while solving the equations if some x[i] comes out to be a fractional value then we cannot proceed further with that value of mid..so if this happens then the current mid isnt a solution..now what should be the next mid value?increase/decrease or adjust it differently to converge to an integer solution(if it exists)?
last question:is there some other way in which this problem can be solved?
Auto comment: topic has been updated by Ryan22oct (previous revision, new revision, compare).
I think this problem definitely has mathematics solution, but it will be a bit hard to find it. If x can't be too big integer, you can just try every x (for(int x = 1; x <= ...; ++x))
Since $$$a_i=2x_i-x_{i-1}+m$$$, this means $$$2^{i-1}a_i=2^ix_i-2^{i-1}x_{i-1}+2^{i-1}m$$$, so adding for $$$i=1$$$ to $$$i=n$$$ gives $$$a_1+2a_2+4a_3+\cdots+2^{n-1}a_n=(2^n-1)x_n+(2^n-1)m$$$, so you can solve for $$$x_n$$$.
i appreciate the method which u told,but the problem is that the value of n goes till 200000 so here this method is not feasible..let me just tell you the problem on which i am stuck on..https://codeforces.net/problemset/problem/2038/B..in this problem we can see that if we can achieve a value of k then k-1 is also achivable so we can use binary search on answer here..so the equations which will be formed are the ones which are written in the blog above and m is the variable on which i am applying the binary search...so please can you guide me how to solve this question using my approach..thank you
The idea is as follows. Let's solve a system of equations modulo some large prime (e.g. $$$mod = 10^9 + 7$$$). That is, for example, the equations will be $$$(a_i - 2x_i+ x_{i - 1}) \% mod = m \% mod$$$. Such a solution will pass as bronze_coder wrote. Then note that if the original system has an integer solution, then our system of modulo equations will also have a solution. On the other hand, since we are looking for solutions that $$$0 \leq x_i < mod$$$, then it is enough just to check that the found solution fits. If $$$|x_i| < 10^{18}$$$, then we can solve the system by another modulus (of the order of $$$10^{18}$$$) or use two different moduli and then recover the answer by $$$CRT$$$.
This idea was used to solve a problem from a recent $$$ICPC$$$ problem
problem
solutions (sorry but only in Russian)