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.

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.

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.

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.

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.

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.

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.

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.

@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!

@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!

@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!

@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!

@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!

@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!

@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!

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 .

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 .

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 .

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 .

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!!!

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!!!

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!

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!

You can see any of the accepted solutions. The solutions are public as of now.

You can see any of the accepted solutions. The solutions are public as of now.

You can see any of the accepted solutions. The solutions are public as of now.

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!

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!

Also I prefer my name to be written as Balakrishnan V instead of B Varadarajan

Also I prefer my name to be written as Balakrishnan V instead of B Varadarajan

Also I prefer my name to be written as Balakrishnan V instead of B Varadarajan

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.

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.

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.

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

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

@Ashutosh: I downloaded your submissions and ran it against my local tester, and it passed all 1000 cases.

@Ashutosh: I downloaded your submissions and ran it against my local tester, and it passed all 1000 cases.

@Ashutosh: I downloaded your submissions and ran it against my local tester, and it passed all 1000 cases.

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

@Josh, much thanks for the help!
So either the bug in my program-generated proof is very subtle (that it fooled both our testers), or …

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.

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.

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.

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

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

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

@Balakrishnan V This is exactly what we get on the judge, but the output is different on our local machine.

Then I guess it must be some memory issue(overflow problem)

Then I guess it must be some memory issue(overflow problem)

Then I guess it must be some memory issue(overflow problem)

@Srihari We are thinking of introducing something of that sort. Stay tuned

Then I guess it must be some memory issue(overflow problem)

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.

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

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

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.

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.

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.

when I changed const ProcObj *f to const ProcObj f, it worked on my system. But even then it shows WA when I submit here.

when I changed const ProcObj *f to const ProcObj f, it worked on my system. But even then it shows WA when I submit here.

when I changed const ProcObj *f to const ProcObj f, it worked on my system. But even then it shows WA when I submit here.

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

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

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

@Balakrishnan, you were right. I just tried submitting via http://www.codechef.com/problems/F6/, and even after the fix, I get WA.

(The comments engine striped away the template declaration from my last message).

@Balakrishnan, you were right. I just tried submitting via http://www.codechef.com/problems/F6/, and even after the fix, I get WA.

(The comments engine striped away the template declaration from my last message).

I made one more change. I changed your SAFETY_EPS to 1E-6 instead of your previous 1E-7.. It worked.

I made one more change. I changed your SAFETY_EPS to 1E-6 instead of your previous 1E-7.. It worked.

I made one more change. I changed your SAFETY_EPS to 1E-6 instead of your previous 1E-7.. It worked.

It is worth noting that my AC solution on the actual contest too needed that change(1e-7 to 1e-6) to get accepted..

It is worth noting that my AC solution on the actual contest too needed that change(1e-7 to 1e-6) to get accepted..

It is worth noting that my AC solution on the actual contest too needed that change(1e-7 to 1e-6) to get accepted..

It is worth noting that my AC solution on the actual contest too needed that change(1e-7 to 1e-6) to get accepted..

It is worth noting that my AC solution on the actual contest too needed that change(1e-7 to 1e-6) to get accepted..

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.

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.

That means that Ashutosh’s code would have worked had he written const ProcObj f instead of const ProcObj &f

That means that Ashutosh’s code would have worked had he written const ProcObj f instead of const ProcObj &f

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

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

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

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

Thanks Balakrishnan, Josh, and Aniruddha for all your help! I really would never have figured out the problem without you guys

Thanks Balakrishnan, Josh, and Aniruddha for all your help! I really would never have figured out the problem without you guys

@Ashutosh You are welcome

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

Can we get all the test case data for problem F2 ?

@ankit It is there in the zipped file.

@ankit It is there in the zipped file.

From where can I get the zip file ?

From where can I get the zip file ?

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…

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…

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…

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…

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…

@ankit The file link is down. It will be available shortly.
@venky. You just need to register on http://www.codechef.com and you are good to go.

@ankit The file link is down. It will be available shortly.
@venky. You just need to register on http://www.codechef.com and you are good to go.

@ankit The file link is down. It will be available shortly.
@venky. You just need to register on http://www.codechef.com and you are good to go.

@ankit The file link is down. It will be available shortly.
@venky. You just need to register on http://www.codechef.com and you are good to go.

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.

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.

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.