Блог пользователя dificilcoder

Автор dificilcoder, история, 3 года назад, По-английски

How to arrive at the correct solution which solves for large input values?

Problem : Hard Compare...

Question

Given 4 numbers A,B,C and D. If AB > CD, print "YES" otherwise, print "NO".

Input
Only one line containing 4 numbers A,B,C and D (1≤A,C≤107) , (1≤B,D≤1012)

Output
Print "YES" or "NO" according to the problem above.

My Program

    #include <iostream>
    #define ll long long
    using namespace std;
     
    int main(){
         
      ll res1, res2, a, b, c, d;
      cin>>a>>b>>c>>d;
      res1 = 1;
      res2 = 1;
      for(int i=1;i<=b; i++){
          res1 = a % ((int)1e9+7) *  res1 % ((int)1e9+7);
      }
      for(int i=1;i<=d; i++){
          res2 = c % ((int)1e9+7) *  res2 % ((int)1e9+7);
      }
      
      cout<<(res1>res2 ? "YES" : "NO");
      return 0;
    }

TestCases

Input : 2887969 614604076030 8478041 209676100616
Answer : YES

Input : 8376260 70 8376259 70
Answer : YES

Input : 2 1 1 1
Answer : YES

Input : 1 7816997 1 1
Answer : NO

Issue with current program : I am not able to solve for large input values

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Take log both the sides and compare

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Since $$$A, B, C, D > 1$$$

      We have $$$AB > CD \Leftrightarrow log_k(AB) > log_k(CD)$$$ for $$$k > 1$$$

      You can also try $$$\frac{A}{C} > \frac{D}{B}$$$

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        but why the pow function doesn't work on that question??

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You can't use modulo before comparison.

          1 % (1e9 + 7) = 1
          (1e9 + 7) % (1e9 + 7) = 0

          but 1 isn't greater than 1e9 + 7.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        log functions will give you float values. Isn't it bad practice to compare floats?

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We have to check the given condition: a^b > c^d which means -> a^b/c^d >1 Let y= a^b/c^d >1 ---> y > 1 ---(1) take log both side : log(y) = b*log(a)-d*log(c) -----(2) From 1st equation we know y >1 --> log(y) > 0 --put this in 2nd equation.

We got: b*log(a) — d*log(c) > 0

C++ Code:

include<bits/stdc++.h>

using namespace std;

int main(){ long long a,b,c,d; cin>>a>>b>>c>>d;

b*log(a)-d*log(c)>0?cout<<"YES":cout<<"NO";

return 0;

}

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use 128-bit integers.