Ryan22oct's blog

doubt related to solving a system of n linear equations using binary search.
By Ryan22oct, history, 26 hours ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Ryan22oct (previous revision, new revision, compare).

→ Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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))

→ Reply
»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/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

    → Reply
    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply