Biểu diễn bằng sai phân

Giả sử nông dân không gian lận. Khi đó dữ liệu lưu lượng sông tuần hoàn với chu kỳ \(2D\).

Đặt \(x_i=d_i-d_{i-1}\) với \(i>1\), và \(x_1=d_1-d_{2D}\). \(x_i\) biểu diễn chênh lệch lưu lượng giữa ngày \(i\) và ngày trước đó trong chu kỳ \(2D\) ngày.

Xét đóng góp của một nông dân vào \(x_i\). Gọi \(T\) là thời điểm đầu tiên người đó đổi giữa chuyển nước và để nước chảy, hoặc ngược lại; gọi \(P\) là số ngày người đó giữ nguyên một trạng thái. Tại các thời điểm \(T,T+P,T+2P,\ldots\), đóng góp của người đó vào \(x_i\) sẽ luân phiên là \(+1\) và \(-1\). Dấu nào xuất hiện trước tùy vào việc đầu chu kỳ \(2D\) ngày người đó đang chuyển nước hay đang để nước chảy. Ví dụ, một nông dân bắt đầu chuyển nước ở thời điểm 3 và đổi trạng thái sau mỗi 8 ngày sẽ đóng góp \(-1\) vào \(x_3\), \(+1\) vào \(x_{11}\), \(-1\) vào \(x_{19}\), \(+1\) vào \(x_{27}\), v.v.

Ta có thể giả sử rằng nếu hai nông dân có cùng \(T\) và \(P\), họ hoặc đều bắt đầu chu kỳ bằng việc chuyển nước, hoặc đều bắt đầu bằng việc để nước chảy. Nếu họ làm hai việc đối nhau thì có thể loại bỏ cả hai nông dân cùng hai phụ lưu tương ứng mà vẫn thu được đúng dữ liệu cũ.

Khôi phục số nông dân

Xét đại lượng

Mỗi nông dân có đúng cặp \((T,P)\) đóng góp \(2D/P\) hoặc \(-2D/P\) vào \(F(T,P)\), tùy trạng thái họ thực hiện trước. Mọi nông dân có \(T\) hoặc \(P\) khác đều đóng góp 0. Vì vậy, số nông dân ứng với \(T,P\) là

và dấu của \(F(T,P)\) cho biết trạng thái ban đầu của họ.

Thử mọi giá trị hợp lệ của \(T\) và \(P\) để tìm số nông dân thuộc từng loại. Sau khi biết thông tin đó, kiểm tra dữ liệu gốc có khớp với mô hình với một số lượng phụ lưu nào đó hay không. Nếu không khớp, in CHEATERS!; nếu khớp, in tổng số nông dân.

Dựa trên phân tích chính thức của Google Code Jam.