##
**Note: For problem M, The editorial is saying that answer is -1 iff n is of form of p^i, Please read it as n is of form of p^i or 2 * p^i.**

**I have lost the tex file, So I am really sorry, Next time I will try to write editorials in a doc kind of format.**

**UPDATE1**: Problems have been added to

**SPOJ**and to our Online judge also. http://www2.cse.iitk.ac.in/judge/public/ . So Enjoy solving them :)

http://www.spoj.com/problems/IITKWPCA/

See the problem from A to J, L to O.

**UPDATE2**: I have corrected the errors in the editorial and uploaded the latest file. If you want some more explantion.I will edit the article, just write a comment about which problem do you think that editorial can be improved and what you do not understand from the editorial.

**latest editorial**from this link:

https://docs.google.com/file/d/0B8cc7eHcqRVNaHNWRjl0T01vX1U/edit?usp=sharing

Please add editorial for F. Also it would be nice if you could link to reference solutions.

ReplyDeletelink to reference solution wont be added, as we have moved problems spoj, so instead of people coding the solutions themselves they would just copy paste the solutions. This is why the editorials were released :)

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

DeleteI misunderstood problem M at first. I would like to know more about the proof. I don't know why the that solution works. Do you have an estimate about when you'll update this analysis? Some pointers to webpages are fine as well.

ReplyDeleteThanks in advance!

hi Miguel Oliveira, I have updated the editorial, I have just in very short explained the proof idea for M. If you can not understand some specific part, then tell me.

ReplyDeleteThank you. Now I understand the general idea of the solution.

ReplyDeleteOne thing I was not getting is that sets A and B have even number of elements. If I understood correctly, if x = (n-x) mod n, gcd(x,n) != 1 (except for x=1,n=2). Maybe you could add that to the analysis.

I never had number theory classes. I don't know how to solve the congruence x^2 = 1 mod n. Could you add a pointer to that?

I posted on SPOJ about problem C. The solution has that time complexity but I'm not sure it's possible to solve all cases within 3s. Maybe we can exchange our solutions and some test cases.

Please see the link,

ReplyDeletehttp://en.wikipedia.org/wiki/Quadratic_residue

http://www.millersville.edu/~bikenaga/number-theory/quadratic-residues/quadratic-residues.pdf

@praveen can you please explain the proof of Co-P{rime again Problem I am unable to understand the proof.

ReplyDeleteThanks.

Lakshman

@praveen can you re-post the end of the editorial about problem C (after : "finding that the point exists in the other set, you binary ") the last lines are not displayed in the pdf file.

ReplyDeleteThanks.