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 :
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | qwexd | 130 |
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 :
| Название |
|---|



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