salahbadri's blog

By salahbadri, history, 8 months ago, In English

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

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
8 months ago, hide # |
Rev. 2  
Vote: I like it +3 Vote: I do not like it

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.

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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