=>Try Yourself First. For help Scroll Down .
Hi Everyone. Appears with a new post which is about the tutorial of an interesting problem on URI Online Judge . This judge is pretty good for the beginners to get addicted with CP. While solving this problem I was stuck about a day on it. Finally with the help of a really great solver I come up with the solution . This is one of the lowest solved problem in URI . I severally searched for solutions on the net but could not find anything satisfactory.That's why I guess it would be better to keep a resource for this problem after solving this.
Anyway , let's start . Hope you will enjoy it.
Problem Link: URI - 1705 - Binary Lover
Problem Clearance: In this problem you will be given a number . You need to find the lowest binary number that is evenly divisible by the given number. Suppose, for input 143 the answer will be 1001 because 1001 / 143 = 7 which is evenly divisible .
Pre-requisite: Prime Factorization, Recursion, Array Compression / Mapping, Binary Conversion .
⏩ Before moving into details think once again with the small hint that is stated as Pre-requisite .
Details :
Observation 1: If you read the question carefully then you obviously noticed that the resultant number could be off 12 digit only. Which means you have to output a Binary Number which is maximum off 12 digit and that is 111111111111 .So what you need to do is to generate all the binary starting from 1 to 111111111111 . It will take about 12 x 4096 operations in total . 4095 is the number whose binary is 111111111111 . You can generate those numbers through recursion or iterative process .
Half your work has already been done.
Approach 1: So what do you think ? Just scan the input number and run a loop through 4096. If any of the Binary representations from 1 to 4095 ( Result is greater than 0 ) is divisible by input number then print answer . Yay !!!!!!!
Sorry to say . You're moving completely wrong way. Why ??
This solution will give you the famous Time Limit Exceeded ( TLE ) . Check out the total input numbers. It is 2*10^5*4096 = 819,200,000 operations ( almost 8 Seconds ).
Approach 2: So after having a TLE verdict I started to think how to reduce the run time.I think, well why don't we just make 16 blocks and put first 256 elements out of 4096 elements into the first block, the second 256 elements into second block and so on. Then we just have to run a loop from 0 through 256 and check whether any of the ith element of all 16 blocks are divisible by Input? So our complexity will be 256*2*10^5 = 51,200,000 operations .
But here is also a disappointing part waiting for me. The complexity of if - else is always O(1) . So for 16 if-else ( which we tried to check for ith element of all 16 block ) it will take 16 operations . And along with that we have run a loop about 256 . So the complexity is almost same as stated in Approach 1. Time Limit Exceeded again . 😞
Approach 3: After getting several TLEs , I was looking for help. Then one of the finest solver named Jamil Siam ( respect bro ) come forward to help me . So, here I am trying to explain the correct approach according to my solving algorithms .
The first thing is after taking inputs we are not allowed to do operations above 500 . That's why you need to find an approach to print the answers using some approach which will take about O(1) , O(sqrtN) or O(log2N) complexity . Which clearly states that, you need to do something like Pre-calculations. My approach was about O(log2N) .
⏩ Now try one more time before reading the rest of the part . Only trying is real you know.
So, we need to find which number from the binary list is divisible by the given number. What if we have the list of all numbers that can divide the ith binary representation of the list (i.e. List of binary representation of 1 - 4095 ). Won't it be better ?? We can answer the query in O(1) or O(log2( 76037) ) [ Here 76037 is the total number of divisors for all Binary Numbers in the list ] . So then our complexity will be either O(number of inputs) or O(number of inputs * log2(76037) )which far less than 10^8 operations .
For example, suppose the current Binary Number is 100 .
So the it's divisors are = 1, 2, 4, 5, 10, 20, 25, 50, 100 .
Now we can make a notation of each divisor i.e. PRESENT[1] = 100, PRESENT[2] = 100 .... PRESENT[100] = 100.
Isn't it cool ?? Yay!!! We found a way to reduce Run Time .
So the question is how to find out all the divisors of a Binary Number ??
i) At first you need to generate primes upto 10^6 . Why ?? Because sqrt(10^12) = 10^6 . So, it's pretty enough for our calculation to calculate primes upto 10^6 .
ii) Then for each Binary Number in the list ( say X ) we will do prime factorization of X . Does it seems weird to you? I mean do you think it will give you TLE in worst case ?
No. It does not. Why ?? Because most of the number is divisible by primes less than 10^6 in the list. There are 664579 primes upto 10^6 . And there are only 219 primes among the Binary list you have generated . And you know no numbers can have divisors greater than it's Square Root value. So you can be so sure that it won't cost so much what you are thinking .
iii) Along with factorizing a number you should store which of the primes are factorizing the number ( say X ) and how many time they are needed to factorizing X . That means you have to store frequency of a Primes along with storing factoring Primes.
iv) Now using those information you have to generate all possible numbers you can . Because they will be the divisor of the number . For example , you have the number 100 . The Prime Factors are:
2, 2, 5, 5 . So the divisors will be: 1( by default ) , 2, 4, 5, 10, 25, 20, 50, 100 . You can do this by recursively . It's kind of a 0-1 knapsack technique. So, while generating divisors you just put them into a STL: MAP ( search on the net about it ) where the key will be divisor and the value will be the Binary Number itself .
v) Now while you will get the number as input you just consider it as a key of map. Just check whether this key has any value or not ? If it has any value then print this or print -1 .
Gotchas : Are you getting Wrong Answer ? Then you must do some mistake in your code. Check your Sieve of Eratosthenes again . Check your Binary Generation function again. Then try seeing Factorization technique you used . Well , then Divisor Generating technique again . Did you consider 0 (ZERO) as a valid answer ? If yes then please remove 0 (ZERO ) from the Binary List you generated .
Well, If these thing is OK then you may did an error while storing values into the MAP . You are said to find out the least number that is divisible by input number. So, while storing a value you need to put the minimum of two number . Got it ??
If you are still getting Time Limit Exceeded then please check your recursions ( if you did ) whether they fall into an infinite loop or not . Don't run the complete Prime List . Instead , you should run it through Square Root of the Binary Number .
I think you have solved the problem by now . Below the code is given you can see whether you did any mistake .
Code: URI - 1705 - Binary Lover Solution .
=>Leave a comment for any kinds of Hugs and / or Bugs. Thank you for reading .
Hi Everyone. Appears with a new post which is about the tutorial of an interesting problem on URI Online Judge . This judge is pretty good for the beginners to get addicted with CP. While solving this problem I was stuck about a day on it. Finally with the help of a really great solver I come up with the solution . This is one of the lowest solved problem in URI . I severally searched for solutions on the net but could not find anything satisfactory.That's why I guess it would be better to keep a resource for this problem after solving this.
Anyway , let's start . Hope you will enjoy it.
Problem Link: URI - 1705 - Binary Lover
Problem Clearance: In this problem you will be given a number . You need to find the lowest binary number that is evenly divisible by the given number. Suppose, for input 143 the answer will be 1001 because 1001 / 143 = 7 which is evenly divisible .
Pre-requisite: Prime Factorization, Recursion, Array Compression / Mapping, Binary Conversion .
⏩ Before moving into details think once again with the small hint that is stated as Pre-requisite .
Details :
Observation 1: If you read the question carefully then you obviously noticed that the resultant number could be off 12 digit only. Which means you have to output a Binary Number which is maximum off 12 digit and that is 111111111111 .So what you need to do is to generate all the binary starting from 1 to 111111111111 . It will take about 12 x 4096 operations in total . 4095 is the number whose binary is 111111111111 . You can generate those numbers through recursion or iterative process .
Half your work has already been done.
Approach 1: So what do you think ? Just scan the input number and run a loop through 4096. If any of the Binary representations from 1 to 4095 ( Result is greater than 0 ) is divisible by input number then print answer . Yay !!!!!!!
Sorry to say . You're moving completely wrong way. Why ??
This solution will give you the famous Time Limit Exceeded ( TLE ) . Check out the total input numbers. It is 2*10^5*4096 = 819,200,000 operations ( almost 8 Seconds ).
Approach 2: So after having a TLE verdict I started to think how to reduce the run time.I think, well why don't we just make 16 blocks and put first 256 elements out of 4096 elements into the first block, the second 256 elements into second block and so on. Then we just have to run a loop from 0 through 256 and check whether any of the ith element of all 16 blocks are divisible by Input? So our complexity will be 256*2*10^5 = 51,200,000 operations .
But here is also a disappointing part waiting for me. The complexity of if - else is always O(1) . So for 16 if-else ( which we tried to check for ith element of all 16 block ) it will take 16 operations . And along with that we have run a loop about 256 . So the complexity is almost same as stated in Approach 1. Time Limit Exceeded again . 😞
Approach 3: After getting several TLEs , I was looking for help. Then one of the finest solver named Jamil Siam ( respect bro ) come forward to help me . So, here I am trying to explain the correct approach according to my solving algorithms .
The first thing is after taking inputs we are not allowed to do operations above 500 . That's why you need to find an approach to print the answers using some approach which will take about O(1) , O(sqrtN) or O(log2N) complexity . Which clearly states that, you need to do something like Pre-calculations. My approach was about O(log2N) .
⏩ Now try one more time before reading the rest of the part . Only trying is real you know.
⏬⏬⏬⏬⏬⏬⏬
So, we need to find which number from the binary list is divisible by the given number. What if we have the list of all numbers that can divide the ith binary representation of the list (i.e. List of binary representation of 1 - 4095 ). Won't it be better ?? We can answer the query in O(1) or O(log2( 76037) ) [ Here 76037 is the total number of divisors for all Binary Numbers in the list ] . So then our complexity will be either O(number of inputs) or O(number of inputs * log2(76037) )which far less than 10^8 operations .
For example, suppose the current Binary Number is 100 .
So the it's divisors are = 1, 2, 4, 5, 10, 20, 25, 50, 100 .
Now we can make a notation of each divisor i.e. PRESENT[1] = 100, PRESENT[2] = 100 .... PRESENT[100] = 100.
Isn't it cool ?? Yay!!! We found a way to reduce Run Time .
So the question is how to find out all the divisors of a Binary Number ??
i) At first you need to generate primes upto 10^6 . Why ?? Because sqrt(10^12) = 10^6 . So, it's pretty enough for our calculation to calculate primes upto 10^6 .
ii) Then for each Binary Number in the list ( say X ) we will do prime factorization of X . Does it seems weird to you? I mean do you think it will give you TLE in worst case ?
No. It does not. Why ?? Because most of the number is divisible by primes less than 10^6 in the list. There are 664579 primes upto 10^6 . And there are only 219 primes among the Binary list you have generated . And you know no numbers can have divisors greater than it's Square Root value. So you can be so sure that it won't cost so much what you are thinking .
iii) Along with factorizing a number you should store which of the primes are factorizing the number ( say X ) and how many time they are needed to factorizing X . That means you have to store frequency of a Primes along with storing factoring Primes.
iv) Now using those information you have to generate all possible numbers you can . Because they will be the divisor of the number . For example , you have the number 100 . The Prime Factors are:
2, 2, 5, 5 . So the divisors will be: 1( by default ) , 2, 4, 5, 10, 25, 20, 50, 100 . You can do this by recursively . It's kind of a 0-1 knapsack technique. So, while generating divisors you just put them into a STL: MAP ( search on the net about it ) where the key will be divisor and the value will be the Binary Number itself .
v) Now while you will get the number as input you just consider it as a key of map. Just check whether this key has any value or not ? If it has any value then print this or print -1 .
Gotchas : Are you getting Wrong Answer ? Then you must do some mistake in your code. Check your Sieve of Eratosthenes again . Check your Binary Generation function again. Then try seeing Factorization technique you used . Well , then Divisor Generating technique again . Did you consider 0 (ZERO) as a valid answer ? If yes then please remove 0 (ZERO ) from the Binary List you generated .
Well, If these thing is OK then you may did an error while storing values into the MAP . You are said to find out the least number that is divisible by input number. So, while storing a value you need to put the minimum of two number . Got it ??
If you are still getting Time Limit Exceeded then please check your recursions ( if you did ) whether they fall into an infinite loop or not . Don't run the complete Prime List . Instead , you should run it through Square Root of the Binary Number .
I think you have solved the problem by now . Below the code is given you can see whether you did any mistake .
Code: URI - 1705 - Binary Lover Solution .
=>Leave a comment for any kinds of Hugs and / or Bugs. Thank you for reading .
No comments:
Post a Comment