Technical Questions in the second round



Download 466,44 Kb.
Page3/6
Date conversion09.08.2018
Size466,44 Kb.
1   2   3   4   5   6

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)

. -- . -- .

| |

. . -- . -- .



| | | |

. -- . -- . -- . -- .

1   2   3   4   5   6


The database is protected by copyright ©sckool.org 2016
send message

    Main page