usernameson's blog

By usernameson, history, 8 years ago, In English

Introduction

This post is about div 2 question A from Round 406 http://codeforces.net/problemset/problem/787/A. Coding the solution is easy however figuring out why this solution works requires a bit more thought.

The Situation

The question boils down to having four fixed integers a, b, c, d all between 1 and 100 and finding the smallest non-negative integer pairs m, n such that b + an = d + cm. A solution that works is to brute force all integer pairs in [0, 200] × [0, 200]. (The editorial says sticking with pairs [0, 100] × [0, 100] is sufficient but the proof in this case given is simpler).

The Technique Overview

If we want to brute force enough pairs to either find a solution or conclude that one does not exist we need to know how many pairs are enough. It turns out a technique in number theory can help us. The idea assume we have a solution to our equation and use it to generate more solutions. Usually in number theory this is used to show if a particular equation has one solution it has infinitely many and the next step is to find a single solution for the equation and then conclude it has infinitely many. In our case we assume we have a large solution and show it can be used to generate a smaller solution.

The Technique in Action

Assume we have a pair (n0, m0) such that b + n0a = d + m0c. Let's perturb our n0 by adding an integer h to it. Then we have b + (n0 + h)a = d + m0c + ha. We would like to combine the last two terms on the right hand side so we let h = tc for some integer t. Then we have b + (n0 + tc)a = d + (m0 + ta)c. Thus given a solution (n0, m0) the pair (n0 + tc, m0 + ta) is another solution for all integers t.

Next we assume we have a solution (n0, m0) where n0 > 200 and show the smaller solution (n0 - c, m0 - a) is positive. This allows us to restrict our search to solutions to those with values between 0 and 200 inclusive. First we note since c ≤ 100 we have n0 - c > 100. Thus the first term is positive. For the second term we note since this new pair is a solution we have b + (n0 - c)a = d + (m0 - a)c. Since c > 0 it is sufficient to prove (m0 - a)c > 0. Also since a > 0, b > 0 and n0 - a > 100 we can conclude the left hand side of the equation is greater than 100. Thus d + (m0 - a)c > 100. Finally since d ≤ 100 we conclude (m0 - a) > 0 as required.

Did I figure all this our during the contest?

I did not. Once I could not see a simple way to generate the answer I decided to brute force. I suspected something like what I described above would occur and brute forced all pairs in [0, 999] × [0, 999]. Fortunately for me doing this worked. My contest submission is below.


#include<algorithm> #include<vector> #include<iostream> #include<utility> #include<string> #include<set> #include<queue> using namespace std; int main(){ int a,b,c,d; cin>>a>>b>>c>>d; for(int i=0; i<1000; i++){ for(int j=0; j<1000; j++){ if(b+a*i==d+c*j){ cout<<b+a*i; return 0; } } } cout<<-1; return 0; }
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the helpful post!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How will i determine the terminating point of the loop?? Please explain.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For this question in the section "The technique in action", I show if there is a solution with n0 > 200 we can find a smaller solution that is positive so we can terminate the outer loop at 200. A similar argument holds to show we can terminate the inner loop at 200. My code terminates the loops at 1000 because that it what I submitted during the contest and I guessed that 1000 was large enough.