divya8080's blog

Need help with a proof
By divya8080, history, 16 months ago, In English

I solved this problem(https://www.codechef.com/problems/SORTSUB7EZ) by using the assumption that:- "all the remainders of ai(wrt any integer) belong to set {0, 1, 2, ....,(ai+1)/2-1}" but idk the proof, can anyone help?

PS: i tried a few values of ai and found out that assumption.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
16 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

to get remainder $$$x \ (2 * x \lt a)$$$ you can do always do $$$a_i mod (a_i - x)$$$ as
$$$y = a_i - x$$$
$$$2y = 2a_i - 2x$$$
$$$a_i + (a_i - 2x) \gt a$$$
$$$2y \gt a$$$

→ Reply