gilcu3's blog

CRYPTO4
By gilcu3, 13 years ago, In English

I know this problem CRYPTO4 a long time ago, and although I implemented all the ideas given here, and some of my own, I still get TLE, so, has someone around here solved it, and is willing to share some hints???

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nobody??? Not even an opinion.....

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

It's proved, years don't pass along your mind :) After 3 years, you take a look at the problem again, think of it about 15 minutes, and you get a new optimization that solves it :) In this case that the longest meaningful code must be less than the length of the message :) solution

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

First of all, thank you kindly for source code with solution! However, I am a bit confused with 1 particular moment: why in the solution it is ok to pick n starting from m/2? How is that possible that it provides correct result if half of possible keys are ignored? Thanks in advance!

→ Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    If a key of length k is valid, then that key squared (of length 2 * k) is valid too, so we only need to check key lengths that can't be squared, aka starting from m / 2.

    → Reply