TopCoder problem "OddsAndEvens" used in SRM 194 (Division I Level Two)



Problem Statement

    

Any integer is either odd or even. An even number is a number which divides by 2 without leaving any remainder. All other numbers are odd. We can create an arithmetic that deals with addition and multiplication of odd and even numbers. For example, the sum of two even numbers will also be an even number, but the sum of an odd and an even number must be an odd number. Here is the list of all possible sums and products in this arithmetic:

EVEN + EVEN = EVEN
EVEN + ODD = ODD
ODD + ODD = EVEN

EVEN * EVEN = EVEN
EVEN * ODD = EVEN
ODD * ODD = ODD

A list of integers is chosen. For each unique pair of numbers in the list we record their sum and product. Given the final contents of String[] sums and String[] products, where each element is either "ODD" or "EVEN", return the number of odd and even numbers in the original list. The corresponding elements in sums and products are NOT necessarily calculated from the same pair of numbers. Your return must be formatted as "EVEN <x> ODD <y>" where <x> is the number of evens and <y> is the number of odds. If the original list cannot be constructed then return "IMPOSSIBLE".

 

Definition

    
Class:OddsAndEvens
Method:find
Parameters:String[], String[]
Returns:String
Method signature:String find(String[] sums, String[] products)
(be sure your method is public)
    
 

Constraints

-sums will contain N(N-1)/2 elements where N is an integer between 2 and 10 inclusive.
-products will contain the same number of elements as sums.
-each element in sums will be either "ODD" or "EVEN".
-each element in products will be either "ODD" or "EVEN".
 

Examples

0)
    
{"EVEN"}
{"ODD"}
Returns: "EVEN 0 ODD 2"
The only sum is even. Thus the two numbers are either both even or both odd. If the two numbers are both even then their product will also be even. This contradicts what we have in products. If the two numbers are both odd then their product will also be odd. This agrees with products. Thus there are two odd numbers.
1)
    
{"ODD"}
{"ODD"}
Returns: "IMPOSSIBLE"
If the sum is odd then one number is odd and the other is even. The product of an odd and even number is even. This contradicts products. Thus this is IMPOSSIBLE.
2)
    
{"EVEN","EVEN","EVEN"}
{"EVEN","EVEN","EVEN"}
Returns: "EVEN 3 ODD 0"
The sum and product of any two even numbers are always even. Here there are 3 even numbers.
3)
    
{"EVEN","ODD","ODD"}
{"ODD","EVEN","EVEN"}
Returns: "EVEN 1 ODD 2"
Two numbers are odd and one number is even. The two odd numbers give us one even sum and one odd product. The even number combined with the other two odd numbers gives two odd sums and two even products.
4)
    
{"ODD","EVEN","ODD","EVEN","ODD","EVEN"}
{"ODD","EVEN","EVEN","EVEN","ODD","ODD"}
Returns: "EVEN 1 ODD 3"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2394

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5069&pm=2394

Writer:

dimkadimon

Testers:

lbackstrom , brett1479

Problem categories:

Math