Write a program that plays "Cows and bulls". The user thinks of a number less than 10000, with no two digits identical (like 1234. numbers like 0875 are allowed. But 5456 and 3922 are not because it contains 2 indentical digits). The program starts by guessing a number. The user gives the number of hits and misses. A hit is a number in the right place and a miss is a number in the wrong place. e.g If the the number you thought is 4273 the feedback for 2135 is 0 hit 2 miss 0913 is 1 hit 0 miss 4217 is 2 hit 1 miss Your program should use the feedback provided by the user for the next guess and keep guessing after every feedback till it gets the right number. A good program will get the number in about 7 guesses (on an average).
--------------------------------------------------------------------------------
Algo :
5) Cows and bulls. This requires some explaining because nobody got it. But actually its not that difficult. You create an array of all possible numbers. Guess one randomly from that list. Based on the feedback reduce your list eliminating the numbers that can't satisfy the feedback. Guess again from the new list. You will hit the right number in 5 to 7 trys.
--------------------------------------------------------------------------------
6) Knapsack problem.
A Sack is given with a specified volume. And a set of bags are given, each with a specified mass and volume. You have to fill the sack using some of bags such that the total volume of chosen bags is less than or equal to the volume of the sack and their total mass is maximum. Input: Input will be read from a file called "bags.dat". It will contain the number of bags, the volume of the sack, followed by the volume and the mass of the bags. eg. 6 100 10 2 50 10 20 5 40 9 30 5 35 8 Output: Output should be printed on the screen. It will be the number of all the bags to be used. For the given example it will be, 3,4,6
--------------------------------------------------------------------------------
Algo :
6) Knapsack problem. This is a straight forward algorithm. Try all possible combinations that satisfy the given volume constraint and choose the one with the maximum mass.
--------------------------------------------------------------------------------
7) Zigzag An n by m matrix with all its elements between 1 to 4 is given. The left top element(1,1) is 1 and right bottom element(m,n) is 4. You have to find out a continuous zigzag path connecting these two elements, such that, 1)small parts of the zigzag are lines connecting two elements. 2)The numbers in the zigzag path should read 1-2-3-4-1-2-3-4... 3)The zigzag must touch all squares. Assume a solution exists. Example : Given: Solution should be: ;1 3 1 2 ;1 3 1-2 |/ \| | 2 1 4 3 2 1 4 3 / \ / 2 3 4 3 2-3 4 3 / /| 4 1 2 4; 4-1-2 4; Input: input should be read from a file called "matrix.dat". The file contains, row no. column no. elements. eg. 4 4 1 3 1 2........ Output: Output should be printed on the screen. Program should print out the row and column numbers of the elements in the order they are visited. eg. (1,1) (2,1) (1,2) (2,3) .....
--------------------------------------------------------------------------------
Algo :
7) Zigzag. Many people used brute force algorithms. Their code didn't work for a matrix of order 8. One way to do this is to maintain a list of all possible ins and outs for every square. Using the ins of the neigbouring nodes decrease the possible outs for every square. Then use the neighbouring outs to decrease the ins of every square. Do this a few times and you will get very near the solution. Then do a few check and you can get it.
--------------------------------------------------------------------------------
8) Partitioning
You have "n" numbers having values from 1 to n. You have to write a code to partition it into "m" groups such that sum of numbers in each group is equal to n*(n+1)/(2*m). Assume that numbers n and m are such that n*(n+1)/(2*m) is an integer. Your program should print out the numbers in each group. Or if it is not possible to partition the numbers into m groups, then print out that its not possible. Example : n=20 and m=3 Group 1 : 1,8,11,13,18,19 Group 2 : 2,5,12,14,17,20 Group 3 : 3,4,6,7,9,10,15,16 Input: Two integers n,m. Output: Print out to the screen the numbers in each group in a differnt line. Testing: We will run atleast 5 test cases for this problem. So if you cannot write a generalised code which will take care of all n and m, you can try to write codes based on specific conditions.
--------------------------------------------------------------------------------
Algo :
8) Partition. An algo which worked very well, was to start by adding the number n(the largest number) to group 1. Then add the next largest number ( n-1 in this case) , and check whether your sum in that group is greater than n(n+1)/(2m). If it is greater, than take out the number and then add the next greatest number and so on till you get the sum equal to n(n+1)/(2m). For the next group, start out similarly, add the largest of the remaining numbers to the group, and keep adding the next largest, till you get the sum.
--------------------------------------------------------------------------------
*********************************************************************************************
PROBLEM 2:
C-on-test - Intra-IIT Round Brought to you by CSEA, IITB in association with VERITAS software.
--------------------------------------------------------------------------------
Problem 1. ~~~~~~~~~~ With Election fever on its high and politicians running short on time you have write an program which they can use to call junta to come forward and vote... The program should print Come-Sure-Come on a line by itself just once. No leading or trailing spaces. The output is case sensitive i.e. come-sure-come would be regarded as incorrect. As an concerned citizen of this country you should do your bit towards it. Ask yourself, Do you want an elected government or are you apathetic ?
--------------------------------------------------------------------------------
Problem 2. ~~~~~~~~~~ Elections over, mps' elected, the auction house set and the horse-trading is on. All the mp's are seated in a circle. Each belongs to either the H front or the T front of the regional faction of the secular group of the leftist liberal democratic anti-communalist pro-poor progressive party of India. In the center of the circle is THE ONE of the current polity Akal Bechari Bhaggayi (ABB). His aim is to convert all the mp's to either H or T group. But mps' being mps', having had years of experience are not so easy. They always go in pairs (so they can use each other as excuse later). In each step ABB can ask any 2 adjacent mp's to toggle their loyalty. Time however is of the essence. Everyone wants a piece of the action and if ABB doesnot convert fast he will be out of center stage. This is where you come into the picture. You being the brilliant students from IITB can surely use your skills to help him out. Help ABB figure out the minimum number of steps required to achieve his aim. You will be given a string consisting of H's and T's as input on a single line. The size of the input is bounded above by 1600. Consider the input string to be the Circle listed out clockwise from some point. You have to output the number of steps it will take ABB to convert all mp's to one type. The number is to be printed on a line by itself. No leading or trailing data. If it is not possible to do the conversion then output -1. Sample Input: HTTH ~~~~~~~~~~~~~ Sample Output: 1 (for above example. Either pair of T's or H's
*********************************************************************************************
PROBLEM 3:
| Problem 0: Helloworld |
`-----------------------'
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
moth-eaten 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 x-value which runs
from 1 from to the number of readings, and a y-value, 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 y-value, 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 y-values 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 n-reading problem, for which a ``good'' rearrangement
exists, the answer will consist of n lines. There will be at most
500 readings, with y-values 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 even-length (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(n-1) a(2n-1) .....
Odd 2n+1 nos : if a(n)=a(n+1) no
else pick a(n) a(2n+1) a(n-1) 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 two-dimensional 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)
. -- . -- .
| |
. . -- . -- .
| | | |
. -- . -- . -- . -- . |