Contest 1 - Hints to Problems [OFFICIAL]

CodeChef-DSA-learners
,
1

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
2

hints for multiple of 3 please

4 Likes
3

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
5

Try in O(n) by taking current indices !

1 Like
6

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
7

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
8

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
9

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
11

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

3 Likes
12

got it… thanks

2 Likes
13

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

3 Likes
14

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

1 Like
15

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

1 Like
16

did you solve laddu problem?

1 Like
17

if yes then please share the approach .

1 Like
18

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

4 Likes
19

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

1 Like
20

can u post it here.

1 Like
21

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
22

@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