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.**

Reminder: The contest will start in 3 hours.Auto comment: topic has been updated by E869120 (previous revision, new revision, compare).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.

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.

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)`

Similarly

`R2 = 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 —

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 wealwaysget 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 ?

Edit —

Case —

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

Although your solution is not correct, but there's many other way to solve:

1. Brute-force approach: Since 0 ≤

c_{i, j}≤ 100, it's enough seeing 0 ≤a_{i}≤ 100. If you brute-force all possible combinations of (a_{1},a_{2},a_{3}), then automatically you can decide the values of (b_{1},b_{2},b_{3}), or fails to find. The time complexity isO(MAX^{3}).2. Better approach than 1., you only have to brute-force the value of

a_{1}, and then you can decide the value ofb_{1},b_{2},b_{3},a_{2},a_{3}in this order. The time complexity isO(MAX).3. Better approach than 2., actually you can set the value of

a_{1}to zero, so you can solve it inO(1). It is the solution in editorial.What is the answer to the test case I provided ? Will you be adding it to the question test cases ?

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.

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 ?

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