I've stumbled on something in Problem A that feels right intuitively, but I don’t have a proof of its validity yet …
If someone can help to explain :
https://mirror.codeforces.com/contest/2144/submission/338745804
I've stumbled on something in Problem A that feels right intuitively, but I don’t have a proof of its validity yet …
If someone can help to explain :
https://mirror.codeforces.com/contest/2144/submission/338745804
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
| Name |
|---|



If s1%3=s2%3=s3%3=x, then (s1+s2+s3)%3=(3*x)%3=0.
If they are all different, then {s1,s2,s3}%3={1,2,3}, then (s1+s2+s3)%3=0
This means that if you can cut the array as the problem requieres, then the sum of s1+s2+s3 is 0 mod3, an easy check you can see that if two of s1,s2,s3 are the same mod3 while the other is not, then s1+s2+s3 is never 0 mod3.
This means that you can cut the array if and only if (s1+s2+s3)%3=0, which is the sum of all aimod3. Now, your solution says that if you can cut the array, then the solution is 1,n-1. This means that you take 1 element for prefix and suffix, and the rest for the middle. Clearly, if a1=an-1=x mod 3, then the sum of the middle is also x mod3 as the total sum is 0 mod 3, also if a1!=an-1 mod 3, it leads to the same conclusion.
I think I didn't get silly in my proof, and I think it leads to this conclusion: If you are able to cut the array, i.e the sum of all ai mod3=0, then you can cut in any way