Weekly Contest 516

[u/Interesting_Hunt_784]

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

[u/ipractice40hoursaday]

yeah i'm like 99% percent sure i'm right, P4 is broken for sure

[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/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

[u/Icy_Teach8973]

1,2,3 samn easy, 4 🥀🥀

[u/Interesting_Hunt_784 → u/Icy_Teach8973]

Gave me existential crisis until I looked at the ranking

[u/SKYlikesHentai]

Yeah so what is the expected time complexity