Searching for Soulmates USACO 2022 January Contest, Silver

Problems and Contests
#1

I have solved this problem by myself in O(log(A)*log(B)).
When I check out the official solution, it appears that there exists a O(log(max(A,B)) algorithm.
Can someone tell me how to do it or some hints?
Thanks!

#2

It’s just a small modification to the model solution:

solution 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class SearchingForSoulmates {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        for (int t = Integer.parseInt(in.readLine()); t > 0; t--) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            long cow1 = Long.parseLong(tokenizer.nextToken());
            long cow2 = Long.parseLong(tokenizer.nextToken());
            long answer = Long.MAX_VALUE;
            long here_so_far = 0;
            long cow = cow1;
            for (int removed = 0; cow2 >> removed > 0; removed++) {
                long prefix = cow2 >> removed;
                while (cow > prefix) {
                    if (cow % 2L == 1L) {
                        cow++;
                        here_so_far++;
                    }
                    cow /= 2L;
                    here_so_far++;
                }
                long here = here_so_far;
                here += prefix - cow;
                here += removed;
                here += Long.bitCount(cow2 & ((1L << removed) - 1L));
                answer = Math.min(answer, here);
            }
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}
1 Like