E869120's blog

AtCoder Beginner Contest 088
By E869120, history, 6 years ago, In English

Hello Codeforces!

On February 18th, 21:00 JST, AtCoder Beginner Contest 088 will start.

Announcement Page

The problems were prepared by square1001 and me (E869120). Thanks to chokudai and rng_58 to helping us to host the round on AtCoder!

You will be given 100 minutes, and there are 4 problems with the following scores: 100 — 200 — 300 — 400.

This contest is rated for participants whose rating is lower than 1199, but as usual, participants whose rating is more or equal to 1200 can take part out of competition.

Good luck and have fun!

UPD: The contest is over. Let's discuss about the problems.

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

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Reminder: The contest will start in 3 hours.

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by E869120 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Firstly, I want to thank my friend, E869120 and his brother square1001 for organising this wonderful contest.

There were several things I loved about it.

  1. The problems were at the right difficulty level.
  2. Clear problem statements.

Problem C in particular was very fresh and interesting. I've never seen a problem like it before and it probably should win the best 'problem of the contest' award. I thoroughly enjoyed participating and had a great time brainstorming over C and D.

I want to discuss my solution to Problem C, because I did not expect it to get AC. I don't know how to prove it but it passed all test cases. Maybe the problem setters can provide a proof of my approach or come up with a test cases that fails my approach.

I'll write the matrix down. 

(a1 + b1) (a1 + b2) (a1 + b3)

(a2 + b1) (a2 + b2) (a2 + b3)

(a3 + b1) (a3 + b2) (a3 + b3)

What I did was notice that the sum of the diagonals and anti-diagonals is equal = (a1 + b1 + a2 + b2 + a3 + b3)

Now, let R1 be the sum of the first row. R1 = 3a1 + (b1 + b2 + b3)

SimilarlyR2 = 3a1 + (b1 + b2 + b3)

R1 - R2 = 3(a1 - a2)

Clearly if R1 - R3 is not a multiple of 3, there are no possible integers a1 and a2

I applied the same thinking over all pairs of rows and columns.

Now, my program checked three conditions —

  1. Sum of diagonals = sum of anti diagonals
  2. Difference between any pairs of rows is a multiple of 3.
  3. Difference between any pairs of columns is a multiple of 3.

Clearly, if any of these conditions is false, we cannot get 6 integers of the form required in the question.
But, if these three conditions are satisfied can we always get 6 such integers ?

I was able to prove that these conditions were necessary, but not that they were sufficient.

Here's the link to my submission.

Can someone provide a proof to my approach or tell me that it is wrong ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Edit —

    Case — 

    0 0 0 
0 0 3
0 0 0

    My program gives "Yes", but I think the correct output is "No".

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Although your solution is not correct, but there's many other way to solve:
    1. Brute-force approach: Since 0 ≤ ci, j ≤ 100, it's enough seeing 0 ≤ ai ≤ 100. If you brute-force all possible combinations of (a1, a2, a3), then automatically you can decide the values of (b1, b2, b3), or fails to find. The time complexity is O(MAX3).
    2. Better approach than 1., you only have to brute-force the value of a1, and then you can decide the value of b1, b2, b3, a2, a3 in this order. The time complexity is O(MAX).
    3. Better approach than 2., actually you can set the value of a1 to zero, so you can solve it in O(1). It is the solution in editorial.

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

      What is the answer to the test case I provided ? Will you be adding it to the question test cases ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        The answer to the testcase you provided is: "No".
        And we can't add additional testcases to this problem. For every problem, it is inevitable to avoid passing all faux solution, because the number of testcase is sometimes limited. Actually your solution uses "mod three" and it is not expected — and so, if testcase is random in the view of "modulo", and passes your condition 2. and 3. is probability , I think. I think if I provide 200 or 300 testcases it will be solved :), but it is impossible to do that because of the judge system and if we do so in such easy problem the judge queue will stuck.
        But it is a major problem in competitive programming contests. Do you know the meaning of "Accepted (AC)"? The word is not "correct" because it is not always the accepted solutions is correct. I came across many cases about passing faux solutions, and especially E869120, the winner of ABC 075, was accepted D with incorrect solution :)
        But, many problem setters uses random and corner cases, and I added some corner cases even in problem A (100 points problem). And we will be more aware of thinking about some faux solutions. Thank you.

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

          Setting corner cases is important.

          Thank you for your clear explanation of the three approaches. For some reason, the brute forces didn't occur to me at all in the contest ! When you listed the two approaches, I understood the editorial solution :). I wasn't able to understand it till then. You might want to include those two also in the editorial :).

          I liked Problem C a lot. What was the inspiration behind it ? Was it your problem or your brother's ?

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for teaching. I have written a post based your teaching. Here is the GitHub of all my solutions.

      → Reply