Sunday, 18 August 2013

Weekend Programming Contest on 17 August 2013 Editorials


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.

You can download the latest editorial from this link:

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

PS: I have updated the editorial, You might face some problems in viewing it in google docs itself. Please download the file and view it.

10 comments:

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

    ReplyDelete
  2. link 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 :)

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. I 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.
    Thanks in advance!

    ReplyDelete
  5. 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.

    ReplyDelete
  6. Thank you. Now I understand the general idea of the solution.
    One 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.

    ReplyDelete
  7. Please see the link,
    http://en.wikipedia.org/wiki/Quadratic_residue
    http://www.millersville.edu/~bikenaga/number-theory/quadratic-residues/quadratic-residues.pdf

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

    Thanks.
    Lakshman

    ReplyDelete
  9. @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.

    Thanks.

    ReplyDelete