DPS Dwarka INOI practice

Almost after breaking my resolution of frequent blogging, here I present to you a post about the last Codechef Contest I did the DPS Dwarka INOI practice.
The contest was fairly easy, I don't think it kind of lived up to the name of the INOI practice. But I think it was a nice contest, and somehow I ended up solving all the 6 problems.
So here's something straight from the horse's mouth (wait did I just called myself a horse ? ummm...)

Problem 1 :- Chef and Powers of 2

So here we have another codegolf problem and almost immediately the word that pops into my head is "Python"(that mystical language used by the ancients to treat all maladies) that can be used to express my ideas in the most consize manner as possible.

The problem basically states to decompose an even number as a sum of distinct powers of 2 in increasing order.

My first approch :-

1. n=int(input())  
2. s="{0:b}".format(n)  
3. s=s[::-1] #reverses the string magically :P  
4. for i in xrange(len(s)):  
5.     if s[i]=='1':  
6.         print 2**(i),   

Take the number convert it to its binary equivalent string and if the character at i'th postion is '1' print 2^i but you know what ? It was TOO LONG 100 characters OMG unsuitable for codegolf and it fetched me just 0.34 points. So back to the drawing board.

Realized that why do I have to convert the number to a binary string when it's stored as a binary number in memory.
So cutting down some unnecessary code gives.

1. n=int(input());i=1  
2. while (1<<i)<=n:  
3.     if ((1<<i)&n):  
4.         print 1<<i,  
5.     i+=1   

So something better but wait a minute bitshifting ??? it's unecessary it costs me 2 characters while mutiplication will make it just 1.

1. n,k=input(),2  
2. while k<=n:  
3.     if k&n:print k,  
4.     k*=2   

Cute isn't it ? Wait I can do better. the last step was to remove indents and that made me learn the inline if statement of python
The final version

1. n,k=input(),2  
2. while k<=n:print k if k&n else '',;k*=2   

now removing the indents makes it kind of ugly from python's point but for codegolf its just fine so here I was with 0.708 points on the board. cool now moving onto the next problem

Problem 2:- Chef and Fibonacci

So the problem states that :-
given two numbers A,B find the C'th fibonacci number where C=gcd(A,B) and since the number can be pretty large print it modulo 10^9+7 (pretty standard one).

Since the constraints are fairly large so here's the place to put your matrix exponentiation skills to action.
So as learnt from e-maxx the following equations are great to observe the behaviour of Fibonacci series
                                    
                                                  So if   
                                  Then

Now time for some code. It's nice to observe that matrix exponentiation is just the same as binary exponentiation establising the the essence of symmetry between the mathematical entities.

1. from fractions import gcd  
2.   
3. basis=[[0,1],[1,1]]  
4.   
5. def multiply(m1,m2):  
6.     one=(m1[0][0]*m2[0][0]+m1[0][1]*m2[1][0])%(10**9+7)  
7.     two=(m1[0][0]*m2[0][1]+m1[0][1]*m2[1][1])%(10**9+7)  
8.     three=(m1[1][0]*m2[0][0]+m1[1][1]*m2[1][0])%(10**9+7)  
9.     four=(m1[1][0]*m2[0][1]+m1[1][1]*m2[1][1])%(10**9+7)  
10.     return [[one,two],[three,four]]  
11.   
12. def modular(base,exponent):  
13.     res=[[1,0],[0,1]]  
14.     while exponent:  
15.         if exponent%2==1:  
16.             res=multiply(res,base)  
17.             exponent-=1  
18.         else:  
19.             base=multiply(base,base)  
20.             exponent>>=1  
21.     return res  
22.   
23. t=int(input())  
24. while t>0:  
25.     t-=1  
26.     a,b=map(int,raw_input().split())  
27.     c=gcd(a,b)  
28.     l=basis  
29.     ans=modular(l,c-1)  
30.     print (ans[0][0]+ans[1][0])%(10**9+7)   

Just to clarify the basis here is our matrix P and multiply fuction multiplies two matrices of 2x2 order
modular raises them to power and rest is nothing but python's awesomeness.
So here was another problem in the bag.

Problem 3:- Chef and mountains

Problem statement:- Given an array and  n queries of two numbers A and B check that the max value in range [A,B] is greater than value at index A or not. Another standard problem , R.M.Q.
nothing  special about the implementation either.
Nothing special, just initialize the Segment tree and start making queries.
Not to mention that got 6 WA's due to an undetected bug.

1. #include <cstring>  
2. #include <vector>  
3. #include <list>  
4. #include <map>  
5. #include <set>  
6. #include <deque>  
7. #include <stack>  
8. #include <bitset>  
9. #include <algorithm>  
10. #include <functional>  
11. #include <numeric>  
12. #include <utility>  
13. #include <sstream>  
14. #include <iostream>  
15. #include <iomanip>  
16. #include <cstdio>  
17. #include <cmath>  
18. #include <cstdlib>  
19. #include <ctime>  
20. #include <memory.h>  
21.    
22. using namespace std;  
23. #define FOR(i,a)    for(int i = 0;i < a;i++)  
24. #define REP(i,a,b)  for(int i = a;i < b;i++)  
25. #define vi vector<int>  
26. #define MAXN 5000010  
27.    
28. int ar[MAXN],M[MAXN];  
29.    
30. void init(int ar[MAXN],int M[MAXN],int node,int b,int e)  
31. {  
32.     if(b==e)  
33.     {  
34.         M[node]=ar[e];  
35.         return ;  
36.     }  
37.     init(ar,M,2*node+1,b,(b+e)/2);  
38.     init(ar,M,2*node+2,(b+e)/2+1,e);  
39.     M[node] = max(M[2*node+1] , M[2*node+2]);  
40. }  
41.    
42. int query(int ar[MAXN],int M[MAXN],int node,int b,int e,int i,int j)  
43. {  
44.     if(i>e||j<b)//out of bounds  
45.     {  
46.         return -1;  
47.     }  
48.     if(b>=i&&e<=j)  
49.     {  
50.         return M[node];  
51.     }  
52.     int p1,p2;  
53.     p1=query(ar,M,2*node+1,b,(b+e)/2,i,j);  
54.     p2=query(ar,M,2*node+2,(b+e)/2+1,e,i,j);  
55.     return max(p1,p2);  
56. }  
57.    
58. int main()  
59. {  
60.     int n,q,a,b,c;  
61.     scanf("%d",&n);  
62.     FOR(i,n)  
63.     {  
64.         scanf("%d",&ar[i]);  
65.     }  
66.     init(ar,M,0,0,n-1);  
67.     scanf("%d",&q);  
68.     while(q--)  
69.     {  
70.         scanf("%d %d",&a,&b);  
71.         if(b-a>=2)  
72.         {  
73.             c=query(ar,M,0 ,0,n-1,a,b-2);  
74.         }  
75.         else  
76.         {  
77.             printf("YES\n");  
78.             continue;  
79.         }  
80.         if(c>ar[a-1])  
81.         {  
82.             printf("NO\n");  
83.         }  
84.         else  
85.         {  
86.             printf("YES\n");  
87.         }  
88.     }  
89.     return 0;  
90. }   

Problem 4:- Chef and moon

The Problem asks to find all pairs of shortest paths from any source to destination and print "YES" if it's less than or equal to a given number k otherwize print "NO"
Take a look at the question and it just screams of Floyd-Warshall. So nothing special about it at all either, I was surprised at the fact that only 370 people solved it.

1. #include <cstring>  
2. #include <vector>  
3. #include <list>  
4. #include <map>  
5. #include <set>  
6. #include <deque>  
7. #include <stack>  
8. #include <bitset>  
9. #include <algorithm>  
10. #include <functional>  
11. #include <numeric>  
12. #include <utility>  
13. #include <sstream>  
14. #include <iostream>  
15. #include <iomanip>  
16. #include <cstdio>  
17. #include <cmath>  
18. #include <cstdlib>  
19. #include <ctime>  
20. #include <memory.h>  
21.    
22. using namespace std;  
23. #define FOR(i,a)    for(int i = 0;i < a;i++)  
24. #define REP(i,a,b)  for(int i = a;i < b;i++)  
25. #define vi vector<int>  
26. #define MAXN 1000000000  
27.    
28. int city[110][110];  
29.    
30. int main()  
31. {  
32.     ios_base::sync_with_stdio(false);  
33.     FOR(i,100)  
34.     {  
35.         fill(city[i],city[i]+100,MAXN);  
36.     }  
37.     int n,m,K,a,b,c;  
38.     cin>>n>>m>>K;  
39.     FOR(i,m)  
40.     {  
41.         cin>>a>>b>>c;  
42.         city[a-1][b-1]=c;  
43.         city[b-1][a-1]=c;  
44.     }  
45.     FOR(i,n)  
46.     {  
47.         city[i][i]=0;  
48.     }  
49.     for(int k=0;k<n;k++)  
50.     {  
51.         for(int i=0;i<n;i++)  
52.         {  
53.             for(int j=0;j<n;j++)  
54.             {  
55.                 city[i][j]=min(city[i][j],city[i][k]+city[k][j]);  
56.             }  
57.         }  
58.     }  
59.     int q,u,v;  
60.     cin>>q;  
61.     while(q--)  
62.     {  
63.         cin>>u>>v;  
64.         if(city[u-1][v-1]<=K)  
65.         {  
66.             cout<<"YES\n";  
67.         }  
68.         else  
69.         {  
70.             cout<<"NO\n";  
71.         }  
72.     }  
73.     return 0;  
74. }  

Problem 5:- Chef and array

Number of ways of partitionong an array in to 3 contiguous parts such that each part gets same sum.
Straight forward memoization.
1) Convert the array to it's prefix sum.
2) If sum of all elements is not divisible by 3 print 0.
3) Memoize for each index i how many elements in the remaining indices greater than i have value    2*(sum[n]/3)
4) for each index i where sum[i] == (sum[n]/3) add the memoized value to a counter.

The code will explain better I guess.

1. #include <cstring>  
2. #include <vector>  
3. #include <list>  
4. #include <map>  
5. #include <set>  
6. #include <deque>  
7. #include <stack>  
8. #include <bitset>  
9. #include <algorithm>  
10. #include <functional>  
11. #include <numeric>  
12. #include <utility>  
13. #include <sstream>  
14. #include <iostream>  
15. #include <iomanip>  
16. #include <cstdio>  
17. #include <cmath>  
18. #include <cstdlib>  
19. #include <ctime>  
20. #include <memory.h>  
21. using namespace std;  
22. #define FOR(i,a)    for(int i = 0;i < a;i++)  
23. #define REP(i,a,b)  for(int i = a;i < b;i++)  
24. #define vi vector<int>  
25. #define MAXN 1000000  
26. #define LL long long  
27. LL ar[MAXN];  
28. int tr[MAXN];  
29. int main()  
30. {  
31.     int n;  
32.     fill(tr,tr+MAXN,0);  
33.     scanf("%d",&n);  
34.     FOR(i,n)  
35.     {  
36.         scanf("%lld",&ar[i]);  
37.         if(i!=0)  
38.         {  
39.             ar[i]+=ar[i-1];  
40.         }  
41.     }  
42.     if(ar[n-1]%3!=0)  
43.     {  
44.         printf("0\n");  
45.         return 0;  
46.     }  
47.     LL tw=2*(ar[n-1]/3);  
48.     LL on=(ar[n-1]/3);  
49.     for(int i=n-3;i>=0;i--)  
50.     {  
51.         if(ar[i+1]==tw)  
52.         {  
53.             tr[i]=tr[i+1]+1;  
54.         }  
55.         else  
56.         {  
57.             tr[i]=tr[i+1];  
58.         }  
59.     }  
60.     LL ans=0;  
61.     FOR(i,n)  
62.     {  
63.         //cout<<ar[i]<<tr[i]<<endl;  
64.         if(ar[i]==on)  
65.         {  
66.              ans+=tr[i];  
67.         }  
68.     }  
69.     printf("%lld\n",ans);  
70.     return 0;  
71. }  

Problem 6:- Chef and confusing road

Tell you what Deja vu problem Unbearable Controversy of being. with relaxed constraints. My solution which got TLE on codeforces AC here on one go.

The procedure i followed was to take the any two nodes and  find next successive members of the graph and take the intersection of both and add it to the count.

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define FOR(i,a)    for(int i = 0;i < a;i++)  
6. #define REP(i,a,b)  for(int i = a;i < b;i++)  
7. #define vi vector<int>  
8.   
9. vector<set<int> >adjlist;  
10. set<int>intersect;  
11.   
12. int main()  
13. {  
14.     ios_base::sync_with_stdio(false);  
15.     int m,n,a,b,drc=0;  
16.     cin>>n>>m;  
17.     adjlist.resize(n);  
18.     FOR(i,m)  
19.     {  
20.         cin>>a>>b;  
21.         adjlist[a-1].insert(b-1);  
22.     }  
23.     FOR(i,n)  
24.     {  
25.         for(set<int>::iterator it=adjlist[i].begin();it!=adjlist[i].end();it++)  
26.         {  
27.             int p1=*it,p2;  
28.             set<int>::iterator it1=it;  
29.             it1++;  
30.             while(it1!=adjlist[i].end())  
31.             {  
32.                 p2=*it1;  
33.                 intersect.clear();  
34.   set_intersection(adjlist[p1].begin(),adjlist[p1].end(),adjlist[p2].begin(),adjlist[p2].end(),std::inserter(intersect,intersect.begin()));  
35.                 if(intersect.find(i)!=intersect.end())  
36.                 {  
37.                     drc+=(intersect.size()-1);  
38.                 }  
39.                 else  
40.                 {  
41.                     drc+=(intersect.size());     
42.                 }  
43.                 it1++;  
44.             }  
45.         }  
46.     }  
47.     cout<<drc<<endl;  
48.     return 0;  
49. }   

So here ends another contest and it's editorial I am kind of  trying keep my resolution of Blogging frequently.Now for some bragging, by the way I stood 22nd overall in this contest  :) this much of bragging is deserved after writing a post this long. Also I got a near perfect score in USACO Bronze division January Contest , Not perfect though but still fine, so up-next USACO Bronze January Contest. If I get upgraded to silver will be looking forward to it too :)

See you guys Later.
Adios.