Planning to study Bachelors of Computer Science at University?

Students come to university to get a computer science degree for several reasons and here are few of them:

1. They want to get a computer science degree and get a job in country X in the field of Software.
2. They just want to get a degree and then go back to their country (generally international students)
3. They already decided at a very young age (say 12 - 16) that they wanted to study Computer Science. They know exactly what they want to do in life.

This article is for students whose reason is (1) i.e. they want get a bachelor's degree and then work in country X / Y in the field of Software development.

It starts here:

There are some questions every 18 year old student coming here to study computer science should ask himself.

1. Is university here to make sure you graduate with excellent grades and get a job that you like?
2. No they are not here for that. They are here to take your money. That's right, they are only interested in your money. But you might say - no way, it doesn't look like that from outside. You will never realize this during the degree. However this is the reality and you will realize it after graduating and then struggling to get a job (if you don't have good grades and good communication skills). Go to the job search website www.seek.co.nz and search for graduate jobs in the field of computer science / IT. I have never seen more than 50 results. Now what you don't know is that the only way you are going to find a job after graduation if you have any of the following two things:
(a) Excellent Grades
(b) Good communication skills
(c) Some extra software development work which you did by yourself during university time.

More later......

ACM Timus - 1794

Here is the problem which was baffling me for quite some time :

http://acm.timus.ru/problem.aspx?space=1&num=1794

The problem description is quite clear. In summary, there are students sitting in a circle and a teacher would be asking each of them some questions which are part of a test. Each student has their own choice as to when they would like to go give the test. The teacher will ask questions in clockwise order only and can start from anyone of them. The choices of the students are represented as this:

4 (number of students)

4 1 2 3 (their choices)

This means:

1st student would like to give the test at 4th position.
2nd student would like to give the test at 1st position. (He wants to go first, may be he is well prepared !!)
3rd student would like to give the test at 2nd position.
4th student would like to give the test at 3rd position.

In this case the teacher should start asking questions from the 2nd student because then each one of them will get the choice of their own, like this (remember that the students are sitting in the circle)
4 1    2     3
4th 1st 2nd 3rd

First Approach

Since I already knew from others the problem has an O (n) solution, I straightaway went looking for that. At first I thought we might need to look for longest increasing continuous sequence of numbers and that might be the answer. So in the above the longest increasing sequence is 1 2 3 and then 4 as all students are sitting in a circle. I drew out some cases and it failed there.


Second Approach : O(n^2)

Then I went for brute force approach. Start at every position and then see for which one you get the most correct positions. So for the above input:

4 1 2 3

1 2 3 4
4 1 2 3
4 3 1 2
4 3 2 1

For the second case we met the most matches (4) and so the answer is 2. The teacher should start asking from the second student onwards. The problem is this algorithm is n^2 and for n = 10^5, the loop will run 10 billion times which times out on their server.

Third Approach : O(n)

The key is to realize what's going on here. Let's look at the input again.

4 1 2 3
First student is saying that he wants to go fourth. Basically this means he wants the second student to go first.
Second student is saying that he wants to go first. This means he wants himself (second student) to go first.
Third student is saying that he wants to go second. This means he wants second student to go first.
Similarly fourth student is saying that he wants to go third. This means he wants second student to go first.

So basically we can replace "4 1 2 3" with "0 4 0 0". Now you can look at this as the votes received by each student from some other student or himself. Now we just need to see who received most votes. As an exercise you can try doing the following case:

5
3 3 1 5 5
This will get replaced by "1 0 1 1 2". The most votes were received by 5th student and so answer is 5. The reason 5th student got 2 votes is because 2nd and 4th student wants 5th student to go first.

Varun