Hello guys :) <br> <br>↵
↵
Competitive coding wing of GEEKHAVEN IIIT Allahabad is organising a contest on hackerearth on saturday 12th august. The contest is mainly centred for second year students, although I hope that everyone will be able to enjoy the problem set. The contest is prepared by the members of the wing. <br> <br>↵
↵
It has Balanced problemset with some interesting problems to simulate the grey cells and great to start the weekend.↵
<br><br>↵
↵
<strong>The link of the contest is — https://www.hackerearth.com/challenge/college/codemania-20/ </strong><br><br>↵
↵
The contest duration is 24 HRS. <br><br>↵
↵
I hope for an huge participation. :) <br><br>↵
↵
<strong> UPD: (EDITORIAL) </strong> <br><br>↵
↵
###### 1. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/cross-the-stairs/↵
↵
<spoiler summary="hint">↵
You can simply brute force for the solution. one by call friend for each level and then compute the answer for that call. Out of all possible solution select the maximum one. <br>↵
###### http://paste.ubuntu.com/25305339/ <br>↵
###### http://paste.ubuntu.com/25305411/↵
</spoiler>↵
↵
###### 2. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/honey-bees/↵
↵
<spoiler summary = "hint">↵
the problem was simple brute force. There were two cases to handle, when the second index is odd, and when second is even for both type of queries. Just make a big enough picture, and it will help you in understanding the solution. <br>↵
###### http://paste.ubuntu.com/25305429/↵
</spoiler>↵
↵
###### 3. https://www.hackerearth.com/problem/algorithm/modern-game/↵
↵
<spoiler summary = "hint">↵
You will have to convert the required ans into binary format. Then do dynamic programming over all bit positions. for every position you can either put one, or zero. This is true for all three numbers. At every point check whether putting these bits will give you a one. This information can be used to set a valid flag. In the end if flag is set and there is no carry for summation of the three numbers, then we have our solution. <br>↵
###### http://paste.ubuntu.com/25305466/↵
</spoiler>↵
↵
###### 4. https://www.hackerearth.com/problem/algorithm/an-excursion-in-mathematics/↵
↵
<spoiler summary = "hint">↵
You can use the constraints to solve this problem. Let us loop over the value of z for example. Then we have 3 equations in two variables. This makes the equation simple to solve. Then solve the equations to find the roots.↵
They are — x = sqrt(a — sqrt(2 b — a^2))/sqrt(2), y = sqrt(sqrt(2 b — a^2) + a)/sqrt(2) <br>↵
###### http://paste.ubuntu.com/25305520/ ↵
</spoiler>↵
↵
###### 5. https://www.hackerearth.com/problem/algorithm/coin-toss/↵
↵
<spoiler summary = "hint">↵
Note that the ways of tossing and of H and T have a bijection with each other.↵
↵
Let X(n),Y(n),Z(n) represent the allowable sequences ending with 2,1 and 0 consecutive tails respectively.↵
↵
We have:↵
↵
X(n)=Y(n-1)...(i)↵
Y(n)=Z(n-1)...(ii)↵
The above two results can be shown by considering that we can append a tails to the end of the n-1 length chain to create an n length chain with one more consecutive tail at the end.↵
↵
Now let F(n) denote the total number of acceptable sequences.↵
↵
Now, we have:↵
↵
Z(n)=F(n-1)...(iii)↵
(By appending an heads to the end of any acceptable sequence and removing heads from end of any (acceptable) sequence ending with tails ... bijection can be proved)↵
↵
Also (obviously):↵
↵
F(n)=X(n)+Y(n)+Z(n)↵
↵
Thus, we can show:↵
↵
F(n)=F(n-1)+F(n-2)+F(n-3) ...by (i), (ii), (iii)↵
↵
We can easily compute this in log(n) complexity using Matrix Exponentiation.↵
↵
solution link : https://paste.ubuntu.com/25305080/↵
↵
Time complexity : O(T*log(n))↵
↵
java solution : http://paste.ubuntu.com/25305535/↵
</spoiler>↵
↵
###### 6. https://www.hackerearth.com/problem/algorithm/ben-and-the-omnitrix/↵
↵
<spoiler summary = "hint">↵
prerequisite : Lowest Common ancestor , DFS↵
↵
For each 1 ≤ i ≤ n and 0 ≤ j ≤ log(n), store the minimum 20 values in the path from U(vertex) i to its 2^j-th parent in an array.↵
Now everything is needed is: how to merge the array of two paths? ↵
You can keep the these 20 values in the array in increasing order and for merging, use standard merge function which will work in . And then delete the extra values (more than 20).↵
Do the same for a query (just like the preprocess part) and you will get the list. ↵
↵
solution link : http://paste.ubuntu.com/25305169/↵
↵
Time complexity: O((n+q)*20*log(n))↵
</spoiler>↵
↵
###### 7. https://www.hackerearth.com/practice/basic-programming/input-output/basics-of-input-output/practice-problems/algorithm/play-with-numbers-2/↵
↵
<spoiler summary = "Hint">↵
PLAY WITH NUMBERS.↵
↵
Time Complexity:-O(max(N,Q))↵
↵
In this question you had to find out the expected value of value of the subarray from l to r.↵
↵
The expected value of the subarray is the mean of the subarray i.e. the sum of all the terms in the↵
subarray divide by the number of terms in the subarray. So to solve this we make an array A where ↵
A[i] stores the cumulative sum of all elements before index i+1. Then for every query given l and r ↵
the answer will be (A[r]-A[l-1])/(r-l+1). To ensure that we get the floor of the expected value we ↵
need to do integer divison.↵
↵
C++ Code — https://paste.ubuntu.com/25305261/↵
</spoiler>↵
↵
###### 8. https://www.hackerearth.com/problem/algorithm/alex-and-the-substring/, https://www.hackerearth.com/problem/algorithm/alex-and-the-substring-med/↵
↵
<spoiler summary = "hint">↵
Just make 26 maps for each character. make 2, such map arrays. one stores the frequency of sum that ends in current character and other for sums till previous index (sums means prefix sum); Then just iterate over the values then decrease in both array for current character and then add count of such numbers that end in same prefix sum (as then their difference will be zero)↵
###### http://paste.ubuntu.com/25305573989/↵
</spoiler>↵
↵
###### 9. https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/owl-fight/↵
↵
<spoiler summary="hint">↵
A direct implementation of dsu.↵
http://paste.ubuntu.com/25305377/↵
http://paste.ubuntu.com/25305621/↵
</spoiler>↵
↵
###### 10. https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/clock-1/↵
↵
<spoiler summary = "hint">↵
CLOCK↵
↵
Time Complexity:-O(R*R)↵
↵
In this question you had to find out number of integral points that lie between ↵
the minute hand and the hour hand (taking the clockwise angle from the minute to the hour hand) within the clock.↵
↵
For this we first needed to find out the angle of the minute and hour hand.↵
->minute hand angle:-m*6;↵
->hour hand angle:-h*30+m*(0.5);↵
After this for every integral point in the range (-R,-R) we need to check if it lies within the circle↵
and whether it lies between the minute and hour hand.↵
↵
C++ Code — https://paste.ubuntu.com/25305475/↵
</spoiler>↵
↵
↵
Competitive coding wing of GEEKHAVEN IIIT Allahabad is organising a contest on hackerearth on saturday 12th august. The contest is mainly centred for second year students, although I hope that everyone will be able to enjoy the problem set. The contest is prepared by the members of the wing. <br> <br>↵
↵
It has Balanced problemset with some interesting problems to simulate the grey cells and great to start the weekend.↵
<br><br>↵
↵
<strong>The link of the contest is — https://www.hackerearth.com/challenge/college/codemania-20/ </strong><br><br>↵
↵
The contest duration is 24 HRS. <br><br>↵
↵
I hope for an huge participation. :) <br><br>↵
↵
<strong> UPD: (EDITORIAL) </strong> <br><br>↵
↵
###### 1. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/cross-the-stairs/↵
↵
<spoiler summary="hint">↵
You can simply brute force for the solution. one by call friend for each level and then compute the answer for that call. Out of all possible solution select the maximum one. <br>↵
###### http://paste.ubuntu.com/25305339/ <br>↵
###### http://paste.ubuntu.com/25305411/↵
</spoiler>↵
↵
###### 2. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/honey-bees/↵
↵
<spoiler summary = "hint">↵
the problem was simple brute force. There were two cases to handle, when the second index is odd, and when second is even for both type of queries. Just make a big enough picture, and it will help you in understanding the solution. <br>↵
###### http://paste.ubuntu.com/25305429/↵
</spoiler>↵
↵
###### 3. https://www.hackerearth.com/problem/algorithm/modern-game/↵
↵
<spoiler summary = "hint">↵
You will have to convert the required ans into binary format. Then do dynamic programming over all bit positions. for every position you can either put one, or zero. This is true for all three numbers. At every point check whether putting these bits will give you a one. This information can be used to set a valid flag. In the end if flag is set and there is no carry for summation of the three numbers, then we have our solution. <br>↵
###### http://paste.ubuntu.com/25305466/↵
</spoiler>↵
↵
###### 4. https://www.hackerearth.com/problem/algorithm/an-excursion-in-mathematics/↵
↵
<spoiler summary = "hint">↵
You can use the constraints to solve this problem. Let us loop over the value of z for example. Then we have 3 equations in two variables. This makes the equation simple to solve. Then solve the equations to find the roots.↵
They are — x = sqrt(a — sqrt(2 b — a^2))/sqrt(2), y = sqrt(sqrt(2 b — a^2) + a)/sqrt(2) <br>↵
###### http://paste.ubuntu.com/25305520/ ↵
</spoiler>↵
↵
###### 5. https://www.hackerearth.com/problem/algorithm/coin-toss/↵
↵
<spoiler summary = "hint">↵
Note that the ways of tossing and of H and T have a bijection with each other.↵
↵
Let X(n),Y(n),Z(n) represent the allowable sequences ending with 2,1 and 0 consecutive tails respectively.↵
↵
We have:↵
↵
X(n)=Y(n-1)...(i)↵
Y(n)=Z(n-1)...(ii)↵
The above two results can be shown by considering that we can append a tails to the end of the n-1 length chain to create an n length chain with one more consecutive tail at the end.↵
↵
Now let F(n) denote the total number of acceptable sequences.↵
↵
Now, we have:↵
↵
Z(n)=F(n-1)...(iii)↵
(By appending an heads to the end of any acceptable sequence and removing heads from end of any (acceptable) sequence ending with tails ... bijection can be proved)↵
↵
Also (obviously):↵
↵
F(n)=X(n)+Y(n)+Z(n)↵
↵
Thus, we can show:↵
↵
F(n)=F(n-1)+F(n-2)+F(n-3) ...by (i), (ii), (iii)↵
↵
We can easily compute this in log(n) complexity using Matrix Exponentiation.↵
↵
solution link : https://paste.ubuntu.com/25305080/↵
↵
Time complexity : O(T*log(n))↵
↵
java solution : http://paste.ubuntu.com/25305535/↵
</spoiler>↵
↵
###### 6. https://www.hackerearth.com/problem/algorithm/ben-and-the-omnitrix/↵
↵
<spoiler summary = "hint">↵
prerequisite : Lowest Common ancestor , DFS↵
↵
For each 1 ≤ i ≤ n and 0 ≤ j ≤ log(n), store the minimum 20 values in the path from U(vertex) i to its 2^j-th parent in an array.↵
Now everything is needed is: how to merge the array of two paths? ↵
You can keep the these 20 values in the array in increasing order and for merging, use standard merge function which will work in . And then delete the extra values (more than 20).↵
Do the same for a query (just like the preprocess part) and you will get the list. ↵
↵
solution link : http://paste.ubuntu.com/25305169/↵
↵
Time complexity: O((n+q)*20*log(n))↵
</spoiler>↵
↵
###### 7. https://www.hackerearth.com/practice/basic-programming/input-output/basics-of-input-output/practice-problems/algorithm/play-with-numbers-2/↵
↵
<spoiler summary = "Hint">↵
PLAY WITH NUMBERS.↵
↵
Time Complexity:-O(max(N,Q))↵
↵
In this question you had to find out the expected value of value of the subarray from l to r.↵
↵
The expected value of the subarray is the mean of the subarray i.e. the sum of all the terms in the↵
subarray divide by the number of terms in the subarray. So to solve this we make an array A where ↵
A[i] stores the cumulative sum of all elements before index i+1. Then for every query given l and r ↵
the answer will be (A[r]-A[l-1])/(r-l+1). To ensure that we get the floor of the expected value we ↵
need to do integer divison.↵
↵
C++ Code — https://paste.ubuntu.com/25305261/↵
</spoiler>↵
↵
###### 8. https://www.hackerearth.com/problem/algorithm/alex-and-the-substring/, https://www.hackerearth.com/problem/algorithm/alex-and-the-substring-med/↵
↵
<spoiler summary = "hint">↵
Just make 26 maps for each character. make 2, such map arrays. one stores the frequency of sum that ends in current character and other for sums till previous index (sums means prefix sum); Then just iterate over the values then decrease in both array for current character and then add count of such numbers that end in same prefix sum (as then their difference will be zero)↵
###### http://paste.ubuntu.com/25305
</spoiler>↵
↵
###### 9. https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/owl-fight/↵
↵
<spoiler summary="hint">↵
A direct implementation of dsu.↵
http://paste.ubuntu.com/25305377/↵
http://paste.ubuntu.com/25305621/↵
</spoiler>↵
↵
###### 10. https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/clock-1/↵
↵
<spoiler summary = "hint">↵
CLOCK↵
↵
Time Complexity:-O(R*R)↵
↵
In this question you had to find out number of integral points that lie between ↵
the minute hand and the hour hand (taking the clockwise angle from the minute to the hour hand) within the clock.↵
↵
For this we first needed to find out the angle of the minute and hour hand.↵
->minute hand angle:-m*6;↵
->hour hand angle:-h*30+m*(0.5);↵
After this for every integral point in the range (-R,-R) we need to check if it lies within the circle↵
and whether it lies between the minute and hour hand.↵
↵
C++ Code — https://paste.ubuntu.com/25305475/↵
</spoiler>↵
↵
