Connection Status:
Competition Arena > SkewSymmetric

SkewSymmetric

SRM 319 · 2006-09-18 · by NeverMore

SRM 319 · 2006-09-18 · by NeverMore · Brute Force, Simple Math
Class Name: SkewSymmetric
Return Type: int
Method Name: minChanges
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A skew symmetric matrix M satisfies MT = -M, where MT denotes the transpose of the matrix M and -M denotes the matrix obtained by multiplying each entry of M by -1. The transpose of a matrix M is obtained by replacing the element in the i'th row and j'th column of M with the element in the j'th row and i'th column of M. Note that this requires the diagonal elements of a skew-symmetric matrix to be equal to 0.

Create a class SkewSymmetric which contains a method minChanges. The method will take a String[] M, each element of which is a single space separated list of integers. The j'th number in the i'th element of M represents the value at row i and column j of the matrix. The method should return the minimum number of values in M that must be changed such that the resulting matrix is skew symmetric.

Constraints

  • M will contain between 2 and 10 elements, inclusive.
  • Each element of M will be a single space separated list of exactly n integers, where n is the number of elements in M.
  • Each element of M will contain between 1 and 50 characters, inclusive.
  • Each integer in M will be between -99 and 99 inclusive, with no extra leading zeros.
  • The integer zero will be represented as '0' (quotes for clarity) only, and not '-0' (quotes for clarity) in M.
Examples
0)
{"1 2 8", "-2 1 0", "3 99 3"}
Returns: 5

One possible skew-symmetric matrix obtained by changing 5 elements in M is: 0 2 -3 -2 0 -99 3 99 0 Note that the diagonal elements must be 0.

1)
{"1 2 8 10", "-2 1 0 3", "3 99 3 2", "0 0 0 1"}
Returns: 9
2)
{"0 1", "-1 0"}
Returns: 0
3)
{"0 1 1 1 1 1", "-1 0 1 1 1 1", "-1 -1 0 1 1 1", 
"-1 -1 -1 0 1 1", "-1 -1 -1 -1 0 1", "0 0 0 0 0 0"}
Returns: 5
4)
{"0 0 0 0", "0 0 0 0", "0 0 0 0", "0 0 0 0"}
Returns: 0

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SkewSymmetric with a public method int minChanges(vector<string> M) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous