Today, the problem G2 could be solved in an extravagant way, using randomized xor-hashing, I am not quite sure what is the chance that I will get hacked,so please feel free to either try and hack my solution, or write a comment describing approximated chance of my random getting hacked. (If you do come up with the approximation, i will edit the blog to include your statement)
Here`s the submission 238069601
UPD: My solution turned out to be the one that is the main one
You can't hack the FBI.
The probabilty is analogous to the following — Among n people, the probability that atleast 2 have same birthday.
Its formula is well known. To approximate the value in this case , I found an upper bound on the probability by using identity e^x = (1+x/n)^n for large n ( in this case ~1e18) it turns out that probability of this happening is of the order of 1e-7 ie almost 0 Note that if we use int instead of long long for hashing the probability is of the order of e^400 ie it is guaranteed that the solution will not work
If there is some mistake, please point it out
This assumes (among other things) that the input is random, but the OP specifically is asking for manually crafted input to break the code.
But a hash value created will be equally random whatever input may be given isn't it?
The figure e^400 is of course an error. Happens in case you use incorrect approximations. But yeah in case of int the probability of 2 integers clashing will be very close to 1
Can you please explain your solution?
I will try, but i am bad at explaining, the part with XOR-hashing is there just for finding the segments that are isolated (for every a_i in that segment, the other element that equals a_i is also in that segment).
After that, we have a list of those segments (also you have to understand that for all pairs of segments they can be either non-intersecting, or one is inside of the other).
After finding all segments you can see that the result is minimal cover of the array, that is a well-known problem (but actually I overlooked that dp solution and understood it only now), the second part is a little bit tricky, because for every isolated segment that is included in final minimal answer, we can start by choosing any element that is covered ONLY by that segment.
Now we calculate number of those elements for every chosen segment, after that the final answer is just the product of those numbers
i think it will be very hard to hack a lgm so orz
Hacked THE FBI using HTML!
that is actually clever))))
you can refer here.