### errorgorn's blog

By errorgorn, 20 months ago,

Note: I am not sponsored by the JOISC committee, if the committee is not ok with prizes, I will remove them.

I have managed to solve this problem with $n=45000$. As far as I know, the person with the highest $n$ other than me is jqdai0815 who has achieved $n=44000$ in this comment.

I think this problem is quite interesting to constant optimize, so I am offering prizes for people who can improve the solution. The prizes work as follow:

• For every increase of $\min(\lfloor \frac{n}{100} \rfloor,460)$ by $1$, I will give the person 5USD (sorry, I'm still a broke student).
• You must link a submission of your code on oj.uz that is AC.
• You must state the value of $n$, rounded down to nearest $100$, that your code works in under $1$ million queries.
• As a bonus, you can explain what your optimizations are (well, I would like to know how you were able to optimize this problem).
• If this limits of $n$ turns out to be too hard, I might make the conditions more lenient.

I'll start first.

This is my solution: https://oj.uz/submission/619999. It can barely solve $n=45000$. The maximum number of queries used in $10$ random tests is $999920$.

These are my optimizations
Here is the test case generator, if you want

Good luck!

UPD: The maximum value of $n$ has been capped to $46000$, I think $50000$ was probably too unrealistic of a goal.

• +219

 » 20 months ago, # |   -68 Hello, how should i use the test case generator? What I was thinking was to output the test case generator output into a file and then input from that same file when i test my code. Is that how I should do it or is there a better way?Thank you