Hello everyone!
JOI Open Contest 2023 will be held from Saturday, August 5, 04:00 UTC to Sunday, August 6, 04:00 UTC. You can start any time and the duration is basically 5 hours. Note that the duration becomes shorter if you start after Saturday, August 5, 23:00 UTC, i.e. less than 5 hours before the contest ends.
There will be 3 tasks, and the maximum score for each task is 100 points. Since this is an IOI-style contest, there may be some subtasks. Each submitted source program must be written only in C++. Problem statements will be provided both in Japanese and in English. You can find more details in the contest page.
Past contests are also available in this page, and you can test your code in oj.uz website.
Good luck and have fun!
I'm sorry I misspelled your name
Hi Masataka Yoneda!
Bump
Looking forward to the problems! Also I hope after the contest finishes, the test data can be released ASAP.
Contest Started
Now the contest begins. You can start any time between Saturday, August 5, 04:00 UTC and Sunday, August 6, 04:00 UTC. Good luck and have fun!
Can anyone share the solutions to problem ANCIENT2 and CELL?
When will the problems be available in oj.uz?
You can solve all problems here: https://oj.uz/problems/source/639
Thank you for your participation!
The contest has ended. Now you can see the ranking, test data, editorials, sample programs at the Contest Website. The English editorials will soon be ready. The analysis mode is enabled for 7 days, and you can upsolve the problem in the contest site during this period.
We appreciate your feedback from JOI Open Contest 2023 Survey (Google Form). Thank you!
How to get (> 10) points on problem A?
You can detect the xor of all bits of the form $$$a + b \cdot k$$$ for all $$$k$$$, where $$$a,b \leq B$$$, by building a machine that is two cycles of length $$$b$$$, but on one position of both cycles, making the $$$1$$$ input, switch you to the other cycle. (This machine is of size $$$2b$$$)
If you use enough of these operations, the hidden bit sequence is uniquely determined and can be found using gaussian elimination. What you actually need is $$$1000$$$ of these xor detectors such that these vectors in the vector space $$$\mathbb{Z}_2^{1000}$$$ (vector space of all sequences of $$$1000$$$ bits) form a basis.
With some offline bruteforcing you can verify that you can find such a basis for quite small $$$B$$$. By building some special machines to get some other bits of the hidden sequence to optimize $$$B$$$ some more, you can get $$$98$$$ points.
I was able to make this work in contest, but it feels unintended since I needed a bitset to make it pass. The basis can be computed offline, but how would you actually find the representation of each individual bit without either storing MBs of info in your source code or running some sort of xor basis algorithm (which should be N^3)?
I also used bitsets, and it gives $$$O(n^3/w)$$$ gaussian elimination, which runs very quick. But writing gaussian elimination $$$\mod 2$$$ with bitsets is actually easier to write than with vector<bool>'s or something, so from the start I implemented that. The basis finding I also did with bitsets, and that ran fast enough, that I could just run on the server. (looking at my submissions, my program uses about 0.042 s). I wouldn't be surprised if some non-bitset implementation also can work.
Yeah, I did all of the above too. I'm just wondering if bitset is required since it seems unusual for an OI to have an intended solution with bitset.
Checking the model code, it appears that bitset is, in fact, intended.
I just tried upsolving this problem and instead of using offline bruteforcing to find the basis, I just randomly generated $$$a$$$ and $$$b$$$ until they are linearly independent. It was able to find a basis very quickly and ac-ed the problem comfortably. Do you know why this is so?
Code
The are only ~$$$51 \cdot 51/2$$$ different $$$a,b$$$ combinations, you can just as well search through them all, and it will be fast enough. Randomly trying them, results in at most a $$$\log$$$ factor slow down, due to some harmonic series argument. The offline bruteforcing was only to verify that such a basis exists, I just pasted this "bruteforce" in my sourcecode.