 # Contest - 5 Hints to the Problems [OFFICIAL]

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

• 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

• 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

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.

4 Likes

Hey I can’t find the official hints for contest 4. Someone provide the link please

Hey,
We are yet to post it as it is work in progress. We will post it soon.

In problem 10 as A0,A1,…,An-1 are pairwise distinct ,but in Hint5 the numbers p1p3, p1p2, p2p3 are repeating , so I feel this is wrong, can someone please explain where I have misunderstood the Hint5

In the FIBEASY question, i think the hint for pow(2,floor(log2(N))) has some issues.
My approach : https://www.codechef.com/viewsolution/33177791
This fails in the second subtask.

Using bitwise shift gives an AC.
https://www.codechef.com/viewsolution/33177709

Question: FIBEASY
Query : I’m getting NZEC despite getting the code to work correctly (on my system) (I took the help of the hints, and I’m pretty sure it’s correct)

So, can anyone pls see my code and maybe tell me what’s wrong?

Thanks for pointing out. Updated.

@real_god Added one more hint to the problem. That will help you. Also, your code is failing for large values of N, as for those X will be large, so you should use either the observation mentioned in the Hint \space 5 or use Matrix Exponentiation

1 Like

In CHMOD there could be more than one segment of a kind with same left and right value. what to do in that case?

for ex. if 1567819567 is the array and
if left is 1 and right is 7 then there are more than 1 segment. what to do then?

Yes I got the same issue.

use pow( 2,floor ( log2 ( (double) N) ) )
This got my issue sorted

Hello,
I am Solving chef and squares,
Here is my Link to my solution: https://www.codechef.com/viewsolution/33629730

My approach was:
The perfect squares are 1,4,9,16,25,36,49,… and so on. And difference b/w these squares is 3,5,7,9,11,13,15… and so on. So I got to knew that N must be odd in-order to solve as difference are odd. After that calculated the sum of odd series and got the first term, later subtracted with N in order to get other term.
a^2 - b^2 = N
a^2 = N + b^2( N must be odd in-order to reach to a^2 as seen in sequence of differences).
Reason for calculating the odd series sum is:-
For example if N = 7
(3,5,7,9,11,…) sequence of difference of squares.
a^2 = 7 + b^2
and since b^2 is sum of previous terms we can get a link by backtracking.
a^2 = 16, b^2 = 9
16 = 9 + 7
9 = 5 + c^2
c^2 = 3 + d^2
d^2 = 1 + 0

So we wind by back tracking we get
16 = 9 + 7
9 = 5 +4
4 = 3 + 1
1 = 1 + 0

N = 7 (4 term in odd series) and did a = N*N and subtracted it N to get b.
a = 4 * 4
b = 16 - 7 (a - n)

which is sum of odd series so that’s why I calculated the sum of odd series. And later on found the term and calculated the sum based on term. and subtracted with N in-order to get other term(required term) for solution. But I don’t know where it is failing. Can you tell where am I failing please.

2 Likes

i think pow() function doesn’t work for type long long int

Whats wrong with this solution https://www.codechef.com/viewsolution/34038553 in question Chef and Semiprimes

hy still getting wa in second subtask. can you please tell me what’s wrong. link to my submission is:- https://www.codechef.com/viewsolution/34477988

Hey I tried Chef and semi primes getting WA
https://www.codechef.com/viewsolution/34637926
Can someone help??

Resolved. I missed the fact that semi prime should be product of 2 primes

I am trying to solve the KPrime question in following way, can anyone please tell whats wrong in this
https://www.codechef.com/viewsolution/35583569

I removed vector since we are just interested in count, thus maintaing a vector only and still getting WA https://www.codechef.com/viewsolution/35588236