HackerRank October Challenge 2013 Editorial [Period] ________________By: Nafis Sadique

Problem: Period
The problem asks to find out n such that for given a, b, m
( (a + b√5)^n ) % m = 1
If no n is found then you have to output -1.

Observation:
Now lets find out the first k for which
((a + b√5)^k) % m = p, p is an integer.
Then   ((a + b√5)^tk) % m = q, q is an integer.

We also can figure out that k < m & t < m. So we can traverse for the value of k. Then We can traverse again for the value of t such that q = 1. After that we have to print tk.

Code:

1. cin >> T;
2. while(T--){
3. cin >> a >> b >> m;
4. c = 1, d = 0;
5. int period = 0;
6. REP(i, m + 10){
7. x = (a * c + 5ll * b * d) % m;
8. y = (a * d + b * c) % m;
9. c = x; d = y;
10. if(d == 0){
11. period = i + 1;
12. break;
13. }
14. }
15. LL tmp = c, fin = 0;
16. e = 1;
17. REP(i, m + 10){
18. e *= tmp;
19. e %= m;
20. if(e == 1){
21. fin = (i + 1) * period;
22. break;
23. }
24. }
25. if(fin == 0)cout << -1 << endl;
26. else cout << fin << endl;
27. }

HackerRank October Challenge 2013 Editorial [Angry Children 2]

Problem: Angry Children 2
You have to pick K elements from N elements, so that

is minimized.

Idea: Take all possible K elements and calculate result with the given equation. print the minimum one among them. (TLE!!)

Optimization 1:  You don't need to take all possible K elements, look, your task is to minimize the result, so take consecutive K elements. that means you have to sort the array first. [if u have no idea about sliding window, read the previous post here.
now you have selected all possible valid K elements in O(N)

Optimization 2:  let, K=4 and  the array after sorting is:-

[x0, x1, x2, x3, x4, x5, x6]

so, first segment is:-

 [x0, x1, x2, x3],  here, st=0, ed=3.

you can calculate result for this segment according to the given equation is:-

for(int i=st; i<ed; i++)

 for(int j=i+1; j<=ed; j++)

   res+=arr[j] - arr[i];

 your can see, you should get TLE with such wired code even for small input.
lets see that above code actually does.

( x1 - x0 ) + ( x2 - x0 ) + ( x3 - x0 ) +

( x2 - x1 ) + ( x3 - x1 ) +

( x3 - x2 )

 after simplify, we can get this

- 3*x0 - x1 + x2 + 3*x3

 i think you already notice. if not, 1st coefficient is k*(-1)+1, then coefficient increase with +2 each time.
the simplified code will look like this:-

ml = k * (-1) + 1;

for( int i=st; i<=ed; i++, ml+=2) 

  res+=  (arr[i] * ml);

Optimization 3:  u thought u finished? nope... N<=10^5. you will still get TLE for larger input.
lets see what happens for 2nd segment.

- 3*x1 - x2 + x3 + 3*x4

now look at the difference with the formula of 1st segment and 2nd segment.
by subtracting formula of 1nd segment from 2st segment we get.

                        - 3*x1 - x2 + x3 + 3*x4

  (-)  - 3*x0 - x1 + x2 + 3*x3

-------------------------------------------------------

               3*x0 - 2*x1 - 2*x2 - 2*x3 + 3*x4 

    ==>> 3*x0 + 3*x4 - 2 * (x1 + x2 + x3)

 we can pre-calculate the cumulative to have summation of (X­_I + X_i+1 ….. + X_k-1) in O(1).
use this optimization for 2nd to last segment.

Note: answer can be a very large (long long) value.

Code: 

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. int main()
5. {
6. int arr[100001], cs[100001], k, n;
7. long long res=0, mn, ml;
8. {
9. cin>>n>>k;
10. for(int i=0;i<n;i++)
11. cin>>arr[i];
12. sort(arr, arr+n);
13.  
14. cs[0]=arr[0];
15. for(int i=1;i<n;i++) cs[i]=cs[i-1]+arr[i];
16.  
17. for(int i=0, t=i+k-1; t<n;i++, t++)
18. {
19. if(i)
20. {
21. res+=(arr[i-1]*(k-1)+arr[t]*(k-1));
22. res-=((cs[t-1]-cs[i-1])*2);
23. mn=min(mn, res);
24. }
25. else
26. {
27. ml=k*(-1)+1;
28. for(int j=i;j<=t;j++, ml+=2)
29. res+=((long long)arr[j] * ml);
30. mn=res;
31. }
32. }
33. cout<<mn<<endl;
34. }
35. return 0;
36. }

HackerRank October Challenge 2013 Editorial [Chocolate Feast]

Problem: Chocolate Feast
You have $N, price of each chocolate is $C, and you can get one free chocolate for each M wrapper. print maximum chocolate you can eat.

Solution Idea: first count how many chocolates you can buy with $N. it simply N/C.
eat all chocolates, now you have the wrappers. if you have more than M wrappers, return multiple of M wrappers, let, M*X wrappers where X>0 to get X more free chocolates. eat them, now count how many wrapper you have, continue the procedure until you don't have enough wrapper to have a free chocolate.

Example:  for N=10, C=2, M=3.
you can buy 5 chocolate with $10, now you have 5 wrapper. return 3 wrapper to get a free chocolate, now you have 2 wrapper and 1 wrapper after eating the free chocolate. so total wrapper=3, return 3 wrapper to get another free chocolate.
so, total chocolate= 5 (buy) + 2 (free) = 7.

Code: 

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. #define SET(a) memset(a,-1,sizeof(a))
5. #define CLR(a) memset(a,0,sizeof(a))
6. #define PI acos(-1.0)
7.  
8. int main()
9. {
10. int tc, n, c, m, tch, wr, tmp;
11. cin>>tc;
12. while(tc--)
13. {
14. cin>>n>>c>>m;
15. tch=wr=n/c;
16. while(wr>=m)
17. {
18. tmp=wr/m;
19. wr=wr%m;
20. wr+=tmp;
21. tch+=tmp;
22. }
23. cout<<tch<<endl;
24. }
25. return 0;
26. }

Similar Problems:
The Coco-Cola Store
Cola
Soda Surpler

HackerRank October Challenge 2013 Editorial [Angry Children]

Tutorial: Sliding Window / Line Sweeping.
Problem: Angry Children
You have an array of N numbers, You have to pick K numbers where the difference of Maximum element and minimum element are minimized.

Idea: Sliding Window / Line Sweeping.
Straightforward Problem. if you are not familiar with sliding window, you can continue reading.
1st thing comes to your mind is, you should try to take elements with minimum difference to your current element. so, sort the array.
as you already sorted the array, not you can find minimum or maximum element of a segment in O(1), first element of the segment is minimum and last element of the value is maximum. thus difference of the segment can be calculate in O(1).
do a linear scan and minimize the answer. see picture below to be clear how sliding window work.
for N=8, K=3.
and the array after sorting is [1,   2,   7,   7,   17,   18,   20,   22]

here we see, in the 5th iteration we get the minimum value. (taking elements 17, 18  & 20).
so the answer is 3.

Note: this is actually a modification / simplification of original sliding window approach, in this problem you are allowed to sort the array first.

Code: 

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. int main()
5. {
6. int arr[100001], k, n;
7. cin>>n>>k;
8. for(int i=0; i<n; i++)
9. cin>>arr[i];
10. sort(arr, arr+n);
11. int mn=1e9;
12. for(int i=0, t=i+k-1; t<n; i++, t++)
13. mn=min(mn, arr[t]-arr[i]);
14. cout<<mn<<endl;
15. return 0;
16. }

Similar Problems:
 Christmas Play
 SRM 601, div-2, 250

Steps to get Commonwealth Scholarships for Bangladeshi Students and Teachers

Click Here

CodeChef October Challenge 2013 Editorial [CAO Stage-3] ____________By: Nafis Sadique

Problem: CAO Stage-3

The problem has 2 sub-problems. The first problem is to finding the position of the monsters.
The second was to find out the winner of the game. Let's solve this problem step by step.

First problem - where are the monsters?

The problem says that we have to find the total number of consecutive free cells in all 4 direction from a cell. Then if the minimum of them has at least a prime less than or equal to it then we can call that this cell has a monster.

We know that the smallest prime is 2. So if any cell has at least 2 consecutive cells containing '^' in all 4 direction then we can say that this cell contains a monster. easy job!!!

Hard problem - who the hell is the winner?

Now we know the position of the monster. But what about the game we are supposed to play?
This game has 2 players. In one move a player can select any monster that is alive and kill all the monsters in the same row and column. The first person who can't give any move loses.
Sounds a lot like grundy game. But how to calculate the outcome?????????????

Well after being stuck for 1 day i finally observed this line in the statement 

"Lava stops flowing past the cells which already have lava in them."

That gave me a hint that we can convert the game to dp state and calculate the outcome.
The hint would be - whenever i select a monster i divide the grid into 4 disjoint grid.

Thus we can get a dp state and then use sprague-grundy theorem to calculate mex etc. etc.

See the code for details and if grundy is unclear then wikipedia would be a good reference.
Also you have to know dp.

Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. int dp[21][21][21][21], grid[21][21];
5.  
6. int go(int x1, int x2, int y1, int y2){
7. if(x1 > x2 || y1 > y2)return 0;
8. int &ret = dp[x1][y1][x2][y2];
9. if(ret != -1)return ret;
10. ret = 0;
11. set < int > ss;
12. for(int i = x1; i <= x2; i++){
13. for(int j = y1; j <= y2; j++){
14. if(grid[i][j] != 1)continue;
15. int a = go(x1, i - 1, y1, j -1);
16. a ^= go(x1, i - 1, j + 1, y2);
17. a ^= go(i + 1, x2, y1, j - 1);
18. a ^= go(i + 1, x2, j + 1, y2);
19. ss.insert(a);
20. }
21. }
22. for(set < int > :: iterator it = ss.begin(); it != ss.end(); it++){
23. if(ret != *it)break;
24. ret++;
25. }
26. return ret;
27. }
28. char pp[21][21];
29. main(){
30. ios_base::sync_with_stdio(0); cin.tie(0);
31. long long a,b,c,d,e,f,g,h = 0,x,y,z;
32. cin >> a;
33. while(a--){
34. cin >> b >> c;
35. for(int i=0;i<b;i++) cin >> pp[i];
36. memset(grid,0,sizeof grid);
37. memset(dp, -1, sizeof dp);
38. for(int i=0;i<b;i++){
39. for(int j=0;j<c;j++){
40. d = 0;
41. if(pp[i][j] == '#')d = 1;
42. if(i < 2 || pp[i - 1][j] == '#' || pp[i - 2][j] == '#')d = 1;
43. if(j < 2 || pp[i][j - 1] == '#' || pp[i][j - 2] == '#')d = 1;
44. if(i > b - 3 || pp[i + 1][j] == '#' || pp[i + 2][j] == '#')d = 1;
45. if(j > c - 3 || pp[i][j + 1] == '#' || pp[i][j + 2] == '#')d = 1;
46. if(d == 0)grid[i][j] = 1;
47. }
48. }
49. d = go(0, b - 1, 0, c - 1);
50. if(d == 0)cout << "Kirito" << endl;
51. else cout << "Asuna" << endl;
52. }
53. }