0
\$\begingroup\$

There are 60 submissions from me to the very first beginner-freshman exercise at codeforces.com. Problem: 100985A - MaratonIME helps Pablito

I don't pass the tests because of Time limit exceeded (tle). I'm just thinking about the test can't be passed using java because of performance. But really, I think a crappy error in my algorithm is more likely. Or my approach is completely wrong. So feel free to comment my approach.

Excercise:

As is well known by any cultured person, rats are the smartest beings on earth. Followed directly by dolphins.

MaratonIME knows about the species hierarchy and uses this knowledge in it's regard. Usually, when they need some resource, they know it's always useful to have a smart rat available. Unfortunately, rats are not very fond of us, primates, and will only help us if they owe us some favour.

With that in mind, MaratonIME decided to help a little rat called Pablito. Pablito is studying rat's genealogy, to help with cloning and genetic mapping. luckily, the way rats identify themselves make the job much easier.

The rat society is, historically, matriarchal. At first, there were little families, each of which had it's own leading matriarch. At that time, it was decided that rats would organize themselves according to the following rules:

Each martiarch had an id number greater than one. Each of these ids were chosen in a way such that they would have the least amount of divisors possible. Each family member had the same id as the matriarch. The id of any newborn rat would be the product of its parents id's. For instance, the offspring of a rat with id 6 and another with id 7 is 42.

Pablito needs to know if two given rats have a common ancestor, but his only tool is the id number of each of the two rats, which is always a positive integer greater than 1 with no more than 16 digits. Can you help him?

Create a program that decides if a pair of rats have some common ancestor.

Input The input begins with a positive integer t ≤ 105, the number of test cases.

After that, follows t lines, each with two integers ai e bi identifying two rats.

Every rat's id is a positive integer greater than 1 and with no more than 16 digits.

Output For each test case, print "Sim" if the rats ai and bi share a common ancestor and "Nao" otherwise.

My latest approach before using multiple threads. (Yeah, TLE there as well).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class A {
    public static void main(String[] args) throws IOException{
        BufferedReader scan = new BufferedReader (new InputStreamReader(System.in));
        int amountTests = Integer.parseInt(scan.readLine());

        for (int i = 0; i<amountTests; i++){
            String[] tmp = scan.readLine().split(" ");
            long l1 = Long.parseLong(tmp[0]);
            long l2 = Long.parseLong(tmp[1]);
            if (l1 < l2){
                searchPrims(l1,l2);     
            }else{
                searchPrims(l2,l1);     
            }
        }
    }

    static void searchPrims(long n, long n2){
        int d = 2;
        while (true){
            if(n%d==0){
                if(n2%d==0){
                    System.out.println("Sim");
                    return;
                }
                n/=d;
                d = 2;
            }
            else if(n==1){
                System.out.println("Nao");
                return;
            }
            else{
                if(d==2)
                    d=3;
                else{
                    d+=2;
                }
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Study Greatest Common Divisor (GCD) methods. You do not need to know all the prime factors of the two rats, you just need to know if they have any factors in common. \$\endgroup\$ – rossum Jul 5 '17 at 14:33
1
\$\begingroup\$

Improving what you have

                d = 2;

Part of the problem is this line. Each time you find a matching divisor, you restart from the beginning. This isn't necessary. The code works without this. Once you've removed all the 2s, nothing will put them back.

    static void searchPrims(long n, long n2){
        int d = 2;
        while (true){
            if(n%d==0){
                if(n2%d==0){
                    System.out.println("Sim");
                    return;
                }
                n/=d;
                d = 2;
            }
            else if(n==1){
                System.out.println("Nao");
                return;
            }
            else{
                if(d==2)
                    d=3;
                else{
                    d+=2;
                }
            }
        }
    }

I would find this easier to read as

    static boolean searchCommonFactors(long n, long n2){
        for (int d = 3; n >= d; d += 2) {
            if (n % d == 0) {
                if (n2 % d == 0) {
                    return true;
                }

                do {
                    n /= d;
                } while (n % d == 0);
            }
        }

        return n % 2 == 0 && n2 % 2 == 0;
    }

This returns a boolean value instead of printing. So we would have to print outside it. Something like

    static void printAnswer(boolean answer) {
        System.out.println(answer ? "Sim" : "Nao");
    }

This way we can split up the returns more naturally. Also, this would be reusable in other problems with different output requirements.

This way we don't keep checking if n2 is divisible by a factor. We check once. If it is, we return immediately. If it isn't, we know it never will be. We discard all of that factor to reduce the maximum size of d.

Putting the even check at the end takes the special behavior out of the loop. This way we can simplify the loop iteration.

We could get back some efficiency by putting that check first and then removing all the 2s from n.

        if (n % 2 == 0 && n2 % 2 == 0) {
            return true;
        }

        while (n % 2 == 0) {
            n /= 2;
        }

Alternative approaches

Your approach basically factors the smaller number. If one of its factors is also a factor of the other number, you say that they are related.

A more efficient approach might be to use the Euclidean algorithm to see if the two numbers have a greatest common divisor (GCD) larger than 1. So you'd say something like

    printAnswer(gcd(l1, l2) > 1);

to get the answer.

A little searching finds a gcd implementation:

public static long gcd(long a, long b) {
    while ( 0 != b ) {
        long temp = a;
        a = b;
        b = temp % b;
    }

    return a;
}

There's a relatively elegant recursive solution.

public static long gcd(long a, long b) {
    return (b == 0) ? a : gcd(b, a % b);
}

But the iterative version should normally be faster.

I would expect this to be faster than your code, as it reduces a and b to the greatest common factor rather than searching out every factor of a only to find that none of them match.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy