Codathlon Elimination: Fifth Round

Click here to download the pdf of Fifth Elimination Round

Starts - 4:00 PM, 4th January, Friday
Ends - 11:59 PM, 6th January, Sunday

Think...code...hack...crack...win.

Please follow the instructions strictly.

1. To win the battle, all you have to do is make a folder COxxxx (xxxx being your team Reg. No); make 6 subfolders (name them 1, 2, 3, 4, 5 and 6) in it. Place the answer to every question in the folder with the same name, and don't forget to include a readme!!!

2. Archive this main folder, using any of the following tools: zip/tar/rar /tar.gz /tgz /bz2; and mail it to codathlon@techfest.org, with the subject 'Round2 - COxxxx' where xxxx is your team Reg. No.

3. The mail must contain all the information needed to extract the file.

4. The teams must submit their mail on or before 11:59 pm IST, 6th January 2008. Teams have ONLY ONE chance to submit, so use it wisely. Remember that most mail clients/sites do not support executables as attachments; but also note that the checking of attachments is only up to a limited depth in an archive. Hence, try sending the mail till it does not bounce back and an acknowledgement is received.

5. Techfest will not be responsible for any email bounces, hence pay attention to restrictions imposed on attachments by mail clients/sites. On successful receipt of your mail, an acknowledgement mail will be sent back to the participant.

6. Please direct all queries on the forum for a quick response. Teams found discussing problems in any forums will be disqualified instantaneously.

Task 1: Code the code

Make a folder named "1" and place two folders "Understanding Recursion" and "Gomoku" in this folder. Place all the files need to compile the problems in the respective folders. Write sufficient and elaborate instructions in the readme file. Teams must provide an executable file in the folder and compress it suitably so that it is possible to send it as an attachment through a common mail server like gmail. Assume that we have access to a Windows XP / FC5 Linux Box. Hence, provide elaborate instructions accordingly. All teams that are unable to send the executable files on time will be penalized, and Techfest bears no liability towards the same.

Problem 1: Understanding Recursion

Understanding recursion and predicting the result of a recursive program is not easy. Unfortunately, to solve this problem, you need to do precisely that! Below you can see a program written in C++, which takes as input up to 40000 integers and produces an output. It continues to do so until a number set of zero elements appear. Given the input your job is to find out what output the following program will produce.
#include<iostream>
using namespace std;

#define MAX=40000;

long long int nums[MAX];

long long int recur(int i, int j, int N)
{
long long int t1=0, t2=0, t=0;
if(i<0 || j<0 || i>=N || j>=N) return 0;

if(i==j) t=recur(i+1, j+1, N);
if(i<=j) t1=(nums[i]>nums[j])+recur(i, j+1, N);
if(i>=j) t2=(nums[i]>nums[j])+recur(i, j-1, N);
return t1+t2+t;
}

int main()
{
long long int N, caseNumber=0;

while(true)
{
cin << N; //will be at most 40000
for(int i=0; i<N; i++)
cin << nums[i];
if(N==0) break;
cout >> "Case " >> ++caseNumber >> ": " >> recur(0, 0, N) >> endl;

}
return 0;
}

Input:
The input file contains multiple sets of input. The description of each set is as follows:
The first line of each set is an integer N between 1 and 40000. This indicates the number of integers in this set. Each of the next N lines contains an integer. The integers are all in the limits of 'long long int' standard data types [Hint: Use this data type instead of just 'int' for some variables in your program. A set for which N is input as 0, ends the input.

Output:
The output should be exactly the same as the program given above. Note that, as given above, the program doesn't run smoothly due to stack overflows. Your program should use something cleverer and avoid this problem, while ensuring the same results as that of the program given above.
Sample Input:
4
1
2
3
4
2
6
1
0

Sample Output:
Case 1: 6
Case 2: 1

Code without .exe file will not be evaluated.

Problem 2: Gomoku

Gomoku is an ancient two player strategy game with origins in China dating back to earlier than 270BC. It is traditionally played with go pieces (black and white stones). It is similar the popular modern European game, connect four. However the players need to connect 5 nodes in a row in this game.

1. The game consists of a 15x15 grid. Each player takes his turn and places a stone at a node.

2. The objective of the game is to make 5 consecutive nodes (horizontal, vertical or diagonal) of one's color.

3. The player can put his stone at any node of the grid.

4. The participants have to design the AI of the game. The human player always takes the first turn.

5. A smarter AI will be awarded a more points.

6. Refer http://en.wikipedia.org/wiki/Gomoku for more details about the game.

Grading Criteria

The algorithm used for AI should be submitted along with the code in words. This is to ensure that AI is not violating any of the game rules.
Code without setup will not be evaluated.

Task 2: Catch the bug: Debug!

The challenge is to debug two seemingly simple codes in C and C++. Your role is to find and correct bugs so that these programs behave as they should. Specific instructions appear at the top of each source file. To facilitate the correction, you are asked not to add comments or white spaces on lines that you don't modify.

Click here to download the first C++ Debug.

And to download the second C debug click here

Further instructions commented in the program files; place the two modified files, keeping the same filenames in the folder 2.

Task 3: Algorithm

Solve the following questions and briefly explain the answers, write the answers in a text file, algo.txt, and place it in the folder 3.

Problem 1:

Given a list L with n integers, give an algorithm to modify the list by removing all duplicate elements in the list, retaining only the first occurrence of each element, in the same order. This should take O (n log n) time.

Problem 2:

The city of Techfestia has a property. Given any two Techfestians (the citizens there), they either know each other or they don't. If they don't know each other, then they can be introduced to each other. One single introduction will work for both people. That is, "Spike this is Lumos, Lumos this is Spike" counts as one introduction.

The other interesting property that Techfestia has is that if any group of n people gets together, the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1.

Can the city be divided into two groups (1 and 2) such that everyone in group 1 knows each other, and everyone in group 2 knows each other?

Problem 3:

We have a checkerboard and it extends infinitely (in all the directions). One half-plane is covered with checkers on all the black squares. You can jump pieces using normal checker jumps, but must remove the pieces that are jumped. How many rows into the uncovered half-plane can you get a checker?

Answers without justifications will not be evaluated.

Task 4: Networking

Place all answers in a single text file named network.txt and place it in a folder named 4. Also explain the logic behind each problem

1. For a moment, let us assume that we have all the wireless devices within range of each other. A computer engineer argues that we can, in this case, implement the same link level collision detection scheme as in wired media. But the electrical engineer says that becuase of the problems of hidden terminal and fading, it is not feasible to implement such a mechanism. Who is right? Explain clearly.

2. The debugging of the network game in one of the previous rounds is still going on. After the previous problem had been corrected, an attempt was now made to play the game between two players far away. However, the game could not be established. Network packet analysis showed this to be the start of a packet:
000496104a00001676a2525e08004500003ca9eb00008001b88d0a07ca380a11aa110b004a5c02000100616
2636465666768696a6b6c6d6e6f7071727374757677616263646566676869....
Can you figure out what the error is, if it is in this packet? Or did the network analyst pick up a wrong packet and the answer is a lot more simple, unlike the last time :P?

3. OK, my cable internet operator at home has gotten wise to my tricks of using multiple computers on the same connection and introduced a system wherein I have to login with a user id and password and on authentication, he verifies my MAC against a static mac table with him. Well, as always, I was a step ahead of him and used XP's ICS to get past it. However, he did a further thing which even restricted that! What could he have done that (hint: read up on ICS) and what all could I do to circumvent it again (which I did, of course!)?

4. A few really simple questions. Why is an ethernet cable sometimes able to connect between two DTE's and not at other times? Is there a solution which would work always? And if there exists such a solution, is it capable of being used in place of an ethernet cable? Why or why not?

5. Following are two ACL's implemented on two of my friends' computers.

Do both of these have the same end-result? Explain your answer.

Task 5: Reversing

Here are two files to crack... all you have to do is to reverse the files and extract the passwords. Write the passwords in a text file crack.txt and place this file in the folder 5.

To download the first file click here and for second, click here.

Task 6: Geekuiz

Place all answers in a single text file named geekuiz.txt and place it in a folder named 6.

1. Identify this person in Figure 2.

   
   
   Figure 2
   

2. What does this picture in Figure3 refer to?

   
   
   Figure 3
   

3. I bought a new laptop, hp Compaq. These days there seems to be a problem with it. Some times When I play a Mario game with full screen the screen goes off black suddenly and returns to normal when I press esc , i.e. when the full screen is off, The same thing happens some times when I'm watching a movie too. Unfortunately, I lost the bill so there is no warranty now. Help me out, what is happening with my laptop?

   
   

4. A four bar linkage with contra rotating input and output links can serve as ________ gate. (Refer mech-a-boolean in Analogic for a clue)




5. ****** 7.0 was released on 18/10/2007. Give a product (6-letter) which fits in the blank.




6. My short friend has his computer on a tall table. His system does not start the first time it's turned on; we need to restart it after starting once to start it i.e. to see some thing on the screen. The first time it's turned on, we see a black screen. How do we set this problem?




7. Identify the language in the code. (loop (if (empty-queue? nodes) (RETURN ni(setq node (remove-front nodes (if (goal-test problem (node-state node)) (RETURN node)) (funcall queuing-fn nodes (expand node problem)))))

Game On!