search

wewark / Codeforces-Gyms-Solutions

My solutions for some Codeforces' Gyms
37 stars 15 forks source link

Ambiguity in solution #4

Closed anishagg17 closed 4 years ago

anishagg17 commented 4 years ago

https://github.com/wewark/Codeforces-Gyms-Solutions/blob/master/Solutions/101608%20-%202017%20ACM%20Jordanian%20Collegiate%20Programming%20Contest/M.cpp

I am unable to understand some logic can you please explain?

wewark commented 4 years ago

Draw a little grid and write for each cell whether it is a losing or a winning cell, starting from the top-left cell which is losing.

You'll find that losing cells form diagonals starting from the main diagonal which has n cells, and going towards the top-right and bottom-left corners. Where each diagonal is less than the previous one by (k + 1) cells as there are k winning diagonals between each losing diagonal. And therefore there are n / (k + 1) diagonals on each side of the main diagonal.

So this is the equation for counting the total number of cells in all those diagonals. image

Simplify the equation and it will match the one written in the code. Notice the k++ in the beginning, in order to use k instead of k + 1.

anishagg17 commented 4 years ago

Thank you very much