So I will describe shortly what happened here.
The situation wasn’t like I didn’t see your messages, or ignored it.
I saw messages like check precision of your fft, are you sure of your fft? and I started panicking and ran big tests on brute force to confirm. After 20 minutes of running I saw that the test is correct so I was relieved. On the other hand a lot of people were getting 50 pts so I thought this is super normal and 1st subtask is ok. On polygon we had 4 solutions (2 fft,2 quadratic) for me and the setter and all were matching (same undefined behavior or I don’t know how is it called). On campus as well. On polygon you write input validator for every problem, and I did. Also, tester proof-read all of them. What I missed is, activating the validator for this problem (which would have detected the issue). I don’t know how i missed it, you should select a validator for each problem.
The test that people were failing on was like:
T=10
and there are only 9 testcases in the file
I am not an expert in undefined behavior to discuss the cases. Apparently, for a lot of people on the 10th case, the program was reading n = 0 and just terminating with no issues, and some other were keeping last value of n. For java an exception would be thrown I think. I am not sure why some c++ solutions were acting differently (maybe different input methods).
The fact that I didn’t activate the validator by just setting the field to “kthval.cpp” made this slip away. It would detect it because it will expect EOF
The result was ruining the contest for div1 which is something unfortunate. I would take a big part of the blame, and I feel like I owe the people a big apology. But neither me or the admin deserve that amount of negativity, we spent a lot of time to come up with the problems (which had a nice quality I think). It’s unfortunate that one mistake would turn all of it into nothing.
I just wanted to share this with the community, and my sincere apologies again. We as people make mistakes somtimes, and it’s not my first time setting problems in codechef (i also set a round before on CF) but this was the first time things go wrong.
As for the ratings, I have no idea and it’s up to admins.
The editorials will be posted in few hours I think.
27 Likes
So what was the problem with the test case that made most solutions fail ?
2 Likes
I really liked the contest problems. I really liked the contest overall.
The servers were running very smoothly.
The test file size, time limits were set properly.
Even Que1 was made very light so that it don’t create issues like long queue.
I totally appreciate all your efforts. I really liked the contest.
It’s just that even after pinging every 5-15 mins in comments, I might not get ratings.
I respect you for writing this post and for your efforts behind the contest.
3 Likes
The test that people were failing on was like:
T=10
and there are only 9 testcases in the file
I am not an expert in undefined behavior to discuss the cases. Apparently, for a lot of people on the 10th case, the program was reading n = 0 and just terminating with no issues. For java let’s say an exception would be thrown I think. I am not sure why some c++ solutions were failing and some other were not.
The fact that I didn’t activate the validator by just setting the field to “kthval.cpp” made this slip away. It would detect it because it will expect EOF
2 Likes
Hey can anyone please tell me how to submit the solutions as a team in codeforces
Some C++ solutions like mine were failing since N doesn’t read 0 and stores the last value of N and prints 9th test case N number of 0s on 10th line. Others might have read N as 0 based on their implementation.
Thanks for your understanding. In my opinion, the issue that happened is more than about some individuals rating. It’s about the frustration that happened to some people, and the contest experience that was ruined.
You can’t imagine how i felt after the contest. It’s not like I didn’t check because I am lazy, or it was an unproved idea. I just didn’t activate the validator, and the super unlucky thing is the admin set the first subtask for 50. If it was 20 let’s say, and top people were getting 80 I would have figured out immediately. Anyway,
Hope it never happens again in any contest.
2 Likes
Yeah exactly, but what I wanted to say is, I don’t know why some solutions were reading 0 and some other keeping last value. Unfortunately for us, 4 solutions were reading 0 
I was kind of sure that something is incorrect in tests and hence I made comment.
This is the first time when I commented about tests being incorrect.
I was not frustrated as I already expected a rejudge but some people’s experience might have been ruined.
I have very bad streak of experiences, Whenever I perform well, there are high chances of contest being unrated XD. I thought I will save it from being unrated this time. Hence kept pinging.
2 Likes
I personally liked more weightage on subtask because it might appreciate beginners to read all problems and even they will enjoy it if questions are tough.
1 Like
The problem is people were writing:
“are you sure of your fft”
“your fft has precision issues”
when people were questioning the correctness, we thought that it’s about the big testcase not the small, and that’s what confused us the most especially with tons of submissions getting 50 (seeing all of them made me think that ok our issue is in big test). Some people near the end of the contest wrote explicitly check 1st subtask, but it was way too late.
2 Likes
I wrote about brute force not passing since 8:30 pm (along with link to my solution) but I guess no one else did that except me.
Next time check by opening submissions of people to see where are they getting AC in sub1 or sub2 if points are equal in both. I know you were panicked. I understand as I have been setter/tester as well.
While everyone is busy in other things, can someone post the fft approach. I know the 50 points solution. Maybe its a too much to ask, but can someone elaborate their fft approach as in when they realise the whole problem boils down to fft multiplication. I haven’t read about fft but it seems it is fairly common among advanced techniques?
2 Likes
why is that problem removed from the practice session ?
Atleast test data is corrected this time.
last time in procon junior finals held on cc one problems test cases were wrong but they never agreed to it and wrong solution was getting ac
This is not the right place to ask this!
1 Like
F[i] = \sum_{j=i}^{n-1} A[j]*2^{n-j-1}*jC_i I am assuming 0 indexed here.
jC_i = {j!\over{i!}{(j-i)!}}
From the above equation we can remove terms containing only i and j by just multiplying A[j] with 2^{n-j-1} * j! and multiplying F[i] at the end with i!^{-1}.
Now all we are left with is:
F[i] = \sum_{j=i}^{n-1} {A[j] \over {(j-i)!}}
If we expand it we get {A[i] \over {0!}} + {A[i+1] \over {1!}} + {A[i + 2] \over {2!}} and so on. So we can compute F by just convolving the inverse factorial upto N in reverse with A. Later just multiply each F[i] with i!^{-1}
10 Likes
@ankit_btech well i thought that creating a new discussion thread for this simple doubt is a right place 
So we can compute FF by just convolving the inverse factorial upto N in reverse with A
. I was doing this in n^2. I think this can be done in nlogn by fft. I guess thats pretty standard .
@admin still waiting for editorials , kindly post.