Hints for Contest 5 problems:
The idea and motivation behind these hints are that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also, open the hints in sequential order.
Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.
The benefit of knowing a partial solution rather than the complete solution is that you can work out the later stages of the problem yourself, thus improving your problem-solving skills.
TLDR; use the hints cautiously, if you start relying on them too much, it can hamper with your learning process.
Hint 1
First, we noticed that we can divide the rectangle into squares of 1 to maximize the cloth used and all of them have the same size. This implies that S = 1 is always an answer but we need to maximize S. So, can we do better?
Hint 2
What is the answer if
- Both L and B are equal?
- L is a multiple of B?
- B is a multiple of L?
Did you notice something strange?
Hint 3
What is the answer if
- L = X*A and B = Y*A where X, Y, and A are positive integers.
Hint 4
If you understand the previous hints then you know that S = A which implies a common factor of L and B. As we want to maximize the value of S, so we need to find the largest common factor. And you know how to find it efficiently.
Hint 1
Iterate over problem codes and consider only those who are only divisible by either A or B.
Not Hint Really!!
Let’s take a container and put the codes that are divisible by A. Then put codes that are divisible by B. Now, remove the duplicate codes from the container.
Interesting!
Can we find the minimum value of X for which this is true?
- X%A == 0 and X%B == 0
Is it somewhere related to prime factors? If we understand the previous hint then we know that prime factorization of X should have all the prime factors(not necessarily distinct) of A and B. But A and B have some common prime factors. As they need to be present at once. This implies:
- X_{min} = (A*B)/gcd(A,B)
Now, we know that we should not select the problem with code multiple to X. Right?
Hint 1
Brute force, As M, takes values from \{1,2,3,... \} and we need to check whether M and (N+M) is a square number. But it yields TLE.
Brute force with observation, As M, is a square so we should iterate over only squares, implies M takes values from \{1,4,9,16,...\} and we only need to check whether (N+M) is a square number. But it yields TLE too.
Hint 2
We have an equation like:
- N + M*M = X*X where N is given and M and X is unknown.
We can rearrange it and gets:
- N = X*X - M*M
- N = (X+M)*(X-M)
Can you understand what you need to do now?
Hint 3
Ya! You guessed right. We need to factor N. It can be done in O(N), but can we do better.
Hint 4
Let’s denote N as a product of two numbers u*v. Now, we know u and v both are the factors of N, and let assume that u and v both are greater than \sqrt N that implies u*v greater than N which is a contradiction. So, either u or v should be less than \sqrt N. So, we can use this information to generate factors of N in O(\sqrt N).
Hint 1
You can brutally solve the problem with the given constraints. First, find all primes less than N using either O(N*N) or O(N* \sqrt N). Then generate all semi-prime using them and again generate all possible sums that can be achieved using two distinct semiprimes. But what about higher constraints??
Hint 1
The subtask can be done by generating D and doing the process as mentioned but for bigger constraints it is impossible. Try printing the first few terms of D.
Hint 2
You can observe that there is a pattern that repeats itself. That means we find the N^{th} team of D in O(1) but which one??
There should be a pattern as D can only have 10 distinct values and every value depends on the sum of the previous two values.
There is also a way to find the N^{th} term of Fibonacci in O(logN).
Hint 3
If the size of D is N and the element left at the end of the process is X then
- If N = 1 then X = D_1
- If N = 2 then X = D_2
- If N = 3 then X = D_2
- If N = 4 then X = D_4
- If N = 5 then X = D_4
- And so on…
Did you notice anything?
Hint 4
Yes. There is a pattern here. For any N, X is given by 2^{floor(log2(N))}. Now we know which Fibonacci term we are looking for. That’s it. Problem solved.
Hint 5
Here, instead of matrix multiplication, we use a well-known fact, which states that the Fibonacci Numbers are Periodic under a given Modulo. As we are using 10 as modulo that’s why period comes to 60.
Hint 1
We can apply a brute force approach for every i from 1 to 100000 and use prefix sum technique to store answers for each i and j where i is 1 \le i \le 100000 and j is 1 \le j \le 5. But this will give TLE. Which part of this algorithm can be optimized?
Hint 2
Let’s think about the k = 1. What is the answer??
It is just finding out the number of primes between a range. And it can be done by??
Hint 3
We can apply Sieve to solve the previous problem but can we do better? Can we modify sieve to serve our purpose? Think!
Hint 4
Yes. Why not! We modify sieve to store the number of primes dividing a particular integer. Now, can you write the code?
Hint 1
As there are two options:
- He can not use the third operation at all which means the answer exists if both (N-1)\%X == 0 and (M-1)\%Y == 0 otherwise not.
- He used the operation which means the answer exists if both (N-2)\%X == 0 and (M-2)\%Y == 0 otherwise not.
Hint 1
If we apply brute force and try to generate all possibilities then this only passes the first subtask. We should do something smart here. Can we use the properties of xor?
Hint 2
The resultant string only has 1 at any position when only one of the respective positions in A and B have 1. But how can we use this information? Can we find the number of ones in the resultant string?
Hint 3
Yes. But there are many possibilities. Then what? What is the minimum and maximum bound on it?
Hint 4
We can find the minimum and the maximum number of 1’s that can appear in the resultant string by knowing the number of 1’s in A and B. If we try some more inspection then we find that number of 1’s in the resultant string is equal to minimum value possible + 2*x where x is a positive integer. But why? Think!
Hint 5
Now we know the different values of 1’s in the resultant array, what just left is combinatorics.
Hint 1
Brute force approach to check for each X from 2 to 10000, how many balls are required to make the gcd of the array equal to X. But this will give you TLE. What else do we do here?
Hint 2
Can we say that if each element is divided by X then each element should be divided by all the factors of X too? Can we use this information?
Hint 3
This means, we only need to check for primes, which can be done efficiently using a sieve.
Hint 1
The problem is forcing us to use primes. Can you see that too? But how? It is clear that we should use more than 2 primes except N = 3 where you can use two primes 2 and 3 to construct a valid sequence of \{2,6,3\}.
Hint 2
Hint 3
As the previous hint explains one of the approach but can not be used for large N. Can we do something better? Are you seeing any optimization on using prime numbers?
Hint 4
Yes. We have to use the prime numbers smartly. There are many ways to do that. One way is that we multiply the first two with one prime number, next to with next prime and so on. Again apply the same with different primes such first and last are multiplied by one of the prime, second and third multiplied by different prime and so on. Choose the two sets of primes wisely so you can be withing \le 10^9.
Hint 5
Preprocess the list of primes beforehand using a sieve.
False Hints
Mis-read the problem and generate different hints for the problem.
Invalid Hint 1
The problem is forcing us to use primes. Can you see that too? But how? It is clear that we should use more than 2 primes except N = 3 where you can use two primes 2 and 3 to construct a valid sequence of \{2,6,3\}.
Invalid Hint 2
Let’s try to make the sequence using 3 primes, \{p_1, p_2, p_3\}. What you find out?
Invalid Hint 3
No, we failed to do this in N=4 where we need more primes? Let’s try some more and find out if there is a pattern.
Invalid Hint 4
Yes. There is a pattern. For values of N\%3 == 0, \space 1, and 2 can be constructed by 3, 4, and 5 primes respectively.
Invalid Hint 5
For N=3*X, where X is a positive integer,
- p1*p3 + p1*p2 + p2*p3 + p1*p3 + p1*p2 + p2*p3 + …
Others can be done by:
- p1*p4 + p1*p2 + p2*p3 + p3*p4
- p1*p5 + p1*p2 + p2*p3 + p3*p4 + p5*p4
Hint 1
It is clear that we can not use the prefix-sum technique to get the answer as modulo is changing and the range is very high for modulo. So, how can we design an algorithm to fill our purpose? Can we use the fact that A_i is only 100?
Hint 2
Yes. But how? As every number can be written as a product of its prime factors, we use this to solve the question. We can use the prefix-sum technique over each prime less than 100. Can this be enough?
Hint 3
No, we need to use the fast modular multiplication technique to find the required answer.