Sort 461 Discussions, By:
Please Login in order to post a comment
Mine works perfectly, simple solution
int n = in.nextInt();
int a = new int[n];
int b = new int[n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
int x = in.nextInt();
a[i] += x;
b[j] += x;
String pts = "Possible";
if(a[i] == b[j])
int temp = b[j];
b[j] = b[i];
b[i] = temp;
pts = "Impossible";
1. Swaps that happen between any 2 buckets are always of equal value (you can exchange 1 for 1 but not 2 for 1, ratio should always be 1:1), therefore the number of balls in each bucket will always remain the same.
2. We need to make sure that the total number of balls in each container should equal the number of balls of any type 't' for a fair trade(1:1 ratio). This is done to check whether there are any type 't' balls that satisfy the requirements of the solution (i.e. we want all balls of a single type 't' in only one container).
3. Calculate the number of balls in each container(sum of rows) and store it in a list.
4. Calculate the number of balls of each type(sum of columns) and store it in a list.
5. Sort the two lists and compare them. If they are equal then a solution exists otherwise, no solution exists.
Try theses cases to see and understand the pattern:
0 4 0
2 0 1
1 0 2
1 2 3 4
2 1 4 3
3 4 2 1
4 3 1 2
0 0 5 0
4 0 0 0
0 2 0 1
0 1 0 2
1 2 3
3 2 1
2 3 1
1 0 0
0 2 0
0 2 0
1 2 1 3
2 1 3 1
1 3 2 1
3 2 1 1
Note: For more test cases try Solved Sudoku puzzles.
Here is Python2 Solution:
q = int(raw_input().strip())
for x in xrange(q):
n = int(raw_input().strip())
m = 
rowsum = *n
colsum = *n
for i in xrange(n):
rowsum[i] = sum(m[-1])
colsum = map(lambda a, b: a+b, colsum, m[-1])
if rowsum == colsum:
My Python 3 solution:
r = sorted([sum(x) for x in container])
c = sorted([sum(x) for x in zip(*container)])
return "Possible" if r == c else "Impossible"
This is fairly simple when you think it through. You don't actually go through each swap, as it only requires whether it's possible or not. The working logic is below:
1.The balls in the containers are not moved around, but just swapped. This means, the number of balls in each container will always remain the same.
2.Also, each container must only have balls with the same number, the numbers of balls of each type must match the number of balls in containers. For example, if there are 3 containers containing 3, 6, 9 balls, then there must be 3 balls of one type, 6 balls of another type and 9 balls of the other type.
3.As a result, when you work out the numbers of balls in each container and the numbers of balls of each type, these two numbers must match to be "Possible". Otherwise, it is "Impossible"
My working python 3 solution is below:
# The balls can only be swapped, meaning the number of balls in each container will remain unchanged.
# Therefore, the numbers of balls in containers must be aligend with the numbers of balls of each type
# e.g. if there are 3 containers with 3, 6, 9 balls, then
# types of balls must be 3, 6, 9 (does not have to be ordered)
q = int(input().strip())
for a0 in range(q):
n = int(input().strip())
M = 
for M_i in range(n):
M_t = [int(M_temp) for M_temp in input().strip().split(' ')]
rowSums = 
colSums = 
# Get sums of each row (number of balls in each container)
for i in range(n):
# Get sums of each column (number of balls of each type)
for i in range(n):
colSum = 0
for j in range(n):
colSum += M[j][i]
# if sorted sums are the same, print Possible
# otherwise, print Impossible
if sorted(rowSums) == sorted(colSums):
i think the website has made a mistake in giving answers to the test cases.
my logic is:
count the total no. of balls of type i.
count the total no. of balls in container i.
if these two values are equal for each i then it is possible otherwise impossible.
shown below is an input of test case 1:
997612619 934920795 998879231 999926463
960369681 997828120 999792735 979622676
999013654 998634077 997988323 958769423
997409523 999301350 940952923 993020546
they have given the answer as possible which is clearly not the case