CGMATH Editorial

PROBLEM LINK:

Practice

Contest

Setter - Aghamarsh V

Editorial - Aghamarsh V

DIFFICULTY :

Cakewalk

PREREQUISITES :

Decimal to Binary Conversion

PROBLEM :

Given two positive integers we need to output which number is grater as on mathematics on mars. Maths on mars states that the number with more number of 1’s in its binary representation is grater than the other.

EXPLANATION :

  • Convert the given two numbers to their equivalent binary representations.
  • Count the number of one’s (1’s) in their respective binary forms.
  • State which of the two numbers is grater . If 1’s in the binary representation of one integer are grater than that of the other , it is said to be the grater of the two.
  • If the two integers’ binary forms have equal number of 1’s, they are said to be equal.

SOLUTION :

Setter’s solution can be found here

When you get to the full problem with 10^5 pairs of numbers up to 10^{18}, it may be be worth reconsidering your approach (depending on language). If you need around 60 div-mod operations to determine the Mars value of each number, potential total of 12 million operations or so, you could alternatively bite off more than one bit at a time and have a lookup for Mars values up to the appropriate power of 2. Generating the lookup array can be fast, so it can be quite big; I use 2^{15}.

My Python solution

It takes only 0.21 seconds for the last subtask. I don’t think so 12 million operations will be that big of a deal. O(tlog(n)) complexity is not that big an issue.

1 Like

@ay2306 Clearly the problem should have allowed T to go to 500000. :slight_smile:

@joffan as u said, the maximum number of operations would be 12 million. But these would be executed by the compiler within 1 second. If we consider 5*10^5 inputs,the same approach would have executed in around 0.9 to 1 second.

@aghamarsh8 OK, I was just multiplying 0.21s (as @ay2306 reported) by 5 to get it over 1 second and applying that to T. But only for fun.

//