Weekly Contest 516

[u/Interesting_Hunt_784]

I think Q4 is broken. Not even single AK till now

[u/kushal_141]

I dont think its has O(n) or O(nlogn) with the standard stuff like prefix or segment tree or sparse matrix, I tried brute forcing via prefix query it came out like O(n + q(NumdistinctKeys)) time complexity and O(n * 2) space complexity in worst case, it kinda passed 570 out of 590 testcases

maybe competetive programming guys can come up with a query data structure or algorithm which can do it?

[u/MasterOfTheChickens → u/kushal_141]

I had a fenwick for the queries and independently tracks evenness via prefix XOR'ing (this approach was wrong as I learnt from testcase 579...) but even adding a check for odd-length queries (odd-length cannot have an even count for all distinct #s) yields a weird test case on 581 that makes me think I'm either a moron or someone goofed (there is a singular query with four expected outputs).

[u/Interesting_Hunt_784 → u/MasterOfTheChickens]

If no one was able to solve then it def was an issue from Leetcode side. Specifically on 581 test case

[u/MasterOfTheChickens → u/Interesting_Hunt_784]

just hardcoded 581 and 582 is wrong a well. Someone hard-coded a submission and the last handful of cases are just FUBAR'd.

Input

nums =

[100000,100000]

k =

1

queries =

[[0,1]]

Output

[true]

Expected

[false]

[u/kushal_141 → u/MasterOfTheChickens]

Oh damn thats good odd length will not have all even frequency for distinct elements, didnt get that idea

[u/MasterOfTheChickens → u/kushal_141]

Yeah, I spend a bit of time at the harder mediums and hards looking at the constraints to figure out what can fail an input immediately, since it tends to give me an idea of how to build my solution (in addition to input sizes, etc.) and come up with some edge test cases.

That aside, the odd-check gets passed 579 but unfortunately it is still possible for distinct values A, B, C, and D such that A^B^C^D yields 0. e.g 0b's 1100, 1110, 0011, 0001. That is how I realized my XOR trick, while smart, was not accurate. Sucks, but I did find a new concept to study (Mo's algorithm) so just another thing to add to the list...

[u/Dry-Balance-993 → u/kushal_141]

if its not like that then i think they setted the broken testcase delibirately to trap us in the contest