August Algorithm Challenge Ranks / Test Cases / Stats

1 min read

Greetings,
We are very happy to announce the winners of our August Algorithm Challenge 🙂

Winners :

Top 5 (India):
1st – Varun Jalan (6.000)
2nd -Anshuman Singh (5.980)
3rd – Anil (5.979)
4th – Sumeet (5.964)
5th – Pradeep B (5.936)

Top 5 (US):
1st – Balakrishnan Varadarajan (5.991)
2nd – Kevin Chen (5.981)
3rd – Tomasz Czajka (5.976)
4th – Josh Metzler (5.965)
5th – Neal (5.940)

Statistics:

All problems are now available in the practice area. The test cases for the problems can be found here
Here are some additional statistics about the contest:

Length of Contest Unique Visitors Unique Participants Total Number of Submissions Percentage of user who have solved at least one problem
10 days 15,824 235 4867 35%
Country Total Participants Average Score per User
IN 164 0.751
US 41 1.866
Rest of World 30 2.494

Feedback:

This time we tried something different with respect to the challenge problem. A user could submit at most 20 times in a span of 24 hours. We would like your feedback regarding this.

  • Was a limit of 20 submissions a day enough or would you like more number of submissions?
  • Alternatively, should we revert back to the re-judging method that was followed for the July Contest?

We also need your feedback about the contest as a whole.

  • How would you rate the contest problems?
  • Were they easier/similar/difficult compared to the previous contests?

Also, if you have any kind of feedback related to the contest or otherwise, feel free to comment.

Mini Challenge:

Lastly, as you all know, we will be having a shorter contest later this month. The August Mini Challenge will be held from 22nd August 15:00 IST to 24th August 15:00 IST. This will consist of a single challenge problem with no limits on the number of submissions. Hope to see you all there.

Regards,
Aniruddha.

Special Problems For Coders With No DSA Knowledge? Smells…

Let us start off with a couple of disclaimers – if your rating is above 1600, this will have literally no change for you....
debanjan321
1 min read

Round-Up Of The 2021 Cook-Offs

We’re done with all of 2021’s Cook-Offs, and we’re taking a look back to see what the competitions brought. Instead of the usual 12,...
riddhi_225
2 min read

2021 December LunchTime | Ending The Year In Style!

We’re done with the December LunchTime, which means that all of 2021’s rated-for-all competitions are over. While there’s plenty to reminisce about for the...
riddhi_225
2 min read

113 Replies to “August Algorithm Challenge Ranks / Test Cases / Stats”

  1. Hi

    I thought this contest was pretty good with application of some neat ideas to solve the problems. I really liked Bytelandian Robots (F2), which after solving seems a lot easier than it did when I first read it.

    One request, is it possible to make the scores in the practice area same as those in the contest for the FX type problem? This way, if we try to submit now, we’d know how good/terrible our practice solutions are when compared to whatever was submitted during the contest.

    Loved this contest! Keep it coming.

  2. Hi

    I thought this contest was pretty good with application of some neat ideas to solve the problems. I really liked Bytelandian Robots (F2), which after solving seems a lot easier than it did when I first read it.

    One request, is it possible to make the scores in the practice area same as those in the contest for the FX type problem? This way, if we try to submit now, we’d know how good/terrible our practice solutions are when compared to whatever was submitted during the contest.

    Loved this contest! Keep it coming.

  3. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  4. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  5. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  6. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  7. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  8. The problems were better this time and could be solved without using a search engine.
    I was expecting the August mini-challenge to be more like ICPC / IOI style with many problems. However doesn’t seem to be. One challenge problem means that a lot of tweaking and needs one to spend the entire day over the same problem (which is kind of boring).
    I hope you make some changes and make it like IOI / ICPC.
    IOI/TC style will make it interesting, so that you only know how correct your solutions were after the contest.

  9. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  10. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  11. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  12. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  13. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  14. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  15. @Vaibhav this is a good point, we will look into adding the top scoring solution for the challenge problem when moving to the practice arena

    @Pratik we are planning a team based ACM-ICPC style competition in a few weeks

    Thanks for your feedback!

  16. Also if possible, kindly have something on the submission page/status page which indicates the number of submission remaining for me in the day. Ofcourse, we can count our submission for the day, but it would be more convinient feature to have.
    And yes, the contest again was great. Thanks for a great contest. Looking forward to the mini contest :).

  17. Also if possible, kindly have something on the submission page/status page which indicates the number of submission remaining for me in the day. Ofcourse, we can count our submission for the day, but it would be more convinient feature to have.
    And yes, the contest again was great. Thanks for a great contest. Looking forward to the mini contest :).

  18. Also if possible, kindly have something on the submission page/status page which indicates the number of submission remaining for me in the day. Ofcourse, we can count our submission for the day, but it would be more convinient feature to have.
    And yes, the contest again was great. Thanks for a great contest. Looking forward to the mini contest :).

  19. Also if possible, kindly have something on the submission page/status page which indicates the number of submission remaining for me in the day. Ofcourse, we can count our submission for the day, but it would be more convinient feature to have.
    And yes, the contest again was great. Thanks for a great contest. Looking forward to the mini contest :).

  20. Hey i liked the august contest…(it was my first tryst wide codechef and although none of my solutions were accepted due to time out…) but i liked this out of box programming and thinking… Long Live CodeChef… and i will definitely do better next time round… a challenge to myself!!!!

    And to anirruddha, plz let us know about this team based contest as early as possible… i m eager to break my jinx at it!!!

  21. Hey i liked the august contest…(it was my first tryst wide codechef and although none of my solutions were accepted due to time out…) but i liked this out of box programming and thinking… Long Live CodeChef… and i will definitely do better next time round… a challenge to myself!!!!

    And to anirruddha, plz let us know about this team based contest as early as possible… i m eager to break my jinx at it!!!

  22. Thanks for the interesting problems!

    I was wondering if it would be possible for you to share the judge program for the Aug 09 Divide-and-conquer problem (F6). I had been struggling for several days during the contest to figure out the trouble with my program (http://www.codechef.com/AUG09/viewsolution/66562/), and could find none. I also wrote my own proof-checker, and that could find no problems either. Even with the test data in the aug09.zip file, I can’t seem to spot the trouble.

    If you could share the judge program for F6, I might have a chance to finally spot the trouble with the proof my program is generating.

    Thanks again!

  23. Thanks for the interesting problems!

    I was wondering if it would be possible for you to share the judge program for the Aug 09 Divide-and-conquer problem (F6). I had been struggling for several days during the contest to figure out the trouble with my program (http://www.codechef.com/AUG09/viewsolution/66562/), and could find none. I also wrote my own proof-checker, and that could find no problems either. Even with the test data in the aug09.zip file, I can’t seem to spot the trouble.

    If you could share the judge program for F6, I might have a chance to finally spot the trouble with the proof my program is generating.

    Thanks again!

  24. I think this was a wonderful contest. I loved the problems (especially the divide and conquer one).
    I think the difficulty level of the contest was perfect. I hope I will have time to participate in the future contests as well.
    I have learned about so many algorithms in the last 3 months.. Great job!

  25. I think this was a wonderful contest. I loved the problems (especially the divide and conquer one).
    I think the difficulty level of the contest was perfect. I hope I will have time to participate in the future contests as well.
    I have learned about so many algorithms in the last 3 months.. Great job!

  26. I thought the difficulty of the problems was fine. I also enjoyed the challenge problem, though I had very little time to work on it this month. I always write a local tester for the challenge problems (a habit formed from TopCoder marathon matches), so the submission limit should not be a problem for me. I guess a count of submissions for the current day might be nice, as the timezone difference might confuse me sometime.

    I used this as an opportunity to learn C#, but was disappointed by its speed. I was going to submit everything in C#, but I had to rewrite Golf Course in C++, as even a dummy solution that read input and wrote the requisite number of integers to output timed out in C#. I also had to switch back to cpp for Crystals for speed reasons.

  27. I thought the difficulty of the problems was fine. I also enjoyed the challenge problem, though I had very little time to work on it this month. I always write a local tester for the challenge problems (a habit formed from TopCoder marathon matches), so the submission limit should not be a problem for me. I guess a count of submissions for the current day might be nice, as the timezone difference might confuse me sometime.

    I used this as an opportunity to learn C#, but was disappointed by its speed. I was going to submit everything in C#, but I had to rewrite Golf Course in C++, as even a dummy solution that read input and wrote the requisite number of integers to output timed out in C#. I also had to switch back to cpp for Crystals for speed reasons.

  28. I thought the difficulty of the problems was fine. I also enjoyed the challenge problem, though I had very little time to work on it this month. I always write a local tester for the challenge problems (a habit formed from TopCoder marathon matches), so the submission limit should not be a problem for me. I guess a count of submissions for the current day might be nice, as the timezone difference might confuse me sometime.

    I used this as an opportunity to learn C#, but was disappointed by its speed. I was going to submit everything in C#, but I had to rewrite Golf Course in C++, as even a dummy solution that read input and wrote the requisite number of integers to output timed out in C#. I also had to switch back to cpp for Crystals for speed reasons.

  29. @Aniruddha: Thanks for the idea of seeing submitted solutions; I actually did that, and compared their results to mine, and things seem to match up okay.

    Now since there isn’t one true answer for the proof part of F6, I still can’t see why my program generated proof is wrong (I do output the correct max-number-of-pieces).

    Knowing which constraint of the F6-judge my proof is violating will help me see my mistake.

  30. @Aniruddha: Thanks for the idea of seeing submitted solutions; I actually did that, and compared their results to mine, and things seem to match up okay.

    Now since there isn’t one true answer for the proof part of F6, I still can’t see why my program generated proof is wrong (I do output the correct max-number-of-pieces).

    Knowing which constraint of the F6-judge my proof is violating will help me see my mistake.

  31. The problems were indeed nice. Unfortunately didnt have much time (relative to my speed 😉 ) this time round. Wonder if you could also introduce a section like “My Approaches” for every problem in the contest just the way you have the “Comments” section or something like the “Editorials” (wiki-based) of TC (rather than requiring someone to start a forum post everytime to ask for one). These sections would surely serve as a good starting point for brief tutorials for many different algorithms.

  32. The problems were indeed nice. Unfortunately didnt have much time (relative to my speed 😉 ) this time round. Wonder if you could also introduce a section like “My Approaches” for every problem in the contest just the way you have the “Comments” section or something like the “Editorials” (wiki-based) of TC (rather than requiring someone to start a forum post everytime to ask for one). These sections would surely serve as a good starting point for brief tutorials for many different algorithms.

  33. The problems were indeed nice. Unfortunately didnt have much time (relative to my speed 😉 ) this time round. Wonder if you could also introduce a section like “My Approaches” for every problem in the contest just the way you have the “Comments” section or something like the “Editorials” (wiki-based) of TC (rather than requiring someone to start a forum post everytime to ask for one). These sections would surely serve as a good starting point for brief tutorials for many different algorithms.

  34. @Ashutosh,
    The number of cuts that you output seems correct.
    However when I input 1.6(for instance) to your code it outputs
    1.6
    6
    0 0.5
    0 0.25
    1 0.25
    0 0.125
    2 0.125

    But the first cut appears incorrect(since the ratio between the largest to the smallest is 1).
    Maybe you did a silly mistake in outputting the cutsizes.

  35. @Ashutosh,
    The number of cuts that you output seems correct.
    However when I input 1.6(for instance) to your code it outputs
    1.6
    6
    0 0.5
    0 0.25
    1 0.25
    0 0.125
    2 0.125

    But the first cut appears incorrect(since the ratio between the largest to the smallest is 1).
    Maybe you did a silly mistake in outputting the cutsizes.

  36. @Ashutosh We have been trying to find the bug for the past 3 hours. The bug is indeed very subtle. Your program produces the correct answer on our local machine, but the output it produces on the judge is something completely different. We still haven’t been able to find out what is causing this error, but it is happening only with your submissions. We checked the other submissions, but they don’t have such an issue.

  37. That is what we feel too, but haven’t been able to go through his submission to check that out.

    @Ashutosh Please re-check your solution to see if something of this sort can happen in your code.

  38. @Balakrishnan, thanks for trying out my program. However, the output of my program (Submission http://www.codechef.com/AUG09/viewsolution/66562/) for k=1.6 is:
    6
    0 0.415584391972
    0 0.259740261216
    1 0.207792195986
    0 0.162337673406
    2 0.129870130608

    (this answer is indeed correct, I’ve checked by hand.)

    @Aniruddha, thanks for taking a look into this; I truly appreciate. It is surprising to me, too, that my program would generate largely varying output on different machines.

  39. @Balakrishnan, thanks for trying out my program. However, the output of my program (Submission http://www.codechef.com/AUG09/viewsolution/66562/) for k=1.6 is:
    6
    0 0.415584391972
    0 0.259740261216
    1 0.207792195986
    0 0.162337673406
    2 0.129870130608

    (this answer is indeed correct, I’ve checked by hand.)

    @Aniruddha, thanks for taking a look into this; I truly appreciate. It is surprising to me, too, that my program would generate largely varying output on different machines.

  40. That is the output we get on our local machine too. But on the judge, we get the output that Balakrishnan pasted. We have no idea why something of this sort could be happening. We are still looking into this.

  41. That is the output we get on our local machine too. But on the judge, we get the output that Balakrishnan pasted. We have no idea why something of this sort could be happening. We are still looking into this.

  42. That is the output we get on our local machine too. But on the judge, we get the output that Balakrishnan pasted. We have no idea why something of this sort could be happening. We are still looking into this.

  43. @Balakrishnan, you are correct in that this is related to the call_unary function; but I don’t think the bug is in my code.

    I just nailed the sucker down to what I believe to be a GCC bug. Try the code with gcc 4.0.1 (which is what I think you and the server are both using):

    template void c1(ProcObj &f) { f(); }
    template void c2(const ProcObj &f) { f(); }

    void B(void) { printf(“B invoked”); }

    int main(void) {
    printf(“Case 1: “); c1(B); printf(“n”);
    printf(“Case 2: “); c2(B); printf(“n”);
    return 0;
    }

    The second instance of B is never invoked (via the c2 that takes in a const arg). Somehow, it is being eliminated away! This is exactly the problem with my code: The call to f(n) in call_unary() is being eliminated!

    Once I “specialized” (over-loaded, really) the template call_unary for the function pointer, I get the right answer with gcc 4.0.1 (I can’t submit to Codechef and check, but I bet I’ll get the right answer on the server now).

    Just add the lines:

    void call_unary(Node *n, void (*f)(Node *)) {
    if(n) f(n), call_unary(n->left, f), call_unary(n->right, f);
    }

    after the decl of call_unary, and I think you should also be able to get the right answer.

    To me, this strongly looks like a GCC bug.

  44. @Balakrishnan, you are correct in that this is related to the call_unary function; but I don’t think the bug is in my code.

    I just nailed the sucker down to what I believe to be a GCC bug. Try the code with gcc 4.0.1 (which is what I think you and the server are both using):

    template void c1(ProcObj &f) { f(); }
    template void c2(const ProcObj &f) { f(); }

    void B(void) { printf(“B invoked”); }

    int main(void) {
    printf(“Case 1: “); c1(B); printf(“n”);
    printf(“Case 2: “); c2(B); printf(“n”);
    return 0;
    }

    The second instance of B is never invoked (via the c2 that takes in a const arg). Somehow, it is being eliminated away! This is exactly the problem with my code: The call to f(n) in call_unary() is being eliminated!

    Once I “specialized” (over-loaded, really) the template call_unary for the function pointer, I get the right answer with gcc 4.0.1 (I can’t submit to Codechef and check, but I bet I’ll get the right answer on the server now).

    Just add the lines:

    void call_unary(Node *n, void (*f)(Node *)) {
    if(n) f(n), call_unary(n->left, f), call_unary(n->right, f);
    }

    after the decl of call_unary, and I think you should also be able to get the right answer.

    To me, this strongly looks like a GCC bug.

  45. @Balakrishnan, you are correct in that this is related to the call_unary function; but I don’t think the bug is in my code.

    I just nailed the sucker down to what I believe to be a GCC bug. Try the code with gcc 4.0.1 (which is what I think you and the server are both using):

    template void c1(ProcObj &f) { f(); }
    template void c2(const ProcObj &f) { f(); }

    void B(void) { printf(“B invoked”); }

    int main(void) {
    printf(“Case 1: “); c1(B); printf(“\n”);
    printf(“Case 2: “); c2(B); printf(“\n”);
    return 0;
    }

    The second instance of B is never invoked (via the c2 that takes in a const arg). Somehow, it is being eliminated away! This is exactly the problem with my code: The call to f(n) in call_unary() is being eliminated!

    Once I “specialized” (over-loaded, really) the template call_unary for the function pointer, I get the right answer with gcc 4.0.1 (I can’t submit to Codechef and check, but I bet I’ll get the right answer on the server now).

    Just add the lines:

    void call_unary(Node *n, void (*f)(Node *)) {
    if(n) f(n), call_unary(n->left, f), call_unary(n->right, f);
    }

    after the decl of call_unary, and I think you should also be able to get the right answer.

    To me, this strongly looks like a GCC bug.

  46. My actual submission passed in the contest with subtracting 1e-8 from k.

    Ashutosh’s submission passes all 1000 tests on my system when compiled as is with g++ 4.2 or 4.3. I ran it under valgrind, and there are no uninitialized or out-of-bounds memory accesses.

  47. My actual submission passed in the contest with subtracting 1e-8 from k.

    Ashutosh’s submission passes all 1000 tests on my system when compiled as is with g++ 4.2 or 4.3. I ran it under valgrind, and there are no uninitialized or out-of-bounds memory accesses.

  48. @Ashutosh This does seem to be a GCC bug and the error is indeed in call_unary. We will be upgrading to GCC 4.3 shortly. This should be fixed before the next contest.

  49. @Ashutosh This does seem to be a GCC bug and the error is indeed in call_unary. We will be upgrading to GCC 4.3 shortly. This should be fixed before the next contest.

  50. @Ashutosh This does seem to be a GCC bug and the error is indeed in call_unary. We will be upgrading to GCC 4.3 shortly. This should be fixed before the next contest.

  51. @Ashutosh This does seem to be a GCC bug and the error is indeed in call_unary. We will be upgrading to GCC 4.3 shortly. This should be fixed before the next contest.

  52. Hi to all..
    i m new to codechef.com..
    i wish to apply fr august minichallenge…
    wether any registration other than registering to codechef.com is needed…
    plz clarify my doubt…

  53. Hi to all..
    i m new to codechef.com..
    i wish to apply fr august minichallenge…
    wether any registration other than registering to codechef.com is needed…
    plz clarify my doubt…

  54. Hi to all..
    i m new to codechef.com..
    i wish to apply fr august minichallenge…
    wether any registration other than registering to codechef.com is needed…
    plz clarify my doubt…

  55. Hi to all..
    i m new to codechef.com..
    i wish to apply fr august minichallenge…
    wether any registration other than registering to codechef.com is needed…
    plz clarify my doubt…

  56. Hi to all..
    i m new to codechef.com..
    i wish to apply fr august minichallenge…
    wether any registration other than registering to codechef.com is needed…
    plz clarify my doubt…

  57. Hi,
    Please please add the editorial section like the one in TC. Best solutions explained for each problem. It will help us to learn.
    Thanks please.

  58. Hi,
    Please please add the editorial section like the one in TC. Best solutions explained for each problem. It will help us to learn.
    Thanks please.

Leave a Reply