## CCC '19 S3 - Arithmetic Square

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Canadian Computing Competition: 2019 Stage 1, Senior #3

You are given a grid which contains integers.

Some of the 9 elements in the grid will have a value already, and the remaining elements will be unspecified.

Your task is to determine values for the unspecified elements such that each row, when read from left-to-right is an arithmetic sequence, and that each column, when read from the top-down, is an arithmetic sequence.

Recall that an arithmetic sequence of length three is a sequence of integers of the form

for integer values of and . Note that may be any integer, including zero or a negative integer.

#### Input Specification

The input will be 3 lines long. Each line will have three space-separated values. Each value will either be an integer in the range from , inclusive, or the symbol X.

For 4 of the 15 marks available, there will be at most 3 X symbols in the input.

For an additional 3 of the 15 marks available, all integer values in the input will be between , inclusive.

For an additional 4 of the 15 marks available, there will be at least 7 X symbols in the input.

For an additional 2 of the 15 marks available, all integer values in the input will be even numbers.

Due to the official test data being weak, an additional subtask worth 1 mark has been added that consists of tests constructed to break solutions that are incorrect but AC on the official test data. Data are provided by d and xiaowuc1.

#### Output Specification

The output will be 3 lines long. Each line will have three space-separated integers. All integers that were given in the input must be in their same position (i.e., same row and same column as in the input). All rows and columns must form arithmetic sequences. All integers in the output must be between , inclusive.

If there is more than one solution, output any solution. There is guaranteed to be at least one solution.

#### Sample Input 1

8 9 10
16 X 20
24 X 30

#### Sample Output 1

8 9 10
16 18 20
24 27 30

#### Explanation of Output for Sample Input 1

Notice that the second element of the second row must be and since , then , and thus, this unspecified element must be . A similar argument applies to the second element of the third row.

#### Sample Input 2

14 X X
X X 18
X 16 X

#### Possible Output for Sample Input 2

14 20 26
18 18 18
22 16 10

#### Explanation of Output for Sample Input 2

This is one of many possible solutions. For example, another solution is:

14 16 18
14 16 18
14 16 18

• commented on June 8, 2020, 8:12 p.m. edited

It's unfortunate that a random solution is easier than the solution proposed in the editorial.

EDIT: and now apparently I have the top submission.

• commented on March 4, 2020, 10:17 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Feb. 8, 2020, 9:53 p.m.

I'm not sure why my code fails the additional test cases, could someone please provide an example where it doesn't work?

• commented on Oct. 4, 2019, 1:17 p.m.

freaking difficult problem bro

• commented on Oct. 4, 2019, 3:11 p.m.

agreed

• commented on June 14, 2019, 10:48 p.m.

this is freaking HARD

• commented on April 15, 2019, 3:13 p.m.

Hey, thanks Troy! ^_^

• commented on April 7, 2019, 10:54 a.m. edit 3

:C

• commented on April 6, 2019, 3:19 p.m.

Great problem. Who's the author though? :thinking:

• commented on April 6, 2019, 8:27 p.m.

it's troy