Connection Status:
Competition Arena > LinAlg

LinAlg

SRM 121 · 2002-11-26 · by mitalub

SRM 121 · 2002-11-26 · by mitalub
Class Name: LinAlg
Return Type: int
Method Name: howMany
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Given an arbitrary number of linear equality equations using an arbitrary (up to 5) number of variables, return the number of distinct possible solutions to the set of equations.

If a set of equations uses the variables (x1, x2, ... xn), a solution is a set of values (r1, r2, ... rn) such that substituting the value ri for the variable xi for all i in all equations results in all the equations evaluating to true equalities.

The number of solutions will always be 0, 1, or infinity. For infinity, return the value 10.

All equations will follow the following grammar:
<EQ> -> <SIDE> "=" <SIDE>
<SIDE> -> integer variable <MORE_VAR_LIST> | integer <MORE_VAR_LIST>
<MORE_VAR_LIST> -> "+" integer variable <MORE_VAR_LIST> | "+" integer <MORE_VAR_LIST> | nil.

Where integer is an integer value, like "23" or "-4" (no space between the negative sign and number) and variable is a single lowercase letter ('a' - 'z'). There can be an arbitrary amount of whitespace between integers, variables, "=" and "+". Leading zeros are allowed in integers, and the integers can range from -10 to 10, inclusive.
For example, an equation might be "03 + 02x = 4y" or "10x + 3y + 2 x = -010".

Notes

  • If a set of equations contains an equation that cannot possibly be satisfied (like "3 + 4 = 2"), there are no solutions.

Constraints

  • equations will contain between 1 and 50, inclusive, elements.
  • Each element of equations will follow the grammar given above.
  • Each element of equations will have maximum length of 50.
  • No integer in equations will be greater than 10 or less than -10.
  • There will be at least 1 variable in equations.
  • There will be at most 5 variables used in equations.
Examples
0)
{"02x+05y+9x+7z=1x",
 "10x=5"}
Returns: 10

The value of x is fixed at .5, but y and z depend on each other so there are infinitely many solutions.

1)
{"2x+4y=3y",
 "2x+-04y=2"}
Returns: 1

This has exactly one solution, x=.2, y=-.4

2)
{"4a+5b+6c+7d+8e=10",
 "10=9a+5b+7d+8e",
 "1=-3a+-2b+-3c+-10d+-5e",
 "2a+5b=7d+10e",
 "9=0a+7b+10c+3d+5e"}
Returns: 1
3)
{"4a+5b+6c+7d+8e=10",
 "10=9a+5b+7d+8e",
 "2=-3a+-2b+-3c+-10d+-5e",
 "2a+5b=7d+9e",
 "9=0a+7b+10c+3d+5e"}
Returns: 1
4)
{"4a+5b+6c+7d+8e=10",
 "10=9a+5b+7d+8e",
 "2=-3a+-2b+-3c+-10d+-5e",
 "2a+5b=7d+10e",
 "9=0a+7b+10c+3d+5e",
 "9=0a+7b+10c+3d+5e"}
Returns: 1
5)
{"1x=2",
 "1x=3"}
Returns: 0

Clearly, there is no solution.

6)
{"1  x+1  y=0"}
Returns: 10

There are infinitely many solutions. For example (0, 0), (-1, 1), etc...

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

Coding Area

Language: C++17 · define a public class LinAlg with a public method int howMany(vector<string> equations) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous