Regionals 2000 :: Europe - Central (UVALive 2158 + HDU 1124 + POJ 1401 + ZOJ 2022 + SPOJ FCTRL)

Problem: Factorial
Tutorial: Trailing Zeros of a Factorial
You are given an integer N, you have to print how many Trailing Zeros N Factorial has.

lets be familiar with the term Factorial. Factorial of a number N is the product of all positive integer less than or equal to N.
Example: 5! = 5*4*3*2*1= 120

Trailing Zeros of a number is the total Zeros the number ends with.
Example: Trailing Zero of 120 is 1,
            Trailing Zero of 153 is 0,
            Trailing Zero of 50300 is 2.

A number will have a trailing zero if the number has 10 as a factor. that means the number should have 2 and 5 as a factor. if we have a pair of 2 & 5, then we can say that it has a trailing zero. so, trailing zero of a number is the minimum of factors of 2 & 5.
wait..
almost all even number has a multiple number of factor 2.
Example: 6! = 6*5*4*3*2*1. has 2 as factors in 2, 4, 6. but there is only one factor of 5 in number 5.
In the factorial of any number, the number of 2′s as factors will always exceed the number of 5′s as factors. that means, there is enough 2's to be paired with 5's.

now, the problem became easier, the total number of 5's as a factor in an integer is the number of trailing zero of that integer. we just need to count the number of 5's as factor of an integer.

if a number is multiple of 5, then it should have at least one 5's as a factor.
if a number is multiple of 25 (5*5), then it should have at least two 5's as a factor.
if a number is multiple of 125 (5*5*5), then it should have at least three 5's as a factor.
and so on...
lets be clear with an example:
the factorial of number 132 has 132/5^1=26 numbers multiple of 5.
132! has 132/5^2=5 (25, 50, 75, 100, 125) numbers multiple of 5^2
132! has 132/5^3=1 (125) numbers multiple of 5^3.
so factorial of 132 has a total 26+5+1=32 factor of 5's.

we are done, number of Trailing Zeros of 132! is 32.
a little simplification for code to avoid pow function is:
Trailing Zero of 132! = 132/5 + (132/5)/5 + ((132/5)/5)/5 = 26 + 5 +1.

Code

Regionals 2006 :: Africa/Middle East - Arab and North Africa. Being Smarty! (UVALive 3755)

Problem: Being Smarty!
You are given two integer (R and N) and two string in a single line. you have to separate the integers and strings.  a string made of upper- or lower-case letters, digits, and/or spaces. A string may be surrounded by double quotes,  If a property contains spaces, the surrounding double quotes are mandatory. first N row contains 1st string, 2nd N rows contains 2nd string, 3rd N rows contains 1st row and so on.
You have to print string of Rth row. if there is any upper case character in that string, print that character in lower case.

Category: Adhoc, IO handling.

Idea: first take the integers, then remove extra spaces, if 1st character of the 1st string is ", then insert the remaining string until another " found to 1st string. do the same for 2nd string. if there is no ", task is easier for you.
you can determine which string you have to print by the following condition.

((r-1)/n)%2, if 0, 1st string, otherwise 2nd stirng

code:

Regionals 2012 :: Asia - Dhaka. Wedding of Sultan (UVA 12582 + UVALive 6201)

Problem: Wedding of Sultan
You are given a path for an connected undirected graph with no cycle. The path is written by a man in the way: if he enter or leave the node he will write it down. When he comes to a node he looks for another connected to it which he has not traversed yet. If he finds such node, he follows that one. Otherwise, he go back. You have to find degree of each node.

Category: basic data structure [stack]

Idea: use stack to push the nodes in path one by one. if two consecutive node are equal, that means, this is the end of that node. now increase the degree of that node by one, and also increase its parent degree by one.
You are done.

Code

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. }