Tuesday, January 3, 2012
Friday, December 16, 2011
A grid of size N rows and M columns is filled with numbers, one in
each cell. You start at the centre of the cell at the top-left corner
(1,1) and your destination is the centre of the cell at the bottom-right
corner(N,M). In each step, you are only allowed to move to the centre
of the cell to the right or to the centre of the cell to the bottom.
There are many paths you can take to reach your destination from your
start – however, every path can be uniquely broken down into a series of
straight line-segments joined at right-angles. Each straight
line-segment in your path is termed a ‘leg’ of your path.
Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form?
Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j).
Constraints:
1 <= T <= 10
1 <= N, M <= 100
Numbers in each cell will be between -10000 and 10000 inclusive.
Output Format:
For each testcase output a single line containing the maximum sum you can form.
Sample Input:
3
2 2
-1 -2
5 -1
3 4
-1 2 -3 -4
-2 -3 5 -2
-1 -1 -2 3
2 2
3 1
5 3
Sample Output:
5
10
6
Explanation:
In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs).
In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers).
In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the ’5′ in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because ’5′ is shared by both legs. We can do better by selecting both 3s).
Time limit: 2 seconds
Memory: 64 MB
ACM International Collegiate Programming Contest, 2010, Asia-Amritapuri Site
Solution ( Source : Team Imperials )
Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form?
Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j).
Constraints:
1 <= T <= 10
1 <= N, M <= 100
Numbers in each cell will be between -10000 and 10000 inclusive.
Output Format:
For each testcase output a single line containing the maximum sum you can form.
Sample Input:
3
2 2
-1 -2
5 -1
3 4
-1 2 -3 -4
-2 -3 5 -2
-1 -1 -2 3
2 2
3 1
5 3
Sample Output:
5
10
6
Explanation:
In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs).
In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers).
In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the ’5′ in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because ’5′ is shared by both legs. We can do better by selecting both 3s).
Time limit: 2 seconds
Memory: 64 MB
ACM International Collegiate Programming Contest, 2010, Asia-Amritapuri Site
Solution ( Source : Team Imperials )
01 | /***** Author : Kunal *****/ |
02 | #include <iostream> |
03 | #include <cmath> |
04 | #include <cstdio> |
05 | using namespace std; |
06 |
07 | #define REP(a,b) for(int a=0;a<b;a++) |
08 | #define FOR(a,b,c) for(int a=b;a<c;a++) |
09 | #define FORD(a,b,c) for(int a=b;a>=c;a--) |
10 |
11 | #define S scanf |
12 | #define P printf |
13 |
14 | #define INF 1000000000 |
15 |
16 | int A[102][102]; |
17 | int rmax[102][102][102]; |
18 | int cmax[102][102][102]; |
19 | int n, m; |
20 |
21 | void findRowMax() |
22 | { |
23 | REP(i, n ) REP(j, m ) REP(k, m ) rmax[i][j][k] = -INF; |
24 | REP(i, n ) |
25 | { |
26 | REP(j, m ) |
27 | { |
28 | rmax[i][j][j] = A[i][j]; |
29 | FOR(k, j+1, m ) rmax[i][j][k] = max( rmax[i][j][k-1], A[i][k] ); |
30 | } |
31 | } |
32 | } |
33 |
34 | void findColMax() |
35 | { |
36 | REP(i, m ) REP(j, n ) REP(k, n ) cmax[i][j][k] = -INF; |
37 | REP(i, m ) |
38 | { |
39 | REP(j, n ) |
40 | { |
41 | cmax[i][j][j] = A[j][i]; |
42 | FOR(k, j+1, n ) cmax[i][j][k] = max( cmax[i][j][k-1], A[k][i] ); |
43 | } |
44 | } |
45 | } |
46 | int dp[102][102][2][2]; |
47 | int main() |
48 | { |
49 | int t; S("%d", &t ); |
50 | while( t-- ) |
51 | { |
52 | S("%d%d", &n, &m ); |
53 | REP(i, n ) REP(j, m ) S("%d", &A[i][j] ); |
54 | findRowMax(); findColMax(); |
55 | REP(i, n ) REP(j, m ) REP(k,2) dp[i][j][k][0] = dp[i][j][k][1] = -INF; |
56 | REP(i, m ) |
57 | { |
58 | if( i-1 >= 0 ) dp[0][i][0][0] = rmax[0][0][i-1]; |
59 | dp[0][i][0][1] = A[0][i]; |
60 | } |
61 | REP(i, n ) |
62 | { |
63 | if( i-1 >= 0 ) dp[i][0][1][0] = cmax[0][0][i-1]; |
64 | dp[i][0][1][1] = A[i][0]; |
65 | } |
66 | FOR(i, 1, n ) |
67 | { |
68 | FOR(j, 1, m ) |
69 | { |
70 | REP(k, j ) |
71 | { |
72 | dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][0] + rmax[ i][ k+1][ j-1] ); |
73 | dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][1] ); |
74 | dp[i][j][0][1] = max( dp[i][j][0][1], dp[i][k][1][0] + A[i][j] ); |
75 | } |
76 | REP(k, i ) |
77 | { |
78 | dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][0] + cmax[ j][ k+1][ i-1] ); |
79 | dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][1] ); |
80 | dp[i][j][1][1] = max( dp[i][j][1][1], dp[k][j][0][0] + A[i][j] ); |
81 | } |
82 | } |
83 | } |
84 | int Ans = -INF; |
85 | REP(i, 2 ) REP(j,2) Ans = max( Ans, dp[n-1][m-1][i][j] ); |
86 | P("%d\n", Ans ); |
87 | } |
88 | return 0; |
89 | } |
My three-year old has a set of rings of different sizes, each fitting
on a wooden peg, with all the pegs arranged in a row. He likes to
arrange the rings on the row of pegs in order of increasing size. He
likes to arrange the rings on the row of pegs in order of increasing (or
decreasing) size. He has exactly the same number of pegs and rings,
and has figured out that even if the rings are not in order to begin
with, by repeatedly swapping two adjacent rings, suitably selected, he
can order them.
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
In the digital world geometric shapes are drawn using pixels. A pixel is a square area of unit dimension. For this problem we say 2 pixels are connected if they share an edge or a vertex between them. This is also called 8-connectivity. Your task is to find the maximum possible area of a closed loop made up of A pixels (these are boundary pixels of the closed loop). Area of a closed loop is the number of pixels which are completely inside the loop or on the loop.
Consider the example below: For A = 4, you can make a close loop as follows -
This has an area of 5 with 4 pixels on the loop and 1 pixel completely inside the loop.
Input:
First line contains an integer N, the number of test cases.
Next N lines contain an integer A for that test case.
N <= 100
A <= 1000
Output:
Print N lines with a single integer stating the maximum area of a closed loop.
Sample Input:
2
4
5
Sample Output:
5
6
Given N1, M1, N2 and M2, find the smallest non-negative integer X such that X % M1 = N1 and X % M2 = N2.
Example Inout
4 7 8 13
4 6 8 12
0 5 0 10
Output:
60
-1
0
Wednesday, December 14, 2011
Tuesday, December 13, 2011
Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap.
http://books.google.co.in/books?id=7XUSn0IKQEgC&lpg=PA116&ots=z77FSOIV0j&dq=Given+an+array-based+heap+on+n+elements+and+a+real+number+x,+efficiently+determine+whether+the+kth+smallest+element+in+the+heap+is+greater+than+or+equal+to+x.+Your+algorithm+should+be+O%28k%29+in+the+worst-case,+independent+of+the+size+of+the+heap.&pg=PA116&redir_esc=y#v=onepage&q=Given%20an%20array-based%20heap%20on%20n%20elements%20and%20a%20real%20number%20x%2C%20efficiently%20determine%20whether%20the%20kth%20smallest%20element%20in%20the%20heap%20is%20greater%20than%20or%20equal%20to%20x.%20Your%20algorithm%20should%20be%20O%28k%29%20in%20the%20worst-case%2C%20independent%20of%20the%20size%20of%20the%20heap.&f=false
Subscribe to:
Posts
(
Atom
)
