Contest 1 - Hints to Problems [OFFICIAL]

Hints for Contest 1 problems:

The idea and motivation behind these hints is 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.

  1. Lapindromes - LAPIN
Hint 1

Store how many times the letter ‘a’ comes on the left side, how many times the letter ‘b’ comes on the left side and so on, in an array. Do the same for the right side too. Then compare.

  1. Factorial - FCTRL
Hint 1

2s and 5s in prime factorisation of n! matter.

Hint 2

Count only the number of 5s in prime factorisation of n!

Hint 3

\left \lfloor{\frac{n}{5}}\right \rfloor gives the number of numbers \leq n, that have at least one 5 in their prime factorisation, \left \lfloor{\frac{n}{5^2}}\right \rfloor gives the number of numbers \leq n, that have at least 5^2 in their prime factorisation, generalise this idea.

  1. Smart Phone - ZCO14003
Hint 1

The final answer is the form A \times B, where A is the price of the app fixed and B is the number of people willing to buy at that price. We’ve seen people get WA because they only maximise A or only maximise B. (Eg. I will make price 1 so everyone will buy, or I will make price very high, but very few people will buy)

Hint 2

Sort all the people by the budgets

Hint 3

If the sorted budget array looks like this = [2, 10, 15, 23]
Then trying to fix the price at 10 is always better than trying to fix the price at 9, because in both cases exactly 3 people will buy at the given price.
That is you only need to try some candidate solutions and not all of them.

  1. Multiple of 3 - MULTHREE
Hint 1

Find a pattern and beware of an incorrect approach, i.e (d_0 + d_1 + d_2 + … + d_n) \mod 10 \neq (d_0 \mod 10 + d_1 \mod 10 + d_2 \mod 10 + … + d_n \mod 10)

Hint 2

d_2 = (d_0 + d_1) \mod 10, d_3 = 2(d_0 + d_1) \mod 10, d_k = 2^{k - 2}(d_0 + d_1) \mod 10

Hint 3

2^1 \mod 10 \equiv 2, 2^2 \mod 10 \equiv 4, 2^3 \mod 10 \equiv 8, 2^4 \mod 10 \equiv 6, 2^5 \mod 10 \equiv 2, 2^6 \mod 10 \equiv 4, … can see the cycling nature of powers of 2 under modulo 10

64 Likes

hints for multiple of 3 please

4 Likes

for zco14003, i tried the same way, but i am getting TLE for main task. my work is done in o(n^2).
because i am traversing on all the elem, … How to reduce time complexity.!?

3 Likes

Try in O(n) by taking current indices !

1 Like

i traversed only over indices like this
for (int i = 0; i < size; i++){
temp = arrLL.get(i);
for (int j = i+1; j <size; j++){
temp += arrLL.get(i);
}
if (temp > maxans) maxans = temp;
}
but not getting how to reduce it in o(n)

1 Like

The hint for the question MULTHREE is really good and compresive.
I like the way you give hint thus we also have to make our logic and understand the question logically.

4 Likes

umm i just did binary search and used max function to check the revenue

it works fine on my ide but its giving me WA on codechef’s ide :frowning:

2 Likes

for (int j = i+1; j <size; j++){
temp += arrLL.get(i);
}

You could write this part in some other way which would reduce your time complexity to O(n). Think about it.

2 Likes

Look at the pattern of digits.After some interval it starts to ___.

3 Likes

got it… thanks

2 Likes

in canvas problem,
3
8 3 6
testcase should give ans 1 na !?

3 Likes

Answer will be 2 as car I and car II are moving at their maximum speed.

1 Like

one approach is to sort the given array. and set the count to n. after every iteration decrease the count.

1 Like

did you solve laddu problem?

1 Like

if yes then please share the approach .

1 Like

@gulshan_yadav
There is no specific approach for this problem ig . Brute force worked for me

4 Likes

@lost_boy when i take input in string it shows me error please help me .

1 Like

can u post it here.

1 Like

If anyone is having difficulty solving the problems of Code-Chef DSA Series-1 problems, you can refer to the this post: Code-Chef DSA Series-1 Editorial.

P.S. But before referring the above post make sure that you have tried everything for solving a problem.

6 Likes

@lost_boy12
#include
using namespace std;
#include<bits/stdc++.h>
void solve(){
int n;
cin>>n;
string ori;
getline(cin,ori);
string cont;
getline(cin,cont);
string contest=cont.substr(12);
int rank=stoi(contest);
string top;
getline(cin,top);
string bug;
getline(cin,bug);
string b=bug.substr(10);
int ra=stoi(b);
string host;
getline(cin,host);
int total=300+(20-rank)+300+ra+20;
cout<<total<<endl;

}
int main(){

int t;
cin>>t;

while(t--){
	solve();
	
}

}

1 Like