CCC '19 S3 - Arithmetic Square

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 0.6s
Memory limit: 512M
Problem types
Canadian Computing Competition: 2019 Stage 1, Senior #3

You are given a 3 \times 3 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

\displaystyle a, a+d, a+2d

for integer values of a and d. Note that d 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 -1\,000\,000 to 1\,000\,000, 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 -10 and 10, 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.

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 the 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 -1\,000\,000\,000 and 1\,000\,000\,000, 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 Sample Output 1

Notice that the second element of the second row must be 16 + t and since 20 = 16 + 2t, then t = 2, and thus, this unspecified element must be 18. A similar argument applies to the second element of the third row.

Sample Input 2

14 X X
X X 18
X 16 X

Sample Output 2

14 20 26
18 18 18
22 16 10

Explanation of Sample Output 2

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

14 16 18
14 16 18
14 16 18

Comments


  • 3
    wwwddddz  commented on Dec. 13, 2023, 11:25 a.m.

    the worst ccc problem ever


  • -20
    sortSlave  commented on Jan. 14, 2022, 1:31 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    DynamicSquid  commented on Feb. 14, 2021, 7:17 p.m.

    I'm trying out a backtracking algorithm, but I keep getting TLE. Here's my attempt. How can I speed this up? Or do I have to use a different approach?


    • -4
      vishnus  commented on Feb. 15, 2021, 1:24 a.m.

      You can try a random number generator which generates a random number then tries to "fill" the grid, and continuously do each step until it generates a valid grid.


      • 0
        DynamicSquid  commented on Feb. 15, 2021, 4:46 p.m.

        Will that use a backtracking algorithm?


        • -1
          vishnus  commented on March 12, 2021, 2:56 a.m.

          Ehh don't wanna reveal too much, but kinda? Except it doesn't bank off previous random number generations.


  • -1
    zhenga1  commented on Feb. 11, 2021, 8:53 a.m.

    Ok so I submitted a solution that is full marks, but I'm a bit curious, as previous submissions(of the exact same code), I did not get full marks and ended up with TLE. Is it just a thing with solutions that rely on random integer generation?


  • 16
    aaronhe07  commented on June 9, 2020, 12:12 a.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.


  • -7
    echofox  commented on March 5, 2020, 3:17 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 23
    helloword  commented on Oct. 4, 2019, 5:17 p.m.

    freaking difficult problem bro


    • 0
      zhenga1  commented on Feb. 11, 2021, 8:57 a.m.

      Yes very difficult, and also you apparently can get varied scores if your solution is based on random numbers lmao. I submitted a solution(the same code) that got 13/16, 14/16, 15/16, and 16/16 each once(TLE was the error).


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

      agreed


  • 18
    ChrisLi  commented on June 15, 2019, 2:48 a.m.

    this is freaking HARD


    • -2
      Jinx  commented on Dec. 19, 2021, 3:25 p.m.

      it's easy to wrap your head around, but hard to put it in the IDE


    • 0
      Ch4rIes  commented on Nov. 8, 2020, 7:43 a.m.

      I think the question itself is not extremely hard, but I dont think it is easy to solve in just 1 hour.


  • 41
    whomax  commented on April 15, 2019, 7:13 p.m.

    Hey, thanks Troy! ^_^


  • 21
    Plasmatic  commented on April 7, 2019, 2:54 p.m. ← edit 3

    :C


    • -7
      ochen1  commented on Feb. 15, 2021, 6:17 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 14
    666245  commented on April 6, 2019, 7:19 p.m.

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


    • 14
      p1geon  commented on April 7, 2019, 12:27 a.m.

      it's troy