FBI's blog

By FBI, history, 6 months ago, In English

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

  • Vote: I like it
  • +73
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +60 Vote: I do not like it

You can't hack the FBI.

»
6 months ago, # |
  Vote: I like it -53 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This assumes (among other things) that the input is random, but the OP specifically is asking for manually crafted input to break the code.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But a hash value created will be equally random whatever input may be given isn't it?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like 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

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you please explain your solution?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

i think it will be very hard to hack a lgm so orz

»
6 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Hacked THE FBI using HTML!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    that is actually clever))))

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can refer here.