Scofield11's blog

By Scofield11, history, 5 years ago, In English

There is a square 3x3 consisting of 9 natural numbers. The sum of every row, every column and both diagonals are mutually the same (row 1 has the same sum as row2, row3, column1, column2 etc.).

Some numbers were deleted from the square (deleted numbers are numbered as 0) and the task is to restore those numbers. It is guaranteed that the task is solvable and that there will never be more than 3 deleted numbers. All numbers are less than 20000.

Input:

5 10 3 
4 0 8                   
9 2 7

Output:

5 10 3
4 6 8
9 2 7

Input:

0 11 11
15 9 0
7 7 13

Output:

5 11 11
15 9 3
7 7 13

Input:

496 469 0
0 523 415
442 0 550

Output:

496 469 604
631 523 415
442 577 550

I have some ideas, and I've tried to do the task, but my way wouldn't work on all test cases.

  • Vote: I like it
  • +16
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Note that the worst input occurs when a diagonal is removed.

0 a b

c 0 d

e f 0

In other cases, you can find the sum of some row/column/diagonal and then subtract the sum of the other two to get the removed number. (Which is trivial)

Coming to this input. You need to search for the answer now. Fix one number and see if we can get other two numbers satisfying constraints. Works in linear time. Or use this for the trivial case also.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the test case that I'm talking about.

    If I wanted to check for the sum, I'd have to check every row, column and diagonal which I can definitely do with a bunch of if statements, but this type of solution would fail that test case, and I just don't know to how to do this code cleanly and efficiently.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The solution proposed by iamrk for this test case is to fix one number (e.g. the upper left corner) and try values for it. The numbers are only up to 20000 so you can try all 20000 values. Each time you try a value you can get the sum of the first row and now, knowing the sum, you can deduce the necessary values for the two remaining missing numbers. If they yield a consistent square — you're done, otherwise continue searching.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for your reply. How would this strategy work if I had two or three numbers deleted in a single row ?

        I can't add up one number to a sum if there are two numbers that need filling.

        This is what I have so far: https://pastebin.com/sF1nRyaz

        I've found sum of every row, column and diagonal and I've found the complete sum, now I'm struggling to solve the task while fulfilling all of the corner cases.

        Please understand that I'm a newbie in many ways, and I can technically solve this problem by making a ton of code with bunch of for loops and if statements, but I'm looking for a more efficient solution because if I did tasks like these in such manner, I would lose a lot of time in competitive programming competitions.

        I like your O(1) solution, I'll probably know how to implement it, now I want to know how to the complete task without making such messy code as given above.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          First of all let's think of what happens if the case is NOT a diagonal being empty. We can think of a few cases:

          • Suppose all 3 missing numbers are in the same row. Then there is another row that has the full sum — you can get it there. Then you could find the missing numbers since each column would have exactly 1 missing number.

          • Suppose there are 2 missing numbers in the same row. Then one of the other rows has the full sum. You can then fill the numbers since one row will contain a single missing number and then two columns will afterwards.

          If all 3 missing numbers are in different rows, then we can consider the same thing from column point-of-view, yielding the same logic. If all 3 missing numbers are in different rows AND different columns, then finding the sum must be done through a diagonal, but reconstruction is still easy from rows/columns. And so we see that the only time you don't have an obvious solution is exactly when a diagonal is missing.

          However, as you said, we wouldn't want to get lost in cases so it would be better to solve the problem in a more general way. All we will use from the mentioned observations is that whenever it's not a diagonal that's missing, it's easy to reconstruct the square.

          Here is my (commented) solution:

          There are probably neater ways but you can't get away without some at least some mess.

          Let me know if the problem is on any online judge so I can make sure it passes.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 5   Vote: I like it 0 Vote: I do not like it

            Without you, I'd have 200+ more lines of this code, thank you. This is your solution, I've just did it in my format: https://pastebin.com/V8jqKnWA

            The O(1) solution for empty diagonals: https://pastebin.com/8JuuNpdj

            What IDE do you use ?

            The task guarantees a correct answer so -1 is not needed. The biggest input from the input file is:

            12062 14773 0
            5607 0 16645
            0 7479 10190
            

            It takes about 1.5 seconds to execute on my PC (I'm not sure if it matters but my CPU is i5-4460).

            I don't know any online judges, nor do I have this task on an online judge, and I don't know the time constraints on this task, but I'm pretty sure its above 2 seconds.

            I have a couple of tasks to which I don't have a solution or tutorial to look for, so is it ok that I send them to you and if you find it easy, to explain to me how you solved the problem ? If I can't find a solution on the internet, of course, I struggle with solving these types of problems efficiently (and in time) and since I'm a newbie, I have no idea where to ask for help.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I have a few things to say:

              • First of all, you've reformatted my code but have a small mistake. Line 35 of the linear complexity code has a 0 instead of a 2 when summing a column. This yields wrong answers sometimes, such as the test case you've given as an example.

              • Secondly, 1.5s for this solution is not normal behaviour. Locally for me all these codes run in less than 0.05s. It could be something like an antivirus pausing your solution upon execution or maybe you're just measuring the time in a wrong way. How did you come to 1.5s?

              • Thirdly, I use Codeblocks IDE as I work on Windows where it is quite adequate. If you work on Linux then that's probably a bad idea, as it's quite buggy there. You can google some C++ IDEs and just find which suits you best.

              • Finally, I am very busy so I can't offer any guarantees on helping you with future problems. I think you should just make a blog similar to this one for any future problem you need help with and send me a personal message with the blog linked. In this way, if I don't have time to help, maybe someone else will. Additionally, any help I give you will also be available to other beginners that might be interested in the problem, and of course, if I make any mistake then other users could point it out.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    Not required by the problem, but I'd like to note that you can also directly compute the values in this case, yielding an $$$O(1)$$$ solution.

    X a b
    
    c Y d
    
    e f Z
    

    To have a solution at all, one must have:

    $$$a+b=c+e=Y+Z$$$

    $$$a+f=c+d=b+e=X+Z$$$

    $$$e+f=b+d=X+Y$$$

    You can confirm the equations that don't contain X, Y or Z and if any of them doesn't hold then there is no solution. If they all hold then we can algebraically solve:

    $$$(a+b)+(a+f)+(e+f)=(Y+Z)+(X+Z)+(X+Y)=2(X+Y+Z)$$$

    $$$X+Y+Z=\dfrac{2a+b+e+2f}{2}$$$

    Hence:

    $$$X=(X+Y+Z)-(Y+Z)=\dfrac{2a+b+e+2f}{2}-(a+b)=\dfrac{e+2f-b}{2}$$$

    $$$Y=(X+Y+Z)-(X+Z)=\dfrac{2a+b+e+2f}{2}-(a+f)=\dfrac{b+e}{2}$$$

    $$$Z=(X+Y+Z)-(X+Y)=\dfrac{2a+b+e+2f}{2}-(e+f)=\dfrac{2a+b-e}{2}$$$

    If any of the formulas produces a fraction, there is no solution.