My MS internship 2 - The interview  

Posted by Unknown in

It was all like a joke or a dream but the company invited us for an interview. We got a mail on 1st April about it. what a day to be serious. But then w had had a talk earlier and then had an interview on 5th. It was a tough long day as the second time in two years i was out of station, the Sunday before my second mid sems in the month of April. Last time had been a successful IIT paper and this time it was an interview. I'll be really looking for something the next time around as well. Mayank and Abhishek had done some preparation and it was really up for the time to tell whether hat would fruit. We were there on time. The college had been helpful.

But it seemed that we were pulled as a part of the regular interviews. And indeed we were. Truly, now it was tough. There were seniors I don't care but they had prepared for it and were ta say formally dressed, prepared and all. And we were simple. The day had long waits as we were called. We were given two questions to do which I came here and came to know that were among the standard questions. I don't even remember as well what the questions were but we were to interact with the examiner to get in and that I should say was the main point. People from all the places were there, but indeed I felt that good. The question was basic and I gave two possible solutions to the examiner. Maybe that was watch they were judging, the number of parallel solutions that we could find out.

So in the end of it i qualified to the second round while both of them were out. They went leaving me alone. This was I think the real test- to pass out 6-8 hours a that silly place with nothing to do alone. People had friends to talk to and I was a junior to them. More so they were strange and too formal to talk to. Finally I got a chance to get the interview. This was the best part of the set. I had long one but indeed it was good, after a little struggle, I figured out almost everything. The questions for me were new but people say they were standard. One was to check out rows and column that had a zero in a binary matrix. One was a discussion of my previous problem (the written round). One was a logical one where the word phrasing was the key. There were numbered doors and serially they were toggled as the tables of one, two, three till hundred were read. Basically initially all were open. Then all multiples of 1 were toggled. Then 2 and so on. There were 100 doors and I had to figure out how many will be open. I figured that out and after that started to feel i was through this round. The answer was simple. for say 16, 8x2 and 2x8 so the toggling cancelled. But 4x4 it doesn't the perfect squares don't toggle twice to cancel.

I had a paper and so was allowed to after that and my third round was left for that time. I did not whether that was to take place. I went through the midsems, the news as started to spread. The third round then came. A sudden telephonic round.

It was a Saturday and luckily I was in my room, alone with no classes. i knew there was an interview to come but did not know when. But got that good enough. The people did consider the second year and asked me only data-structures and OS. A few logical questions and then a test whether I knew OOPs was enough and he hung up. Of the non bookish questions, one was to design an algo for the lift system, maybe because when i came here, I saw that this was the one they wanted to changed all the time.

All right this was in short how I was through. Details summary personally hi milegi, some day if I feel like to.

My MS internship - the background  

Posted by Unknown in

Okay so I am writing all the details in advance. I know I would be discussing a lot about the environment and culture once I return but I don't want my blog to miss it- so that I can redirect people when I am not willing to speak(Got it that's why I gave you the link - Also to popularize the blog) Any way here I start - I had been good at programming right from the start(even though I left computers for biology in class XI and XII). I had a safe lead in VIII & IX of over 10 marks when the subject was introduced. But I had a shock at the boards where I managed 88, while was expecting 98. I tried my best but my school was interested in only toppers - I was not. More so,you rarely get your marks corrected at ICSE, the teachers are careless at those issues. Many said it was not an error at my side but my programs had always been on the non-traditional side, those which are less understood by the people that are used to mugging up the book. All right time had passed and I had landed into Thapar.
I had computers in my first semester and I think it was there that I realized that what I considered as nothing actually was a lot and the basic programming that I used to love was indeed the problem of many. I then had to get my branch changed. I did not take that as seriously towards the going semester but took a week off before AIEEE( strange rule - you need a rank to get your branch changed and hat too better than the closing of the branch this year). I had missed CS by just one seat and this time this was not going to be repeated. Despite a marriage before that which I attended and partying it all over the week, I managed to gt my formulae revised and everyone knows that they ask nothing else at AIEEE. I got my branch changed to computers. i had meanwhile in my first year won quite a few contests and was starting to feel the contest level of the college too low. Sourabh, with an intention to do robotics invited me to join his team for IITKGP fest Kshitij. You know how I am. I don't deny till of course I know I won't do it in all cases.
We somehow go a working model made and decided to go to KGP. But I had always taken overnight there seriously and he had also seen that. Meanwhile I had a serious fever before the fest and couldn't come up in the train. But maybe luck wanted me to go and I was thee the next day, morning flight.
Robotics came out too tough. But then that opened gates for programming. I had a good four hour sleep before the contest and started there afresh. I will talk in details about the IITKGP overnight some other day. Right now what I can say is that, out of sheer luck and co-incidence we ended up sixth and in the consolation list. I had no experience to professional contest programming. Neither were we a match to the fourth year guys. And we had managed only one correct question in seven hours of the eight in the contest. but the last hour had been fruitful as i had found bugs in one of my code - a missing test case and also sourabh had come up with brute force ideas that were looking cheap but came up good.
That was my introduction to contest programming. We finalized IIT Roorkee fest for another try at robotics and more importantly one more standard contest. I meanwhile learned about the ICPC and what it takes to program there. I started a few basic learning - plan do some intermediate to advance now.
We reached IITR and as usual our robot crashed in the trial run to a state that we could not even plan to give it a proper demo on the actual course. Meanwhile IDC was one of the associate sponsors and over half the CS contests were being organized by it. We were spending time there. Mayank and all had also come for gaming and more so time pass. I had been to one more final before this where I had crashed out. But indeed all seemed preparation for this. I was sitting with Mayank and Abhishek here anybody. But this time the brain was working. We were fast and good. In the lead right from the start. Happens someday when everthing falls to place. I was guessing the algos and solving them. Mayank was coming out with strange un-makable algos while sourabh - his team did not have a single person worth while to code. In the end we finished second, after somewhat struggles as the teams suddenly came out with submissions. We were first 10 minutes before the closure. Ok this much short intro must be enough. Lets go to the interview and the trip.... Next posts plz....

Animator vs Animation  

Posted by Unknown






Any idea how you can get this made???

Wikipaedia - What's that maintains it?  

Posted by Unknown in

I am not really a critic, but then if I criticized the world's biggest encyclopaedia for its shortcommings, I should also mention some of its features that has made it to stand the test of time and opposition from teachers who considered this unauthentic.
By the way wiki is still not considered an authentic source to quote out and due its nature it'll never be but then still it provies you accurate and precise information most of the time and that I should say is its success. it has been able to successfully manage the inflowing content marking out that which is old and that which may not be accurate. At so many places you would have seen tags like citation needed, old, needs updation, etc. There is a proper team of people who at their free times go to wikipaedia to read and edit and help maintain this enormous project. And the greatest part is that its successful.
Reasons for the maintainance of wiki or some tricks that worked have been discussed a lot but I write out the tricks that made it pass the test of time.
Internationalization: An article written by say in India is viewed and analysed by a person far off say somewhere in Africa. So he is neither familiar of the concept and in many cases might not have even heard of it. With such kind of people viewing who have no sort of attachment with the subject whatsoever, no connection most probably, you can expect proper judgement.Atleast the grammar, the feel of the issue and the emotions of the author can easily be understood by the third person who can then make sure it is successful.
No Registration: Registration is not compulsory for little editting. What that makes sure is that it hardly takes time for the people to modify it. Of course, the modification is monitored.
User Page: Never thought of it when i did not have an account, but I see it now, user page is an aspect of wikipaedia that has affected it the most. Everyone want's to tell the world what he has done. So if you have a user page as a wiki user, you will atleast know that your contributions are counted and there is a place where people can come to you. Its better than sending emails and keeping problems private. There is supposed to be all open matter on wiki and so is the user page.
Openness of templates: The templates of wiki are all open and the source code free enough to be modified. So the users can come up with new ideas to decorate it.
Support for Review: The most important aspect of maintainace is to check whether false facts do not come up. And that has been maintained by the neormous support for the reviewers or those people who take responsibility to help and maintain. They will normally ahve the WIkiEd installed so no issue of editor for them. Then the task is made simple - every fact requires a direct citation, not present mark it. Marking is just two letters or three letters of typing, not at all time confusing. the links are understandable and so you don't have to explain in detail what you have marked. Plus we can discuss each topic. This means there is a proper page for topic reviews and comments to the original author to use. The editting history is saved and can always be rolled back to. There are options of locking your articles from free editors to rgistered ones so that you atleast have their track.
Unity of theme: one good thing that has come up with the bad editor is the maintainance of the look and the theme. Every page on wikipedia is similar in font, font size, heading style. this makes it look formal and presentable. It looks like a set rather than just a collection.
Culture: wikipaedia has maintained its own culture of openess and helfulness. All code is available. Peopel are ready to show how to work, and maintain the read posts for help recent. The postings form a proper forum where there is everthing a person want ( maybe not proper topics).
I accept that some of the things are really great. Cheers to them!!!

Google Code Jam Answer 3  

Posted by Unknown in ,

This one was too good a question for me. i did something couldn't pass out. I have joined topcoder for practice - all people out there help me improve.....
Fly Swatter
Problem

What are your chances of hitting a fly with a tennis racquet?

To start with, ignore the racquet's handle. Assume the racquet is a perfect ring, of outer radius R and thickness t (so the inner radius of the ring is R−t).

The ring is covered with horizontal and vertical strings. Each string is a cylinder of radius r. Each string is a chord of the ring (a straight line connecting two points of the circle). There is a gap of length g between neighbouring strings. The strings are symmetric with respect to the center of the racquet i.e. there is a pair of strings whose centers meet at the center of the ring.

The fly is a sphere of radius f. Assume that the racquet is moving in a straight line perpendicular to the plane of the ring. Assume also that the fly's center is inside the outer radius of the racquet and is equally likely to be anywhere within that radius. Any overlap between the fly and the racquet (the ring or a string) counts as a hit.

Input

One line containing an integer N, the number of test cases in the input file.

The next N lines will each contain the numbers f, R, t, r and g separated by exactly one space. Also the numbers will have at most 6 digits after the decimal point.

Output

N lines, each of the form "Case #k: P", where k is the number of the test case and P is the probability of hitting the fly with a piece of the racquet.

Answers with a relative or absolute error of at most 10-6 will be considered correct.

Limits

f, R, t, r and g will be positive and smaller or equal to 10000.

t < style="font-weight:bold;">Nothing to speak man here is what rem wrote:

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;

typedef long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;

#define _CRT_SECURE_NO_WARNINGS
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Ford(i,a,b) for (int i(a),_b(b); i >= _b; --i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
#define Repd(i,n) for (int i((n)-1); i >= 0; --i)
#define Fill(a,c) memset(&a, c, sizeof(a))
#define MP(x, y) make_pair((x), (y))
#define All(v) (v).begin(), (v).end()

template<typename T, typename S> T cast(S s) {
stringstream ss;
ss << s;
T res;
ss >> res;
return res;
}

template<typename T> inline T sqr(T a) { return a*a; }
template<typename T> inline int Size(const T& c) { return (int)c.size(); }
template<typename T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template<typename T> inline void checkMax(T& a, T b) { if (b > a) a = b; }

const double pi = 2*acos(0.0);
const double eps = 1e-9;

double asin2(double x) {
double res = asin(max(-1.0, min(1.0, x)));
assert(-pi/2 <= res && res <= pi/2);
return res;
}

double inters(double x1, double y1, double x2, double y2, double r) {
assert(x1 <= x2 && y1 <= y2);
assert(sqrt(sqr(x1)+sqr(y1)) <= r);
if (sqrt(sqr(x2)+sqr(y2)) <= r)
return (x2-x1)*(y2-y1);
vector<double> xs;
xs.push_back(x1);
xs.push_back(x2);
double x = sqrt(sqr(r)-sqr(y1));
if (y1 < r && x1 < x && x < x2)
xs.push_back(x);
x = sqrt(sqr(r)-sqr(y2));
if (y2 < r && x1 < x && x < x2)
xs.push_back(x);
if (x1 < r && r < x2)
xs.push_back(r);
sort(All(xs));
double res = 0;
Rep(i, Size(xs)-1) {
double x1 = xs[i], x2 = xs[i+1];
if (x1 > r-eps)
break;
double s1 = y1*(x2-x1), s2 = y2*(x2-x1);
double s4 = (0.5*x2*sqrt(sqr(r)-sqr(x2))+0.5*sqr(r)*asin2(x2/r))-(0.5*x1*sqrt(sqr(r)-sqr(x1))+0.5*sqr(r)*asin2(x1/r));
double s3 = -s4;
res += max(0.0, min(s2, s4)-max(s1, s3));
}
assert(res <= (x2-x1)*(y2-y1));
return res;
}

int main() {
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);

int t;
scanf("%d", &t);
For(test, 1, t) {
double f, R, t, r, g;
scanf("%lf%lf%lf%lf%lf", &f, &R, &t, &r, &g);
double sum = 0;
if (g > 2*f) {
double x = r;
while (x+f < R-t-f) {
double y = r;
while (sqrt(sqr(x+f)+sqr(y+f)) < R-t-f) {
sum += inters(x+f, y+f, x+g-f, y+g-f, R-t-f);
y += 2*r+g;
}
x += 2*r+g;
}
}
printf("Case #%d: %.6lf\n", test, (pi*sqr(R)-4*sum)/(pi*sqr(R)));
}

exit(0);
}



Everyone out there help me improve!!!

Google Code Jam Answer 2  

Posted by Unknown in ,

Again a bad answer by me. But was easy to write and correct in attempt 1:
Train Timetable
Problem

A train line has two stations on it, A and B. Trains can take trips from A to B or from B to A multiple times during a day. When a train arrives at B from A (or arrives at A from B), it needs a certain amount of time before it is ready to take the return journey - this is the turnaround time. For example, if a train arrives at 12:00 and the turnaround time is 0 minutes, it can leave immediately, at 12:00.

A train timetable specifies departure and arrival time of all trips between A and B. The train company needs to know how many trains have to start the day at A and B in order to make the timetable work: whenever a train is supposed to leave A or B, there must actually be one there ready to go. There are passing sections on the track, so trains don't necessarily arrive in the same order that they leave. Trains may not travel on trips that do not appear on the schedule.

Input

The first line of input gives the number of cases, N. N test cases follow.

Each case contains a number of lines. The first line is the turnaround time, T, in minutes. The next line has two numbers on it, NA and NB. NA is the number of trips from A to B, and NB is the number of trips from B to A. Then there are NA lines giving the details of the trips from A to B.

Each line contains two fields, giving the HH:MM departure and arrival time for that trip. The departure time for each trip will be earlier than the arrival time. All arrivals and departures occur on the same day. The trips may appear in any order - they are not necessarily sorted by time. The hour and minute values are both two digits, zero-padded, and are on a 24-hour clock (00:00 through 23:59).


After these NA lines, there are NB lines giving the departure and arrival times for the trips from B to A.


Output
For each test case, output one line containing "Case #x: " followed by the number of trains that must start at A and the number of trains that must start at B.

Limits

1 ≤ N ≤ 100

Small dataset

0 ≤ NA, NB ≤ 20

0 ≤ T ≤ 5

Large dataset

0 ≤ NA, NB ≤ 100

0 ≤ T ≤ 60

Sample
Input
2
5
3 2
09:00 12:00
10:00 13:00
11:00 12:30
12:02 15:00
09:00 10:30
2
2 0
09:00 09:01
12:00 12:02

Output
Case #1: 2 2
Case #2: 2 0

My answer - agin bad but I got a hold of OOPS

// train.cpp : Defines the entry polong int for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;
class train
{
public:
long int presentstation;
long int availableafter;
long int turnaround;
public:
void reachstation(long int station,long int time)
{
presentstation = station;
availableafter = time+turnaround;
}
void settrain(long int tt)
{
turnaround = tt;
}

};
class time
{
public:
long int start;
long int end;
long int station;
public:
void settime(long int Station,char* time)
{
station =Station;
start = (time[0] - '0') *600 + (time[1] -'0')*60 + (time[3] - '0')*10 + (time[4]-'0');
end = (time[6] - '0') *600 + (time[7] -'0')*60 + (time[9] - '0')*10 + (time[10]-'0');
}
};
int comp(const void *A,const void *B)
{
time *p = (time*) A;
time *q = (time*) B;
return (int) (p->start - q->start);
}
long int main()
{
long int no =0;
cin>>no;
for(long int counter = 1; counter<=no;counter++)
{
printf("Case #%d: ",counter);
long int turnaround = 0;
long int NA,NB;
cin>>turnaround;
cin>>NA>>NB;
char useless[7];
if(NA+NB != 0 )
{gets_s(useless);
}
time Time[200];
train Train[200];
long int NoTrains = 0;
char a[100];
for(long int i=0;i<NA; i++)
{
gets_s(a);
Time[i].settime(0,a);
strcpy_s(a,"");
}
for(long int i=NA;i<(NB+NA); i++)
{
gets_s(a);
Time[i].settime(1,a);
}
qsort(Time,NA+NB,sizeof(time),&comp);
//printf("%d\t%d\t%d",Time[0].start,Time[1].start,Time[2].start);
long int flag;
long int startA=0,startB=0;
for(long int i=0; i<NA+NB; i++)
{
flag=0;
for(long int j=0;j<NoTrains; j++)
{
if((Train[j].availableafter <= Time[i].start) && (Train[j].presentstation == Time[i].station))
{
Train[j].reachstation(1-Time[i].station,Time[i].end);
flag=1;
break;
}
}
if(flag==0)
{
Train[NoTrains].settrain(turnaround);
Train[NoTrains].reachstation(1-Time[i].station,Time[i].end);
NoTrains++;
if(Time[i].station == 0)
startA++;
else
startB++;
}
}
printf("%d %d\n",startA,startB);

}
return 0;

}


and the great answer by rem


#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;

typedef long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int,int> pii;

#define _CRT_SECURE_NO_WARNINGS
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Ford(i,a,b) for (int i(a),_b(b); i >= _b; --i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
#define Repd(i,n) for (int i((n)-1); i >= 0; --i)
#define Fill(a,c) memset(&a, c, sizeof(a))
#define MP(x, y) make_pair((x), (y))
#define All(v) (v).begin(), (v).end()

template<typename T, typename S> T cast(S s) {
stringstream ss;
ss << s;
T res;
ss >> res;
return res;
}

template<typename T> inline T sqr(T a) { return a*a; }
template<typename T> inline int Size(const T& c) { return (int)c.size(); }
template<typename T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template<typename T> inline void checkMax(T& a, T b) { if (b > a) a = b; }

int readTime() {
int h, m;
scanf("%d:%d", &h, &m);
return m+60*h;
}

int main() {
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);

int t;
scanf("%d", &t);
For(test, 1, t) {
int t;
scanf("%d", &t);
int n1, n2;
scanf("%d%d", &n1, &n2);
vector<pii> t1(n1), t2(n2);
Rep(i, n1) {
t1[i].first = readTime();
t1[i].second = readTime();
}
Rep(i, n2) {
t2[i].first = readTime();
t2[i].second = readTime();
}
sort(All(t1));
sort(All(t2));
int r1 = 0, r2 = 0;
while (Size(t1) > 0 || Size(t2) > 0) {
int x;
if (Size(t2) > 0 && (Size(t1) == 0 || t2[0] < t1[0])) {
++r2;
x = t2[0].second;
t2.erase(t2.begin());
} else {
++r1;
x = -t;
}
for (;;) {
int i = 0;
while (i < Size(t1) && t1[i].first < x+t)
++i;
if (i == Size(t1))
break;
x = t1[i].second;
t1.erase(t1.begin()+i);
i = 0;
while (i < Size(t2) && t2[i].first < x+t)
++i;
if (i == Size(t2))
break;
x = t2[i].second;
t2.erase(t2.begin()+i);
}
}
printf("Case #%d: %d %d\n", test, r1, r2);
}

exit(0);
}

See how much I need to improve answer 3 in next post

Google code Jam : i am not a contest programmer  

Posted by Unknown in ,

I may be among the best programmers of my batch in my college but definitely I am not worth calling myself as a programmer. I am far from a standard contest programmer for my programs are still those written on college papers. Plus I am still new to the STl and the contest world. i have just had a few outings. But I plan to have massive changes to this state this year. I have started with the google code jam, a big programming contest popularised by google for programmer's all over the world. The contest had its qualifiers on thursday and indeed as said qualifiers are for only to sort out people who don't know what programming is, it came out. The first question was sort of easy and so was the second one( Even i could do that). But the third one was gud. Just not really as an article I write this posting to my blog to help me trace if i can improve as a programmaer this year. You can expect to see top coder contest codes to be here as well, for I just joined that.
Here is the link to the files Ques+Mine as well as ideal answers + Hope I see this next year:http://w14.easy-share.com/1700957331.html
I have converted the cpp to html. I have used a project at codeproject. The files are at:http://w14.easy-share.com/1700966549.html
So now I can paste the stuff here:
Saving the universe
Problem

The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding.

The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!

To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

Input

The first line of the input file contains the number of cases, N. N test cases follow.

Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.

The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.

Output

For each input case, you should output:
Case #X: Y
where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.


Limits

0 <>Input
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Output
Case #1: 1
Case #2: 0

So here is what I managed: Not good but i need to keep a track of myself.



// savetheuniverse.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"
#include<iostream>
#include<string.h>
#include<conio.h>
#include<stdio.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int no =0;
cin>>no;
for(int counter = 1; counter<=no;counter++)
{
printf("Case #%d: ",counter);
int NoOfEngines = 0;
cin>>NoOfEngines;
char useless[7];
if(NoOfEngines != 0 )
gets_s(useless);
//cout<<NoOfEngines<<endl;
char Eng[1000][100];
int CalledEng[1000] = {0};
for (int Engine = 0;Engine<NoOfEngines;Engine++)
{
gets_s(Eng[Engine]);
//cout<<Eng[Engine]<<endl;
}
int NoOfSearches;
cin>>NoOfSearches;
//cout<<NoOfSearches<<endl;
if(NoOfSearches != 0 )
gets_s(useless);
char Sear[1000][100];
for(int Search = 0;Search <NoOfSearches; Search++)
{
gets_s(Sear[Search]);
//cout<<Sear[Search]<<endl;
}

int Present = 1;
int LastElementIndex=0;
while(1)
{

for(int i=LastElementIndex;i<NoOfSearches;i++)
{
for(int j=0;j<NoOfEngines;j++)
{
if(strcmp(Sear[i],Eng[j]) == 0)
{

if(CalledEng[j] != Present)
{
CalledEng[j] =Present;
LastElementIndex = i;
}
break;
}
}
}
//if(counter==8)
//printf("%d\t%d\n",Present,LastElementIndex);
int flag=0;
for(int i=0;i<NoOfEngines;i++)
{
if(CalledEng[i]<Present) {flag =1 ;}
}
if(flag==1) {break;}
Present++;
if(LastElementIndex >= NoOfSearches-1) break;
}
printf("%d\n",Present-1);
}
return 0;
}



And this was the ideal answer

#include <map>

#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;

typedef long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;

#define _CRT_SECURE_NO_WARNINGS
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Ford(i,a,b) for (int i(a),_b(b); i >= _b; --i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
#define Repd(i,n) for (int i((n)-1); i >= 0; --i)
#define Fill(a,c) memset(&a, c, sizeof(a))
#define MP(x, y) make_pair((x), (y))
#define All(v) (v).begin(), (v).end()

template<typename T, typename S> T cast(S s) {
stringstream ss;
ss << s;
T res;
ss >> res;
return res;
}

template<typename T> inline T sqr(T a) { return a*a; }
template<typename T> inline int Size(const T& c) { return (int)c.size(); }
template<typename T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template<typename T> inline void checkMax(T& a, T b) { if (b > a) a = b; }

char buf[1024*1024];

int main() {
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);

gets(buf);
For(test, 1, atoi(buf)) {
int s, q;
map<string,int> num;
gets(buf);
s = atoi(buf);
Rep(i, s) {
gets(buf);
num[buf] = i;
}
gets(buf);
q = atoi(buf);
vi dp(s, 0);
Rep(i, q) {
gets(buf);
assert(num.count(buf) > 0);
int id = num[buf];
Rep(j, s)
if (j != id)
checkMin(dp[j], dp[id]+1);
dp[id] = 1000000;
}
printf("Case #%d: %d\n", test, *min_element(All(dp)));
}

exit(0);
}

I'll write answer 2 and 3 in a seperate post

Articles to wikipedia - tougher than expected  

Posted by Unknown in

    Recently I had been writing articles for my college techfest Aranya at wikipedia. It was there that I realized what wikipedia we see is not even half of it. They have really done a fine job writing articles for the editor, I don't think does not match any high class. Even the blog editor and the mail editor provide basic features of WYSIWYG. But it seems that despite managing the world's biggest encyclopaedia, the makers have not even added a good enough editor. Atleast enter shoud have been recognisable rather than a tag. High time man, this encyclopaedia gives a tough time editting. their sandbox is just a viewer rather than an editor. I see that they have done a fine job with the templates section keeping the coding open for people to modify but how do they expect people from far off places to write out articles when it is so confusing. The only support i think we have is to paste and add stuff later. We can't even write to our favourite word editor and put the stuff there. For the formatting is gone without a reason. 

   
Editor: You can't start a paragraph with a few white spaces as is normal paragraph formatting. And indeed if we closely notice the articles they either are fully indented or start at the right edge. It is html we are writing, just that it is outside the tag for that is what they have generated. They don't have a simple editor, to say the least. They may be having WikiEd for the users to install as a plugin but that is not the way to deal with the issue. In modern day people are not installing plugins. Plus there is no support for IE 7 and Opera 9. Opera 9 has been in market for so much of time and as far as IE is concerned people are concerned with mostly the IE 8 which is supposed to be highly strict on web developers, and if your site cannot run on the linient 7 forget the strict 8. And I think same will be the case for 8. What the makers need is a team of people who could make some cool stuff for wikipedia and help attract editors. Plus it also require the save now as in the blogger, where you can save your post not for publishing it but because it is incomplete, or yet not formatted well enough. Atlest help add an under construction tag. I started with my article and I opened it next day. Somebody had marked {{Afd}} meaning article for deletion and it would have been deleted in five days if I had not seen it. In such cases think of it if a person decides to write an aricle and just gives it a name. That's how wikipedia they said works. But now its time for expansion, to add articles that were not a part of it straight, that are localized and will become internationalized with time. So people who are there don't know about the stuff and label it. People in regions like India are normally not heavy web users and editors and liek this to start off an article is tough. Plus there is no ABC or the famous check your spelling and basic grammar. They say its not perfect, but its better than nothing. Is it meaningful if people have to again and again change a little words in their article??


   Support: I haven't seen flash and videos in Wikipaedia. The encyclopaedia does not support these. Quite strange, because you cannot definitely say that encyclopaedia should not contains these stuff. With youtube going global and giving great video integration properties, no one can understand why don't they have a proper integration with youtube. I don't think the editors would not wanr videos in their articles and also don't think that keeping a check on videos will be tough. It seems to be simply just that wikipedia wants to isolate itself from everything else on the internet.  That's not sportsmanship. Not even the thing that could benefit the world. I know they are scared of marketization as well as vandalism to everyon'e favourite encyclpaedia, but that does not justify video non - integration as properly as to have it in articles. We seem to remember the legendry CD-DVD based encyclopaedias of Britannica and Encarta when it comes to video and flash content. Researchers would be happy to share their research videos on wikipaedia for the work remains as their's and people might learn something from them.

Coming on to flash, it can be a two sided issue - many would say yes and many no. Wikipaedia is maintained by editors and not by technical geniuses and so we can pardon them for not having interactive flash content on their sites. But still look at the world around. Flash and javascript are a part and parcel of world wide web. People would love to add quizzes and all after their articles. Say make it a sister project where people can make interactive stuff and link it to the encyclopaedia. I don't find a meaning why that is not possible. Wikipedia has tried to live in the world where there are limitations so that its safe. In the end they are a non profit organization and so the people are doing it for virtually nothing. Still I think, with the open source world having so much into it, if you try out you'll easily find people who would like to contribute and make the encyclopaedia come to life.


Content structure : look at the size of articles they have on the encyclopaedia. It is huge. Would it not have been fair to have it two paged rather than one paged. Paging of articles can help improve readability, decrease loading time and the most importanmtly improve the structure and looks of the text. It is strange that the usera make themselves new articles and link them to the original one to get the content spread. So again even if they try to write it structured it is not. they have a contents heading at the top. Why not make content that is bigger spread into pages across the same article. Everyone is using tabs fot this purpose. If not tabs they can use a set of navigation buttons around articles and its subheads. If even not that atleast add a + - tree button that could minimize sections of the article. That is the demand of readibility.

I don't write all this to criticize among the best things of the world wide web. i write this because I've seen this in wikipaedia and its my personal feeling. Everyone is free to write what he feels and as a computer science fan, i have just highlighted some basic technical stuff that wikipaedia could use.

Visual C++ Dllexports and Dllimports : How can we and how not?  

Posted by Unknown in

                                         I don't know wether that would be a cool way to start of the blog, but then this blog is to help others and since I had to really work hard to get my basic dlls working with Visual Studio 2005, using C++, i thought this gotto be in my blog. So here goes.....(I am writing all this best to my knowledge and do not claim it to be absolutely correct. I am still a college student so forgive em but do tell me if anything is wrong.)

DLLs What and Why?

This I am copying from Microsoft's definition of the dll, but well otherwise you would have said incomplete. 

A dynamic-link library (DLL) is an executable file that acts as a shared library of functions. Dynamic linking provides a way for a process to call a function that is not part of its executable code. The executable code for the function is located in a DLL, which contains one or more functions that are compiled, linked, and stored separately from the processes that use them. DLLs also facilitate the sharing of data and resources. Multiple applications can simultaneously access the contents of a single copy of a DLL in memory.

In my words, DLL is just a set of classes and functions that we think are required to be seperate from the main program for whatever the reason, let it be reuse, memory, distribution, cross-platform use etc.  So set out and build your first DLL.

Note that dlls are of two types: Static and Dynamic. A static dll is the one which has to be loaded at the compile time while the dynamic can be loaded at the run time.

What can you export?

You can export functions, classes, member elements from inside a dll. since the process involved is almost similar, i'll be demonstarting only the export of functions.

Building a CPP DLL: Building a CPP dll is not at all tough using visual studio. 

  1. Select File>New>Project.
  2. Select Visual C++>Win32/Smart Device>Console Application.
  3. In the Application Settings select DLL, Export symbols.
  4. With this you will get to a file where everything would be set up.
  5. In the file produced it will have already a definition of an exported variable, function as well as a class. so u can use that rename that and do whatever you wish to.
  6. Remember keeping a track of the header file present as that header file will need to contain information about your exports.

Sample C file generated

Header File

Because I think you would have got my point so I'm copying down the filename and the code from MSDN:

// MathFuncsDll.h

namespace MathFuncs
{
  class MyMathFuncs
  {
  public:
  // Returns a + b
__declspec(dllexport) double Add(double a, double b);

  // Returns a - b
 __declspec(dllexport) double Subtract(double a, double b);

  // Returns a * b
   __declspec(dllexport) double Multiply(double a, double b);

  // Returns a / b
  // Throws DivideByZeroException if b is 0
 __declspec(dllexport) double Divide(double a, double b);
  };
}

// MathFuncsDll.cpp

#include "MathFuncsDll.h"

#include

#include "stdafx.h"
using namespace std;

namespace MathFuncs
{
  double MyMathFuncs::Add(double a, double b)
  {
  return a + b;
  }

  double MyMathFuncs::Subtract(double a, double b)
  {
  return a - b;
  }

  double MyMathFuncs::Multiply(double a, double b)
  {
  return a * b;
  }

  double MyMathFuncs::Divide(double a, double b)
  {
  if (b == 0)
  {
  throw new invalid_argument("b cannot be zero!");
  }

  return a / b;
  }
}

The new terms you might have faced include the '__declspec' and 'dllexport'. You might be able to guess 'dllexport' as to be requiring for export. __declspec is calling convention for the function, for a detailed note on which refer here or you can refer to MSDN

Issue of Name Mangling:Name mangling is the concept where the function is referred to using some terms more than the function name. Basically it is not enough in case of overloading, that we can refer to a function by its name. So the only way to refer to a function was via the full prototype. Now due to the problem of the presence of spaces in prototype and a deliberate attempt to save size, some encryption was done to the code resulting in a mangled code. For example:?terminate@std@@YAXXZ  is the mangled name to void __cdecl std::terminate(void). You can refer to more about this in wikipedia.  

Why I giving you all this is so that you don't have confusion in case you have error messages and also because mangling differentiate's between a C type and a C++ or OOPs type export. 

Also note that you have an option of having an undecorated(or unmangled) code in C++, by using the extern "C" words in the exports, such that the new header has:

extern "C" __declspec(dllexport) double Add(double a, double b);  

instead of  __declspec(dllexport) double Add(double a, double b);

Using CPP to import a CPP DLL: The DLLs can be loaded by other progg. languages as well. But here I write how to load it in CPP, which I think is the reason this article is here. I thas not been updated well on the web and that's why people have been facing problems.

Okay, so here it is... A dll once created can be referenced in another in two ways:

1) Static Linking                           2) Dynamic Linking.

Static Linking: Static linking is when the dll gets imported at compile time. The functions are not loaded but the compiler has an idea of which dll to import and indeed it is reference in the code. Static Linking is normally associated with static libraries (.lib files) but since it is possible with dlls, I don't mind mention it here.

  1. Select File>New>Project
  2. Select Visual C++>Win32/Smart Device>Console Application.
  3. There you are ready to set up stuff.

But static linking does not take place as easily in visual C++, as compared to visual C#, i don't know why. MSDN talks of adding references from add reference but no such references are vailable. That's where people are stuck up many times. Okay so, what you have to do is forget that article,

     4.  Go to Project>Add Existing Item><>

     5. Do all files and select the .lib file.

The .lib file to be selected.

This vital step links out the dll to your project. Now you can write your code which again i am copying from MSDN.

// MyExecRefsLib.cpp

#include "stdafx.h"

#include "MathFuncsLib.h"

using namespace std;

int main()
{
  double a = 7.4;
  int b = 99;

  cout << "a + b = " <<   MathFuncs::MyMathFuncs::Add(a, b) << b = " <<   MathFuncs::MyMathFuncs::Subtract(a, b) << endl;   cout << " b = " <<   MathFuncs::MyMathFuncs::Multiply(a, b) << endl;   cout << " b =" ">

where the unmentioned MthFuncsLib. h is:

// MthFuncsLib. h

namespace MathFuncs
{
  class MyMathFuncs
  {
  public:
  // Returns a + b
  static __declspec(dllimport) double Add(double a, double b);

  // Returns a - b
  static __declspec(dllimport) double Subtract(double a, double b);

  // Returns a * b
  static __declspec(dllimport) double Multiply(double a, double b);

  // Returns a / b
  // Throws DivideByZeroException if b is 0
  static __declspec(dllimport) double Divide(double a, double b);
  };
}
(Note that we will require the static keyword to be present in the library definition as well)

If you compile and run this you get the output as specified at MSDN:

a + b = 106.4
a - b = -91.6
a * b = 732.6
a / b = 0.0747475
 Of course you will need your dll to be present in the debug/release folder.

Dynamic Linking: Dynamic Linking is runtime, that is the process is loaded at the runtime. The compiler has no clue which dll will be loaded and its actual address is referenced in the code. i am not sure functions exported from within the class can be as easily accessed dynamically as from outside or as is the whole class. Thus I am using the function present outside the code of the class:

// AddDll.cpp : Defines the entry point for the DLL application.
//

#include "stdafx.h"
#include "AddDll.h"
#include
#include

BOOL APIENTRY DllMain( HANDLE hModule, 
  DWORD ul_reason_for_call, 
  LPVOID lpReserved )
{
 switch (ul_reason_for_call)
 {
 case DLL_PROCESS_ATTACH:
 case DLL_THREAD_ATTACH:
 case DLL_THREAD_DETACH:
 case DLL_PROCESS_DETACH:
  break;
}
 return TRUE;
}


// This is an example of an exported function.
      ADDDLL_API int Add(int a,int b)
     {
                 return (a+b);
     }
     ADDDLL_API float Add(float a,float b)
     {
                 return a-b;
     }
}

//AddDll.h

#ifdef ADDDLL_EXPORTS
#define ADDDLL_API extern "C" __declspec(dllexport)
#else
#define ADDDLL_API __declspec(dllimport)
#endif

ADDDLL_API int Add(int a,int b);
Again for dynamic loading you 'll need to follow the basic step:

  1. Select File>New>Project
  2. Select Visual C++>Win32/Smart Device>Console Application.
  3. There you are ready to set up stuff.

Now you can write down the to access the dll dynamically:

//CallAddDll.cpp

#include

#include "stdafx.h"

using namespace std;

int main()
{  

       typedef int (__cdecl *ptrFunc) (int, int) ;
       ptrFunc Add;
       HINSTANCE handle = LoadLibrary(L"C:\\AddDll.dll") ;
       if(handle!=NULL)       {
                   Add= (ptrFunc) (GetProcAddress(handle,L"Add") );
                    if(Add!=NULL)
                     {
                                    printf("Result = %d",Add(4,5));
                      }
                       else
                      {
                                    printf("Could Not Load Function! Add");
                       }

       }
       else
       {
                           printf("Could not attach DLL!");
       }

       FreeLibrary(handle);
       return 0;

}

I hope you got a basic idea, for all those who needed help. all suggestions are welcome......

Welcome to the world of AJ  

Posted by Unknown

Hiii to all,

I am Atishay Jain and I prefer you skip this post because this will the usaul boring piece that a person writes to his first blog post. I'll be comin up with some good stuff in teh posts that follow.

So, finally I've decided to come up with my first blog - I had been resistive for quite some time because of time...... no maybe I didn't feel like writing up that much. I am quite an object oriented peson, can't realyy waste out time on something that I don't feel worthwhile. Then, why am I here. Well its a demand of time, the present of the world. Everyone looks up to you to be having a personal blog, fuilled up with content to get an insight into your fields of likings, your passions and maybe to help learn from where you fell down, for life has always been a fall down and write up case. I have had my lucky times and indeed am in the peak of one working at Microsoft IDC for a summer internship, that too after just my second year of B-Tech degree, where I in first year I was studying as a electronics student and shifted over to computers only an year back. Well luck has its day, todqay or maybe everyday.

Soon I'll start filling it up with stuff, so I should tell you what this blog will be going to be about - I won't give you much stuff outside computers and movies because my world is a sort of limited to these and definitely I'm not the one to be free enough to write out any other stuff, and even these whenever i have time. Just to list out stuff you might find here - sth related from 3rd yr engg, CS - my experiences as an MS intern, progg contests, website designing, Aranya-Thapar University's techfest, Adobe flash & Photoshop, maybe 3ds Maxand the list can go on.... Happy reading.