errorgorn's blog

By errorgorn, 2 years ago, In English

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.

  • Vote: I like it
  • +219
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it -68 Vote: I do not like it

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