Today, finally for the first time in history, I got a test case to hack the problem 2155D - Batteries.
But the contest had already ended :(
The test case is actually easy:
(n = 40, a = 4) and the active positions are (1,14,27,40). It should be solved in under (400) operations, but everyone who wrote code that checks by iterating over the gaps between the batteries will get the result in approximately (403)–(404) queries.
One day I'll also hack, today I got the motivation.
UPDATE — It's only for those who did not do cyclic test. (Including tourist)
- MLA19 Do add this test case for later testing in practice.
The tests are bad IMO. People wrote O(t * m) code in E which should TLE but passes
I think you mean about $$$O(n^2)$$$, yeah that's the code I'm talking about. But that is actually smart, The code will always give the output in approx the same steps as desired. But yeah approx doesn't always mean less than equal to right :)
No I mean that in Problem E
People are doing this
This for loop over O(m) but there is no bound on sum of m so its TLE
Oh, The cases were really weak, man.
Not necessarily. 2e9 operations is large, but every one of them is a single OR operation. Time limit is 2 seconds. If we assume one cpu cycle per OR instruction, no compiler optimisation, and 1GHz CPU 2e9 OR operations pass. But codeforces most probably uses faster CPUs, and GCC definitely vectorized the OR operation here because it's GCC it likes doing black magic optimisations. So it should easily pass. Bitwise operations are just way too fast.
The array is cyclic, so when your step size is 1, (40+1) gives you a pair (40,1) to check, hence the code that you're talking about will ask exact 40 queries.
run this code to try out different cases, i have currently used your case with my code.
Yeah, that could work, but not all people did it cyclic, actually you might be the rare one. Congrats:)
We can get the answer here in 40 queries right, because we will get the pair (1, 40) in n iterations for checking the gap length = 1
If doing cyclic yes.
TLDR: those who only asked for (i,j) such that j = i — step , for a step size = step.
and did not consider the pair(i, (i+step)%n+1) , should fail this case mentioned. (tourist is one of them btw).
It wouldn't have mattered whether the contest ended or not :(. Hacks were disabled for the problem from the start...
Oh, that's a relief. I was actually thinking I should've done it before hand. Now I won't regret. Thanks
Auto comment: topic has been updated by karan_garg_12 (previous revision, new revision, compare).
Uphack when?
What is Uphack now ?
OK,I'll provide uphack to system though it won't change ranks.
Could you tell me how can one do it ? Like codeforces has something like Uphack ? I'd like to know. Also would like to do it myself.
For someone who got at least CM,can hack others after contest in a week,it can't change the rank but will be used for furthur submission.
Oh that's nice. Yeah sure go ahead and add this. Thanks for the info.
Sorry,hacks are unavailable just for the task.
In this testcase, tourist code is finding the answer in 403 operations [1, 14, 27, 40]. It supposed to be find in under 400 operations. Please check on this MLA19
I solved the problem in a rather different way from every other solution I have seen; mine seems to get your sample test case in 146 tries, but I am not entirely convinced that my method always works regardless (I ended up submitting right at 1:59:59 and fortunately didn't have any typos, but I didn't have the chance to fully prove to myself that my solution is sufficiently optimal).
What I did:
I start out by creating buckets of size 1. I then continually merge two same-size buckets from small to large forming buckets of size increasing powers of two (with singular buckets across levels being merged small to large at the end).
When merging two buckets, I perform all pairwise queries of the form $$$q(i, j)$$$ such that $$$i \in \text{bucket 1}$$$ and $$$j \in \text{bucket 2}$$$, after which $$$\text{new bucket} = \text{bucket 1} \cup \text{bucket 2}$$$.
342117601
I didn't fully understand your approach, but mine was also guessing in approx 146 queries. My approch was to divide the array in first n/2 blocks then check each block if that block separately have the pair or not, if not now divide the array in n/4 blocks and so on. I got this approach with the idea of pigeon hole principal.
I revised my explanation a bit so that it is hopefully a bit easier to understand. It sounds like I do the same thing as you but in reverse (instead of starting with two blocks and splitting, I start with $$$n$$$ blocks and merge).
Edit: actually, it sounds like you go bottom-up, so we are doing the same thing (I just had a messy implementation).
Same, I'm merging blocks, but starting from n/2.
342105370
your solution is correct runs in roughly $$$O(\frac{3n^{2}}{4a})$$$ queries
nevermind, your case fails this case:
n = 19, a = 3
active positions: (1, 6, 14)
query limit is 120
your code takes 121 queries
Out of curiosity, is my issue the fact that I wait to use the leftover ones at the end instead of just merging them with the next size up immediately?
yes
I most definitely panicked when trying to implement at the end and made a bad last-minute decision to add the separated merging in... oops.
Exactly the same as yours!
I wrote a similar solution in the contest and it passed, but after the contest I found it was not correct by doing stress tests.
FYI, my solution fails with the following case: $$$n=9$$$, $$$a=3$$$, positions $$$\{ 4, 8, 9 \}$$$, max allowed queries $$$27$$$, my solution makes $$$28$$$ queries.
I think this could be avoided is the interactor uses an approximate algorithm on MIS.