   
. .  . .
 
.  .  .  .
7)
.  .  .  .
 
.  .  . .  .  .
     
. .  .  .  . .
   
. .  .  .  . .
     
.  .  . .  .  .
 
.  .  .  .
8)
.  .  .  .  .  .  .
 
. .  .  .  .  .
   
. .  .  .  .  . .
     
. .  .  .  .  . . .
       
. .  .  .  .  .  .  .  .
       
. .  .  .  .  .  .  .  .
       
.  .  .  .  .  .  .  .
     
. . .  .  .  .
   
. .  .  .  .
 
.  .  .  .
Basic pattern:
.

.  .  .  .  .
 
. .
 
. .
 
.  .  .  .
9)
.  .
 
.  .  .  .
  
.  .  .  .
 
.  .
10) .  .
over and over the same square  
still area = 1 .  .
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
,.
 Problem 4: Superstring 
`'
The Problem
~~~~~~~~~~~
A scientist working the swampy, mosquitoinfested jungles of
Sumatra has made an interesting find. She has recovered fragments of
the gene code of a longextinct animal, the Blarky, each fragment
consisting of a string of molecules. The Blarky's genetic code is much
like ours, with each molecule represented by a letter, except that all
26 letters are used, unlike our code that uses only the four letters,
A, T, C and G to code the molecules in the gene.
Unfortunately, no single sample is guaranteed to be the entire
genetic code of the Blarky, though it is known that every sample
contains a string of consecutive molecules in the actual code. To
reconstruct the final genetic code, our scientist relies on a
wellknown principle in genetics that states that the best
approximation of a genetic code from its fragments is obtained by
finding the shortest sequence of molecules that contains all the known
fragments. For example, if the fragments gyy, segyy and
puse are available, then the best guess at the code is
pusegyy.
Write a program that, given gene fragments, obtains the best
approximation. The input consists of n+1 lines when there are n
gene fragments. The first line has a single integer, which is the
number of fragments. All other lines have a single sequence of
letters, there being no space between letters. The sequence on each
line represents a different gene fragment obtained by the scientist.
The output should be the genetic code as guessed from these fragments.
Each fragment is at most 20 molecules long, and there are at most 100
fragments with the scientist. ... 38 marks
In short
~~~~~~~~
You are given some strings, and you are expected to find the shortest
string that contains all the other given strings, i.e. the shortest
superstring.
My approach
~~~~~~~~~~~
NPhard, and can be mapped to finding the Hamiltonian path. Hence
approximate solutions (within 91% of my exact ones) are given full
credit.
Winner1 algo
~~~~~~~~~~~~
(GREEDY) At any stage, find the pair of strings giving the maximum overlap
on merging in the best possible manner. Merge them, and proceed. At the
end, the string left is the approximate answer.
Winner2 algo
~~~~~~~~~~~~
Sort the strings in descending order of length. Pick the longest and
copy it in the final string. Take the next one.Insert it as follows.
If the final string is "abcdef" and the string to be inserted is
a. "pqr" . Final becomes "abcdefpqr".
2. "def". Final remains the same.
3. "defd". Final becomes "abcdefd"
4. "fabc". Form two strings "fabcdef" and "abcdefabc" and Final
becomes the shorter of two.
Keep on inserting strings in the descending order. Its a NP hard
problem. No polynomial time algo exists for it. Our algorithm works
for fairly large number of cases.
Winner3 algo
~~~~~~~~~~~~
Just removed strings that were already present
Test cases
~~~~~~~~~~
1. all overlaps are zot
: any algo will work
2. aaaaa aaabbb aaabbb bbbccc
: two strings identical
3. aaaaa aaaab aabac baaab aabaab
: general arbit
4. cdefghi abcdef hijklm efghij
: two possibilities exist, which do you choose ?
5. raman mantra uma
: greedy does not work:
greedy takes raman+mantra = ramantra, and then uma: ramantrauma
you should take mantra+raman = mantraman, and then umantraman
6. abcd abef cdab efab
7. hello hell llama lotus shell ellot
: one string is a substring of another
8. finger oafing german muffin codger
9. life feels silli
10. with all the might of the earth rama lifted his bow and in just
one stroke fired twenty types of arrows which made all around him
stop to think about his powers
: to check exhaustive searches
11. who holds the hell torch is none other than the guy who lives here
or there and doth not know fear
12. abcdef defab fababc babc labcd gabcde gfab bcdfab ababef cdlab gbcd bcdg
13. csea prog contest is the worst thing that took place ever
14. sc re w t he gu y w ho do es an ex ha us ti ve se ar ch so th at he
lo ok s fo r be tt er so lu ti on s
15. abab abbc bbcad dacca aabdba abdbabd abadbabdbdbabad adbdbdabadba abdbab
adbbad adbabdad adbadb adbadb adbbdaba dabdbad dbadbadabb dbadab dba
: general arbit
************************************************************************************************
PROBLEM 4:
The Problem
~~~~~~~~~~~
(Freebie) Write a program to print the sentence, Hello
world on the screen. There is one space between the two words, and a
newline after World. The program should then input an integer,
add 10 to it and print the sum on the screen, followed by a newline.
Note: You need to submit this program first to register
yourself. .. 2 marks
In Short
~~~~~~~~
int main()
{
int x;
printf("Hello world\n");
scanf("%d", &x);
printf("%d\n", x+10);
}
Comments
~~~~~~~~
This program tests the editor, compiler, submission script, mail,
printf, scanf, +, and just about everything else. In addition, it
registers the person by creating his program and score directories.
Some smart IITian tried out
int *x; scanf("%d", x); printf("%d\n", *x+10);
which promptly crashed, leaving him wondering why.
Someone else (actually, me) did "Hello World" (caps W) and got
incorrect. My fault, actually. I forgot to lowercase it before
checking.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
,.
 Problem 1: Monontonic 
`'
The Problem
~~~~~~~~~~~
An IITian student, having forgotten to attend his last Physics
lab, has to now cook up a graph for the lab report. He has a
motheaten journal from ten years ago of the same lab, in which the
readings are there, but not in the same order that they were taken
down from the experiments. Each reading has an xvalue which runs
from 1 from to the number of readings, and a yvalue, which may be
any positive integer. However, only the latter is visible for each
reading, in the old report.
The student knows that the final graph is a sine wave. With a couple
of hours left for submission, he decides that the closest he can get
to that is to plot a ``zigzag graph''. He will rearrange the readings
in such a way that when a line is drawn between successive readings on
the graph, a zigzag pattern is obtained, with every point being
at a local maxima or minima of the graph. There may be more than one
reading with the same yvalue, but if they are placed adjacent, the
lab instructor will spot the student's ploy immediately and have him
repeat the experiment. Hence, he wants to avoid an arrangement in
which this happens.
Write a program that given a sequence of readings, determines whether
they suit the student's requirements or not. The input consists of
n+1 lines, with a single integer on each, when there are n
readings. The first number is the number of readings, i.e. n, and
the remaining numbers are the yvalues of the readings, given in no
particular order. The output should be the word ``no'' in lowercase
letters, if the readings can't help the hapless student, or the
required sequence, if they can. In the latter case, the readings, in
the correct order, should be output as a single integer on each line.
Hence, for an nreading problem, for which a ``good'' rearrangement
exists, the answer will consist of n lines. There will be at most
500 readings, with yvalues in [0,10]. ... 15 marks
In Short
~~~~~~~~
We define a monontonic sequence as one which strictly increases and
decreases alternately, starting with either increase or decrease.
Given a sequence of numbers, find a monontonic permutation if you can,
or print "no" if you can't.
My approach
~~~~~~~~~~~
If the number with the maximum number of occurrences occurs more than
N/2 times, then it's not possible to find a sequence. Otherwise
alternately output numbers on either side of this most frequent
number. The problem would become more interesting if we insist that
the final sequence has to have increasing magnitude.
Alternatively, (due to sami), one might use divide and conquer,
knowing that an odd length sequence may *have* to start with an
increase or a decrease, but an even length sequence, on reversing,
starts with the other kind of change. Therefore we can have a merge
sort like algo with the merging step optionally reversing one or both
the evenlength (power of 2) sequences and concatenating.
Winner1 algo
~~~~~~~~~~~~
(GREEDY) Sort the numbers in decreasing order and split the sequence
in half. Now, construct the final sequence by taking alternate
elements from the two halves. There will be 4 possible ways of doing
this. Consider all of them.
Winner2 algo
~~~~~~~~~~~~
Sort the list in increasing order . Let this be b1,b2,....,bn Form two
lists as follows. b1,b4,b2,b5,b3,b6 and b4,b1,b5,b2,b6,b3 for even
n ( here n=6) b1,b5,b2,b6,b3,b7,b4 and b4,b1,b5,b2,b6,b3,b7 for odd n
( here n=7) If in both lists there are consecutive equals then
solution not possible else print that list in which no equal
consecutive are present.
Winner3 algo
~~~~~~~~~~~~
Sort
Even 2n nos if a(n)=a(2n) no
else pick a(n) a(2n) a(n1) a(2n1) .....
Odd 2n+1 nos : if a(n)=a(n+1) no
else pick a(n) a(2n+1) a(n1) a(2n) ....
and place a(n+1) appropriately if it fits
(End beginning or centre)
Test cases
~~~~~~~~~~
yes: 1 2 3
yes: 1 2 2 3
yes: 3 2 2 1
yes: 2 1 3 2
yes: 2 3 1 2
yes: 2 2 1 3
yes: 1 3 2 2
no : 1 2 2 2 3
yes: 3 2 2 2 3
yes: 1 2 2 2 1
yes: 3 3 3 6 6 6
yes: 6 4 6 4 6 4 6
yes: 1 2 2 2 2 2 4 5 6 7
no : 1 2 2 2 2 2 4 5 6
yes: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
yes: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
yes: 3 3 3 3 3 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 4 4 3 3 3
3 3 3 3 3 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 4 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 3 3 4 4 4 4 3 3 3 3 3 3
3 4 4 4 3 3 3 3 3 3 3 3 3 3 4 4 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
,.
 Problem 2: Setsplitting 
`'
The Problem
~~~~~~~~~~~
Bheeshma looked grimly at Krishna and said, ``You must decide, O
Yadava, whom you will give your armies to. They cannot remain neutral
in the great war that will take place.'' ``But I love both the
Pandavas and Kauravas. If I give, I give equally, or I do not give at
all.'', replied Krishna, petulantly. Bhishma beamed. ``That is as
easily done as winning a game of Snakes and Ladders with Shakuni at
your side. Just give Yudhistira half your men, and Duryodhana the
other half.'', he said.
``Not so, Pitamaha! My army is comprised of many akshauhinis and
the men of an akshauhini fight together. So, I have to give an
entire akshauhini to either brother, and not parts of it.
Unfortunately, each akshauhini has a different number of
soldiers, and the math I learnt at my Gurukul is inadequate to help me
figure out how to distribute the akshauhinis. What do I do?'',
wailed Krishna. Bheeshma looked on, nonplussed. This was going to be a
tougher nut to crack than that fisherman chap so many years ago....
Write a program that given the number of soldiers in each of Krishna's
akshauhinis determines whether he will send his soldiers to war
or not. The input consists of n+1 lines, for n akshauhinis,
the first line containing a single integer which is the number of
akshauhinis and every other line containing a single integer which is
the number of soldiers in the corresponding akshauhini. The
output should be the word ``no'' on a line, if there is no equitable
distribution possible. If there is, then output the distribution in
the following manner: for each akshauhini that goes to the
Pandavas, print a +, followed by a space, and the number of soldiers
in that akshauhini. For the Kauravas, substitute the + with a
. Each number (with its appropriate sign) should appear on a line
by itself. There are at most 100 akshauhinis, with 0 to 100
soldiers in each, inclusive. ... 20 marks
In Short
~~~~~~~~
You're given a sequence of numbers, you're supposed to insert +'s and
's in between so that it evaluates to zero. i.e. find a subset of sum
S/2, where S is the sum of all numbers (assumed positive). The numbers
are given to be N in number and bounded by M.
For example
~~~~~~~~~~~
1 2 3 4 : + 1  2  3 + 4 or  1 + 2 + 3  4
1 2 3 10 : no
My approach O(MN^2)
~~~~~~~~~~~~~~~~~~~
Have an array of size M*N which marks all the sums that can be made
out of the N numbers. For example, 0 can be formed by taking no number
in a set. x1 can be formed. x2 and x1+x2 can be formed. i.e. for each
number xi, go through the array sj and mark xi+sj as formable. In the
end, check if the S/2'th element of the array is marked. For finding
the sequence, the entire sequence need not be stored for each array
element, a pointer is sufficient. For example, s[0] = 0, s[x1] = 0,
s[x2] = 0, s[x1+x2] = x1, ... so that by following s[S/2] down to 0,
the set can be obtained.
Winner1 algo
~~~~~~~~~~~~
(BRANCH AND BOUND) Recursively enumerate all the subsets of {1,..,N},
where N=#inputs. Whenever the running sum of a subset exceeds half the
total sum, abandon that path.
Winner2 algo
~~~~~~~~~~~~
We used Brute force. Let the list be a1,a2,..,ai,...,an.
Initially i=1 and av[1]=(a1+a2+.....+an)/2.
Prob: pick some numbers in ai to an such that total is equal to av[i].
step: If we can include ai solve the prob with av[i+1]=av[i]ai
and i=i+1. If we can't include ai solve prob with av[i+1]= av[i]
and i=i+1.
If i>end : Solution not possible for that combination.
If at any stage num[i] is ve : Sol not possible for that combination.
If at any stage num[i]=0 : Sol found.
If solution is not found for a1 then solution not possible.
Winner3 algo
~~~~~~~~~~~~
Greedy:
Sort
Pick the largest as long as feasable
Feasable when fits and required no > least no.
Test Cases
~~~~~~~~~~
yes: 1 2 3 4 5 6 7
no : 6 5 4 1 2 3
yes: 1 2 2 3
no : 2 4 6 10
no : 4 1 16 2 7
yes: 0
no : 2 1 1 1 1 2 2 1 2 2
yes: 1 2 1 1 1 1 2 2 2 1 2 2
yes: 1 1 1 1 1 1
yes: 70 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
yes: 11 19 33 48 7 8
yes: 50 40 10 10 1 1 1 1 1 1 1 1 1 1
yes: 40 27 91 54 67 9 36 40 61 92 30 11 61 0 34 8 32 84 39 73 37 52 71 86 48
35 72 4 31 8 49 47 56 95 48 20 87 72 31 10 30 83 77 5 89 34 68 36 19 10
96 95 43 49 22 95 12 60 11 93 15 72 72 69 73 26 90 96 24 78 1 0 95 0 60
23 88 69 52 34 37 16 45 14 93 41 90 5 52 51 56 69 46 29 28 90 12 5 81
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
,.
 Problem 3: Areas 
`'
The Problem
~~~~~~~~~~~
Star Date 6876.21. The known Universe is under the control of
Earth. To facilitate easy patrolling, all of Earth's dominion has been
mapped onto a twodimensional grid of squares. The grid is described
by equidistant points, with each pair of adjacent points being joined
by lines. Each square in the grid is a colony of Earth, and any
spaceship must travel only along the lines of the grid.
Recently, a renegade band of Klatchians have been making furtive raids
on our colonies. A Klatchian ship materialises at some point on the
grid and drops its crew there. The crew travels from point to point in
some random order, and after some time returns to the point where they
started so that the ship can pick them up again. During this journey,
they may revisit points and travel lines they have already gone
through. All the colonies circumscribed by the travel line of the
Klatchians are laid to waste. Earth Patrol has managed to capture an
abandoned ship used in such a raid that contains only a log mentioning
the details of the crew's trip along the grid lines. Each line of the
log contains a letter, ( n, s, w, e), which gives the direction
of travel (north, south, west, east) and a number that denotes the
number of lines travelled in that direction. For example, the log,
( s 1 w 1 n 1 e 1 ) is a trip that destroys exactly one
square, while ( s 2 w 2 n 2 e 2 ) destroys 4. A longer
sequence, with a diagram describing the travel is attached at the end.
Write a program that given the details of a Klatchian trip finds out
how many colonies have been destroyed. The input is as specified above
in the example, and the output should be an integer with no spaces
before or after it, and succeeded by a newline, that gives the number
of colonies. There are at most 200 lines of input, with the number on
any line not exceeding 200. ... 25 marks
In Short
~~~~~~~~
A particle moves on a grid in an arbitrary manner, but finishing at
the starting point. What's the area of the boundary of the region it
encloses?
My approach
~~~~~~~~~~~
Find a point outside and floodfill, by doing a DFS on the outside
region.
Winner1 algo
~~~~~~~~~~~~
(O(M^3) ALGO) The alien travels along some M lines, say. Extend all
these lines in both directions. This gives rise to some grid of
rectangles. For every rectangle in this grid, find out if it is
bounded on all 4 sides by line segments from the alien's path
(standard test for point inclusion in a convex figure). If yes, add
this rectangle's area to the current area.
Others have not submitted algos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Cases
~~~~~~~~~~
1)
4, e 1, n 1, w 1, s 1 .  .
Area = 1  
.  .
2)
4, n 1, w 1, e 1, s 1 .  .
Area = 0 
.
3)
.  .
 
. .  .
 
.  .  .
4)
.  .  .
 
. .  .
 
. .  .  .
 
.  .  .  .
5)
.  .
 
.  .  .
 
.  .
6)
.  .  .
 
. .  .  .
   
.  .  .  .  .
   
. .  . .
 
.  .  .  .
7)
.  .  .  .
 
.  .  . .  .  .
     
. .  .  .  . .
   
. .  .  .  . .
     
.  .  . .  .  .
 
.  .  .  .
8)
.  .  .  .  .  .  .
 
. .  .  .  .  .
   
. .  .  .  .  . .
     
. .  .  .  .  . . .
       
. .  .  .  .  .  .  .  .
       
. .  .  .  .  .  .  .  .
       
.  .  .  .  .  .  .  .
     
. . .  .  .  .
   
. .  .  .  .
 
.  .  .  .
Basic pattern:
.

.  .  .  .  .
 
. .
 
. .
 
.  .  .  .
9)
.  .
 
.  .  .  .
  
.  .  .  .
 
.  .
10) .  .
over and over the same square  
still area = 1 .  .
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
,.
 Problem 4: Superstring 
`'
The Problem
~~~~~~~~~~~
A scientist working the swampy, mosquitoinfested jungles of
Sumatra has made an interesting find. She has recovered fragments of
the gene code of a longextinct animal, the Blarky, each fragment
consisting of a string of molecules. The Blarky's genetic code is much
like ours, with each molecule represented by a letter, except that all
26 letters are used, unlike our code that uses only the four letters,
A, T, C and G to code the molecules in the gene.
Unfortunately, no single sample is guaranteed to be the entire
genetic code of the Blarky, though it is known that every sample
contains a string of consecutive molecules in the actual code. To
reconstruct the final genetic code, our scientist relies on a
wellknown principle in genetics that states that the best
approximation of a genetic code from its fragments is obtained by
finding the shortest sequence of molecules that contains all the known
fragments. For example, if the fragments gyy, segyy and
puse are available, then the best guess at the code is
pusegyy.
Write a program that, given gene fragments, obtains the best
approximation. The input consists of n+1 lines when there are n
gene fragments. The first line has a single integer, which is the
number of fragments. All other lines have a single sequence of
letters, there being no space between letters. The sequence on each
line represents a different gene fragment obtained by the scientist.
The output should be the genetic code as guessed from these fragments.
Each fragment is at most 20 molecules long, and there are at most 100
fragments with the scientist. ... 38 marks
In short
~~~~~~~~
You are given some strings, and you are expected to find the shortest
string that contains all the other given strings, i.e. the shortest
superstring.
My approach
~~~~~~~~~~~
NPhard, and can be mapped to finding the Hamiltonian path. Hence
approximate solutions (within 91% of my exact ones) are given full
credit.
Winner1 algo
~~~~~~~~~~~~
(GREEDY) At any stage, find the pair of strings giving the maximum overlap
on merging in the best possible manner. Merge them, and proceed. At the
end, the string left is the approximate answer.
Winner2 algo
~~~~~~~~~~~~
Sort the strings in descending order of length. Pick the longest and
copy it in the final string. Take the next one.Insert it as follows.
If the final string is "abcdef" and the string to be inserted is
a. "pqr" . Final becomes "abcdefpqr".
2. "def". Final remains the same.
3. "defd". Final becomes "abcdefd"
4. "fabc". Form two strings "fabcdef" and "abcdefabc" and Final
becomes the shorter of two.
Keep on inserting strings in the descending order. Its a NP hard
problem. No polynomial time algo exists for it. Our algorithm works
for fairly large number of cases.
Winner3 algo
~~~~~~~~~~~~
Just removed strings that were already present
Test cases
~~~~~~~~~~
1. all overlaps are zot
: any algo will work
2. aaaaa aaabbb aaabbb bbbccc
: two strings identical
3. aaaaa aaaab aabac baaab aabaab
: general arbit
4. cdefghi abcdef hijklm efghij
: two possibilities exist, which do you choose ?
5. raman mantra uma
: greedy does not work:
greedy takes raman+mantra = ramantra, and then uma: ramantrauma
you should take mantra+raman = mantraman, and then umantraman
6. abcd abef cdab efab
7. hello hell llama lotus shell ellot
: one string is a substring of another
8. finger oafing german muffin codger
9. life feels silli
10. with all the might of the earth rama lifted his bow and in just
one stroke fired twenty types of arrows which made all around him
stop to think about his powers
: to check exhaustive searches
11. who holds the hell torch is none other than the guy who lives here
or there and doth not know fear
12. abcdef defab fababc babc labcd gabcde gfab bcdfab ababef cdlab gbcd bcdg
13. csea prog contest is the worst thing that took place ever
14. sc re w t he gu y w ho do es an ex ha us ti ve se ar ch so th at he
lo ok s fo r be tt er so lu ti on s
15. abab abbc bbcad dacca aabdba abdbabd abadbabdbdbabad adbdbdabadba abdbab
adbbad adbabdad adbadb adbadb adbbdaba dabdbad dbadbadabb dbadab dba
: general arbit
************************************************************************************************
PROBLEM 5:
1. You are given an array of positive integers. you want to check whether there is a triplet(a,b,c) such that a + b = c

2.Given a number n & a prime p(< n) consider the binomial coefficients C(n,0) , C(n,1) , C(n,2), ... ,C(n,n) one wants to find out how many coefficients are not divisible by p. (try for a log(n) algo.)

3.A chess board (NxN) is given. you want to place knights such that no attack each other & no 2 control the same position.   A      B    a   *           b  in the above grid the 2 knights(position marked A & a) are attacking each other & the 2 knights (position marked B & b ) control the same position( marked Bp addresses baahar bo chummi header iitians mail mankars sendits.sh slocat.sh time xaa xab xac xad xae xaf xag xah xai xaj xak xal xam xan ); you have to give the maximum no. of knights that u can place.

4.Given a string one wants to find out the shortest even palindrome starting from the first index. e.g 1.aabbaa now there are 2 even palindromes(starting from the 1st index) aa & aabbaa. thus the answer is aa. 2.abb although bb is a palindrome but it doesn't start from 1st index thus answer 1.
************************************************************************************************
PROBLEM 6:
Contest ~~~~~~~~~ Brought to you by CSEA, IITB in association with VERITAS software. ==================================================================
You are Dunce E. Dumdum, freshie at IIT Bombay, Powai  400076. Having cracked a cool 3567 rank in IIT JEE after 5 years of concentrated mugging, you think that the future is bright and a gentle smile plays on your lips as you look around at the verdant green campus and the hallowed halls of learning. Little do you know what a dark, gloomy future awaits you. So here's already PROBLEM 1: Credits: 10 ~~~~~~~~~~ Filled with the enthusiasm and excitement of hostel life, you are exploring your new home when suddenly you bump into what appears to be a wall. Closer examination reveals the "wall" to be actually a gigantic, disgruntled and unshaven SENIOR. You politely say "Hi!". SENIOR just grunts in reply. You are about to continue when suddenly SENIOR booms out "Hey FRESHIE!". The plaster is still falling off the ceiling as you turn back with trembling legs. So starts a nice interactive session with SENIOR. Oneway intros over, SENIOR starts asking more technical questions. Your slowly losing that gentle smile on your lips as the questions get livelier. But here comes a question which puts the g.s. back where it belongs: SENIOR says, " I will give you a number (N). Find positive integers `x' and `y' so that x^y + y^x = N, and the sum (x + y) is maximum." So your job is to find such x and y. Input: The integer N in a line by itself. Output: The values of x and y in the format x y on a line by themselves, separated by a blank. Any order of x and y is ok.

PROBLEM 2: Credits: 20 ~~~~~~~~~~ After many such encounters of the SENIOR kind, finally you feel that things are in order and the gentle smile, though mellowed with bitter experience, is still there. But a week's over, and so is your stock of undies, which number 7 (seven). You have realised that now you need to wash them! (Becoz Mommy insists that you wear a clean pair of undies every day.) But now you have had a taste of an IITian's life: too many things to do, too less time. So following Mommy's advice, you decide to plan out things. You know your routine now, so you know exactly what days you will be able to do the washing and what days you won't. You decide 2 things: 1> Since the number of undies is 7 (seven), the washing dates can atmost be separated by 7. Thus, if you wash on the 15th, you have to wash on or before the 22nd. 2> Since basically you are a lethargic bum, you decide that you will wash only if you have atleast 2 dirty undies to wash. Thus the dates must be separated by atleast 3. (So you have to wash on or after 18th, if you wash on the 15th) Since, as mentioned above, you are a lethargic bum, you want to find out the MINIMUM number of days you need to have a fresh undie every day to wear. You also know the number of days you have to spend, and the possible washing days. Input: The total number of days(N) on the first line. The total number of washing days(M) on the second line. The dates of the washing days, M of them, one on each line. NOTE: The dates are numbered from 0 to (N1). Assume that you start out with a fresh set of undies BEFORE 0th day, (i.e the 1th day), so you need to wash on or before 6th, but but not before the 2nd day. Output: The minimum number of days you need to do the washing. Just the number, on a line by itself. Output 1 if it is impossible to schedule washing days subject to the conditions. Sample Input: 10 4 0 3 6 9 Sample Output: 1 (Since you can wash on the 6th This was an error earlier). length of input > strings? could be at max 100000.

PROBLEM 3: Credits: 30 ~~~~~~~~~~ Now you have finally drained the bitter cup: you have realised that life in IITB is not all that rosy, and only by mutual cooperation and worksharing (read cogging) can help you thru the troubled times. Particularly when you are trying to crack math problems. You have a long list of math problems.You and other fellow sufferers decide to handle it together. Each math problem takes you or your friends 1 manhour to crack. But there's a catch: there are some problems that can be done only if some previous problems are done. You decide (as Mommy advices) to prioratize the problems. For problems A and B, for which A appears in the list before B, there are two possibilities: 1> If A has lower or equal priority than B, then 2 students can simultaneously work on problems A and B, to decrease the number of manhours. 2> If A has higher priority than B, then A has to be completed before B. Now since this is a common cause, you have a huge number of freshies who can work on the problems, so there's no constraint on the number of problems being tackled at the same time, as long as the above two conditions are met. As mentioned above, you are a lethargic bum, and so are your friends, so you want to decide what's the MINIMUM number of manhours to solve all the problems. Input: The total number of problems (N) on the first line. The priorities you assigned to the problems in the list, one after the other, on separate lines, as they appear in the list. Thus there are N more lines after the first one, each having a priority value, an integer. Output: The minimum number of manhours needed to solve all the problems in the list. Just the number. Note that a higher priority problem can be done before a lower priority job, even if it comes later in the list. THUS: IF A comes before B in the list and B has higher priority than A, then B can be done before A, or with A simultaneously. BUT if B has lower priority than A, then B HAS to be completed before A. Sample Input: 10 1 1 2 3 1 4 1 2 1 5 Sample Output: 3 (1,1,2,3,4,5) are done first, (1,1,2) are done next, (1) last. Therefore the answer is 3

PROBLEM 4: Credits: 50 ~~~~~~~~~~ Return of the SENIORS. SENIORS strike back. Now your Hostel elections are round the corner. The SENIOR who's standing for G.Sec is unfortunately your wingmate, and so he wants you to go door to door canvassing for him. But lethargic bum that you are, you crib incessantly, and whine and say that Mommy forbids you from such hard work and to concentrate on your studies. So rather than listen to your whines, the SENIOR relents and gives you a list of `N' room numbers you have to visit in order, and tells you that you can visit any `k' of them. You are ecstatic. But again that lethargic bum in you tells you that you would like to minimize your travelling. So you decide to pick a `k' subsequence of room numbers so the the total consecutive absolute differences in room numbers is minimized. Input: N,k  on the first line, the two numbers separated by a comma. Then the room numbers, N of them, one on a line. Output: The minimum total sum of consecutive absolute differences, just the number, on a line by itself. Sample Input: 7,3 67 35 89 37 100 36 4 Sample Output: 3 (By choosing 35,37, 36. Thus 3 = 35  37 + 37  36).

PROBLEM 5: Credits: 40 ~~~~~~~~~~ Your roommate is in the Civil engg. dept. His project consists of setting hanging a heavy plane metal sheet from cables attached to the roof. Bad. Theorem 4.7.18 in the Green book says that to minimize tensile strain( DUH...) you have to have 4 (four) points from which the metal sheet is hung. So that means that these 4 points must be coplanar. WORSE. Your roomie, having got JEE rank 4754, is worse than you. Since your JEE is nearly 1000 more than his, he thinks you are GOD, and turns to you for help. He tells you that there are `N' points in 3D space which represent the ends of the cables. He also tells you that all these points have nonnegative integer coordinates. Since you have a huge ego (rank 3500+ is GREAT, you feel) you have to find 4 coplanar points, given that there ARE 4 coplanar points in the data.The gentle smile replaced by a frown, you set to work. Input: The number of points `N' on the first line. The coordinates of the points, in the format x,y,z  separated by commas, on the next N lines. NOTE: The points are numbered from indices 0 to (N1), as they appear in the list. Output: The indices of 1 set of 4 points, in the format: i j k l where i, j, k, l represent the indices of the points. Sample Input: 5 2,0,0 0,2,0 1,1,1 1,1,0 0,0,2 Output: 0 1 3 4 (the plane is (x + y + z) = 2).

PROBLEM 6: Credits: 50 ~~~~~~~~~~ DANIYA time!!! Work time also for you lethargic bum. The gentle smile on your face is conspicuous by its absence. Finally DANDIYA day comes. Out of the small number of girls in IIT, an even smaller number has arrived. SENIORS being SENIORS, get priority and pairs are formed. You, poor sod, don't have a partner, and have to do the dirty work of arranging publix in circles. The (lucky) boys have already formed the outer circle. The girls have formed the inner one. Your newly elected G.Sec (your wingmate, remember?) puts you to work. The girls being ladies, stay where they are. So you have to rotate the outer circle of boys so as to match them with the girls they have paired up with, or decide if it can't be done. To avoid choas, you would like to have the smallest number of movements.To add to your problems, some guys won't mind dancing with some girls apart from their partners. Input: Two strings of characters of equal length, each on a separate line. You have to find the least index of the character in the second line where the 0th character in the first string should go, so that the two strings match. The characters are numbered from 0 to (length  1). In short: If a(0) a(1) ... a(n1) b(0) b(1) ... b(n1) are the two strings, then find the minimum 'k' so that a(i) = b(k + i (mod n)); for all i = 0, 1, 2,.. (n1); NOTE: Output 1 if such a 'k' does not exist. Output: The index 'k' as specified above, just the number, on a single line. NOTE: Output 1 if such a 'k' does not exist. Sample Input: aabaa abaaa Sample Output: 4 (Since the 0th character of the first string, a, matches with the 4th character of the second string, so that if you take the 0th character to the 4th character the first string matches with the second.) Epilogue: After spending 4 years in IIT Bombay, Powai400076, you permanently lose that gentle smile from your lips forever, but atleast learn the value and importance of hard work, so that you are no longer a lethargic bum.
***********************************************************************************************
SIEMENS INFO :
THIS PAPER CONSISTS 6 PARTS. all are multiple choice q's
1)general
2)c/unix
3)c++/motif
4)database
5)xwindows
6)mswindows
we have written q's not acc. to each part.total 50. q's. time is
sufficient.
if u have basic idea about all of the u can easily answer the paper.
paper

1)which of following operator can't be overloaded.
a)== b)++ c)?! d)<=
2)#include
main()
{
printf("Hello World");
}
the program prints Hello World without changing main() the o/p should
be
intialisation
Hello World
Desruct
the changes should be
a)iostream operator<<(iostream os, char*s)
os<<'intialisation'<<(Hello World)<
b) c) d)none of the above
3)CDPATH shell variable is in(cshell)
a) b) c) d)
4) term stickily bit is related to a)kernel
b)undeletable file
c) d)none
5)semaphore variable is different from ordinary variable by
6)swap(int x,y)
{
int temp;
temp=x;
x=y;
y=temp;
}
main()
{
int x=2;y=3;
swap(x,y);
}
after calling swap ,what are yhe values x&y?
7) static variable will be visible in
a)fn. in which they are defined
b)module " " " "
c)all the program
d)none
8)unix system is
a)multi processing
b)multi processing ,multiuser
c)multi processing ,multiuser,multitasking
d)multiuser,multitasking
9)x.25 protocol encapsulates the follwing layers
a)network
b)datalink
c)physical
d)all of the above
e)none of the above
10)TCP/IP can work on
a)ethernet
b)tokenring
c)a&b
d)none
11)a node has the ip address 138.50.10.7 and 138.50.10.9.But it is
transmitting data from node1 to node2only. The reason may be
a)a node cannot have more than one address
b)class A should have second octet different
c)classB " " " " "
d)a,b,c
12) the OSI layer from bottom to top
13)for an application which exceeds 64k the memory model should be
a)medium
b)huge
c)large
d)none
14)the condition required for dead lock in unix sustem is
15)setuserid is related to (in unix)
16) bourne shell has
a)history record
b)
c)
d)
17)wrong statement about c++
a)code removably
b)encapsulation of data and code
c)program easy maintenance
d)program runs faster
18)struct base {int a,b;
base();
int virtual function1();
}
struct derv1:base{
int b,c,d;
derv1()
int virtual function1();
}
struct derv2 : base
{int a,e;
}
base::base()
{
a=2;b=3;
}
derv1::derv1(){
b=5;
c=10;d=11;}
base::function1()
{return(100);
}
derv1::function1()
{
return(200);
}
main()
base ba;
derv1 d1,d2;
printf("%d %d",d1.a,d1.b)
o/p is
a)a=2;b=3;
b)a=3; b=2;
c)a=5; b=10;
d)none
19) for the above program answer the following q's
main()
base da;
derv1 d1;
derv2 d2;
printf("%d %d %d",da.function1(),d1.function1(),d2.function1());
o/p is
a)100,200,200;
b)200,100,200;
c)200,200,100;
d)none
20)struct {
int x;
int y;
}abc;
you can not access x by the following
1)abc x;
2)abc[0] x;
abc.x;
(abc) x;
a)1,2,3
b)2&3
c)1&2
d)1,3,4
21) automatic variables are destroyed after fn. ends because
a)stored in swap
b)stored in stack and poped out after fn. returns
c)stored in data area
d)stored in disk
22) relation between xapplication and xserver (xwin)
23)UIL(user interface language) (xwin)
24)which is right in mswindows
a)application has single qvalue system has multiple qvalue
b) " multiple " " single "
c)" " " multiple "
d)none
25)widget in xwindows is
26)gadget in x_windows is
27)variable DESTDIR in make program is accessed as
a)$(DESTDIR)
b)${DESTDIR}
c)DESTDIR
d)DESTDIR
28)the keystroke mouse entrie are interpreted in ms windows as
a)interrupt
b)message
c)event
d)none of the above
29)link between program and out side world (ms win)
a)device driver and hardware disk
b)application and device driver
c)application and hardware device
d)none
30)ms windows is
a)multitasking
b) c) d)
31)dynimic scoping is
32) after logout the process still runs in the background by giving
the command
a)nohop
b)
33)process dies out but still waita
a)exit
b)wakeup
c)zombie
d)steep
34)in dynamic memory allocation we use
a)doubly linked list
b)circularly linked
c)B trees
d)L trees
e)none
35)to find the key of search the data structure is
a)hask key
b)trees
c)linked lists
d)records
36)data base


employ_code salary employ_code leave


from to

1236 1500 1238  
1237 2000 1238  
1238 2500 1237 

1237  
1237  
1237  
 
select employ_code,employ_data ,leave
the number of rows in the o/p
a)18
b)6
c)7
d)3
37)DBMS
38)read about SQL,db
39)which is true
a)bridge connects dissimiler LANand protocol insensitive
b)router " " " " "
c)gateway " " " " "
d)none of the above
40)read types of tree traversals.
41)42)43) simple programs on pointers in c
_____________________________________________________________________
BEST OF LUCK
This is sisl paper given in iit kanpur. enjoy this.
All are multiple choice questions.60 questions to be answered in 60 mins.
Distribution of questions:
10 questions from data structures and some general topics.
10 questions from Unix and C.
7Questions from Data base.
Remaining from Windows(x windows,MS Windows etc..)
The distribution is not exact.Only approximate.
Totally there are six sections as below:
1.General
2.Unix and c
3.RDBMS
4.C++/object oriented
TCP/IP
6not remembered.
The questions are as follows:
RDBMS
1.What is RDBMS...Def
2.Two tables are given.In 1st table 2 columns are there.one
isEmployee no,second is salary.In second table 3 columns are there,one is
employee no,second is date,3rd is salary.
Select employee no,from table1,table 2.
How many records it will contain?.(This is somewhat difficult).
3.What is transaction?
TCP/IP:
1.X.25 protocol belongs to which layer.
2,Order all the 7 layers in sequence
3,One node has 2 IP address but data goes through only one link.What is the
reason?
4,Router,Bridge,Gateway....Which one of these can not connect
two different LANS and is protocol sensitive.
5,Client sends serverreqest or demand or Choices
are given.
Another section...
1.main(argc,argv)
{
if(argc<1)
printf("error");
else
exit(0);
}
If this program is compiled without giving any argument ,what it will print.
2.What are the static variables...def
3.What is Dynamic allocation ?
4.Dead lock condition...What may be the condition for it.
5.Semaphore variable?..def
> 6.Most
************************************************************************************************
TISL
part 1
it consists of number series.In some institutes alphabetical series is
given instead of number series.Iam having number series so iam sending
that.Please go through tha alphabetical tests also.
1. 19,24,20,25,21,26,? ans:22
2. 11,14,12,15,13,16,? ans: 14
3. 10,2,8,2,6,2,? a:4
4. 8,9,11,14,,18,23,? a:29
5. 25,25,22,22,19,19,? a:16
6. 14,2,12,4,10,6,? a:8
7. 7,16,9,15,11,14,? a:13
8. 40,42,39,44,38,46,? a:37
9. 3,18,4,24,5,30,? a:6
10. 18,20,22,20,28,20,? a:22
11. 18,20,10,12,4,6? a:0
12. 7,6,8,5,3,7,? a:4
13 9,18,21,25,20,? a:30
14 3,3,4,8,10,36,? a:33
15.30,28,25,20,34,28,? a:21
16. 4,8,16,32,64,128,? a:256
17. 8,16,24,32,40,48,? a:56
18. 13,11,14,12,15,13,? a:16
19. 6,18,36,108,216,648,? a:1296
20. 4,4,8,8,16,16,? a:32
21. 2,6,18,54,162,486,? a:1458
22. 4,20,35,49,62,74,? a:85
23. 10,18,15,23,20,28,? a:25
24. 4,10,8,14,12,18,? a:16
25 10,15,12,17,14,10,? a:16
