Good Bye 2014

Well, seriously speaking one of my new year's resolutions will be to write and update my blog frequently. As far as the last post regarding heapsort is concerned well I have come a long way ahead of it and I guess, there won't be much need of doing it now because almost all procedures were written and I will wrap it up in a python code:-

1. def heapsort(A,n):  
2.     buildheap(A,n)  
3.     heapsize=n  
4.     i=n-1  
5.     while(i>0):  
6.         A[0],A[i]=A[i],A[0]  
7.         heapsize=heapsize-1  
8.         heapify(A,0,heapsize)  
9.         i=i-1 

That would be sufficient I think. As procedures heapify and buildheap were dealt before.
Now the thing for what I meant to write this post for.
                                           The GoodBye 2014 Contest on Codeforces
This contest was held on Dec 30th 2014 on Codeforces. It had 6k+ participants (a huge number literally)

The tasks were designed by tncks0121 and ainta. 

There were 7 problems with varying difficulty and 2:30 hrs time slot was provided to solve the problem set, also the contest was a division combined contest meaning Div 1 + Div 2 participants battling it out for supremacy (and we all know how that ends). The top 3 for the contest were tourist , Petr and rng_58 surprisingly they are also the top 3 contestants in terms of overall rating now. Petr went 3k+ after the contest making him the 3 person ever to achieve the feat of becoming a Codeforces target, after tourist and rng_58. Here is the link to standings.

Let's talk about the problems now.
First problem was
                                                  A. New Year Transportation 
A basic problem of the ad-hoc category but masked under an unusally long problem statement.
The idea was to navigte through the array starting from the index 0 and increasing the index i by value A[i] (i.e. the value at that index) and checking if you are able to reach the t'th element or not.
So a fairly straightforward approach gave an AC.
my code for The task (in python).

1. n,t=map(int,raw_input().split())  
2. ar=map(int,raw_input().split())  
3. curr=0  
4. while curr!=t-1:  
5.     curr=curr+ar[curr]  
6.     if curr>=n-1:  
7.         break  
8. if curr==t-1:  
9.     print "YES"  
10. else:  
11.     print "NO"  

The second problem was
                                                 B. New Year Permutation
I spent quite some time on this problem because it was not easy for me to grasp certain concepts which were necessary to solve this problem. So a sufficient amount of time was spent on pen and paper convincing myself that all connected components of the graph can be swapped to achieve the best ordering as possible. So I simplified the solution in terms of an algorithmic procedure that involved.
1) Traversing the graph's all components (connected or disconnected)
2) For all the connected components sort them in increasing order of vertices and their specific weights.
3) Print the array in that order.
My only problem now was to code the BFS from scratch because I don't have an all purpose template at hand and I am on a lookout for it.
My Code for the task (C++).

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define FOR(i,a)    for(int i = 0;i < a;i++)  
4. #define REP(i,a,b)  for(int i = a;i < b;i++)  
5. #define vi vector<int>  
6.   
7. vector<int>graph[400];  
8. int ar[400];  
9. int ans[400];  
10.   
11. int ok(bool vis[400],int n) //checks if all the nodes are visited or not 
12. {  
13.     FOR(i,n)  
14.     {  
15.         if(vis[i]==false)  
16.         {  
17.             return i;  
18.         }  
19.     }  
20.     return -1;  
21. }  
22.   
23. int main()  
24. {  
25.     ios_base::sync_with_stdio(false);  
26.     char st[400];  
27.     int n;  
28.     cin>>n;  
29.     FOR(i,n)  
30.     {  
31.         cin>>ar[i];  
32.     }  
33.     bool vis[400];  
34.     fill(vis,vis+n,false);  
35.     FOR(i,n)  
36.     {  
37.         cin>>st;  
38.         int flag=0;  
39.         FOR(j,n)  
40.         {  
41.             if(st[j]=='1')  
42.             {  
43.                 flag=1;  
44.                 graph[i].push_back(j);// construct the graph  
45.             }  
46.         }  
47.         if(flag==0)  
48.         {  
49.             vis[i]=true;  
50.         }  
51.     }  
52.     while(ok(vis,n)!=-1) //until all elements are visited 
53.     {  
54.         int pn=ok(vis,n);  
55.         queue<int>q;  
56.         vector<int>v1;  
57.         vector<int>v2;  
58.         q.push(pn);  
59.         v1.push_back(pn);  
60.         vis[pn]=true;  
61.         while(!q.empty())  //BFS
62.         {  
63.             int tp=q.front();  
64.             q.pop();  
65.  for(vector<int>::iterator it=graph[tp].begin();it!=graph[tp].end();it++)  
66.             {  
67.                 if(!vis[*it])  
68.                 {  
69.                     q.push(*it);  
70.                     vis[*it]=true;  
71.                     v1.push_back(*it);  
72.                 }  
73.             }  
74.         }  
75.         int sz=v1.size();  
76.         FOR(i,sz)  
77.         {  
78.             v2.push_back(ar[v1[i]]);  
79.         }  
80.         sort(v2.begin(),v2.end());  
81.         sort(v1.begin(),v1.end());  
82.         FOR(i,sz)  
83.         {  
84.             ar[v1[i]]=v2[i];  
85.         }  
86.     }  
87.     FOR(i,n)  
88.     {  
89.         cout<<ar[i]<<" ";  
90.     }  
91.     cout<<endl;  
92.     return 0;  
93. }  

One more additional point in this problem was that it was fairly easy to pass the pretests with greedy swaps. But that solution was sub-optimal and that's what made this the most hacked problem of the contest. During the contest I was also afraid of being hacked after seeing so many successful hacks although nothing happened.

The third problem was.
                                                 C. New Year Book Reading
This was the problem I was expecting to be pretty difficult but turned out fairly easy, a cetain manual inspection of the sample test cases revealed the underlying principle of the optimal ordering and the minimum weights to pick up.

 My strategy was
1) For each day , take the book the person read on the  day and label it as .
2) Check the previous days from  downto  and keep going till .
3) Construct a set of distinct books read during that interval apart from .
4) Add the weights of the books in your set to the final answer.

   Code C++

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

 
I have also learnt from discussions on Quora that we wouldn't need the set at all for this problem but I think this was the first approach that came to my mind and I coded it up, It might be a bit inefficient but still, it gives the correct answer and I'm happy about it.

I'm currently doing the 4th problem which I couldn't solve during the contest and would update the analysis later, my friend Sandeep told me that it's got something to do with the linearity of expectation and advised to read it from CLRS as nearly all expectation related questions have that element in it, so will do that in a while.

Also as the upcoming mission statement I would like to say that nearly all the upcoming posts would be about Programming Contests and the analysis of their problems. The contests might be the upcoming ones on TC/CF or old ones which I intend to do as virtuals, so stay tuned in for some more action.

and Finally (although I am a bit late) I would like to say, "Happy New Year" to everyone and wishing you success in all your upcoming endeavors.

Thanks for reading.